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

Question

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?

Answer 1

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}$