What is the meaning of double bars and 2 at the bottom in ordinary least squares?

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?

• 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
• 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

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}$
• 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
• Spelling error: "Frobenius". – hobbs Jan 6 '17 at 8:22
• Instead of "this is a common norm" I would've just said "L2 is the norm" ;) – Mehrdad Jan 6 '17 at 11:26