I saw this notation for ordinary least squares here.

$$ \min_w \left\| Xw - y \right\|^2_2$$

I have never seen the double bars and the 2 at the bottom. What do these symbols mean? Do they have specific terminology for them?

  • 4
    The use of the double bars just indicates that we are using the L2 norm. – Michael Chernick Jan 5 '17 at 17:18
  • @MichaelChernick and the 2? Is that part of "L2 norm"? – Aseem Bansal Jan 5 '17 at 17:19
  • 1
    Yes, like L2, there is also L1. – Jon Jan 5 '17 at 17:22
  • I think $X_w$ should be $Xw$ since $w$ is a vector – ilanman Jan 5 '17 at 18:01
  • @ilanman Yes that is what was in the notation before the edit. I changed it back – Aseem Bansal Jan 5 '17 at 18:07
up vote 28 down vote accepted

You're talking about the $\ell_2$-norm (Euclidean norm) of the vector ($Xw - y$). If this foreign to you, briefly, the $\ell_p$-norm of a vector $u \in \mathbb{R}^{n}$, is:

$$\|u\|_p = \big(\sum_{i=1}^{n} |u_i|^p\big)^{\frac1p} $$

So in your case $\|u\|_2^2 = (\big(\sum\limits_{i=1}^{n} |u_i|^2\big)^{\frac12})^2 = \sum\limits_{i=1}^{n} u_i^2$ which is consistent with the sum of squared residuals for a linear regression. In the context of regression problems, you'll also see this a lot in mean squared error (MSE) calculations, and in ridge regression.

This is a common norm (among other reasons, it's mathematically convenient), so when it's obvious from the context, you'll see the lower $2$ omitted, and just $\|u\|^2$.

As mentioned in the comments, you may also see the $\ell_1$-norm:

$$\|u\|_1 = \sum_{i=1}^{n} |u_i| $$

Which corresponds to the absolute value. Again, you'll see this in mean absolute error (MAE) or lasso problems.

Other popular norms:

  • $\ell_0$-norm: Hamming distance, or # of non-zeros in a vector, i.e. in calculating the sparsity of a vector. Technically this isn't a norm (it's a cardinality function), because you have a $\frac{1}{0}$ term in the definition, but it has the form of a norm so we call it one.
    • This norm is the ideal norm used in inducing sparsity for regression problems since we really want to zero out coefficients, however computing $\ell_0$ regularization is NP-hard, so instead we approximate it with $\ell_1$ which is solvable via linear programming. It's also popular in Compressed Sensing.
  • $\ell_{\infty}$-norm: = $\underset{i} {\text{max}}$ $\{|x_i|\}$ for $i = 1, ..., n$
  • $\|A\|_F$: Frobenius (Euclidean) norm, applied to a matrix $A \in \mathbb{R}^{n\times m} = \sqrt{\sum \limits_{i=1}^{n}\sum \limits_{j=1}^{m}|a_{ij}|^2}$
  • 2
    The link to wolfram alpha was really helpful. – Aseem Bansal Jan 5 '17 at 18:12
  • You write that the $\ell_0$ (pseudo)norm counts the number of zeroes in a vector—did you perhaps mean the number of non-zero entries? (This would be more consistent with what I've seen, and also would mean that $\lVert u \rVert_{0}$ would be the Hamming distance between $u$ and $0 \in \mathbb R^n$, as opposed to being $n$ minus that distance.) – wchargin Jan 5 '17 at 22:16
  • Yes you're correct thanks! – ilanman Jan 5 '17 at 22:29
  • 1
    Spelling error: "Frobenius". – hobbs Jan 6 '17 at 8:22
  • 1
    Instead of "this is a common norm" I would've just said "L2 is the norm" ;) – Mehrdad Jan 6 '17 at 11:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.