TITLE: norms and sparsity
QUESTION [3 upvotes]: Could anyone please elaborate on why $L^2$ norm moves toward the outliers compared to $L^1$ norm. I mean, what property/quantity in the mathematical expression of the norms makes it perform such way.
One more thing is, how $L^1$ norm introduces more sparsity in the solution?
Thank you.
Praveen

REPLY [0 votes]: Note: since sparsity metrics are independent of the scale (or are 0-homogeneous), it could be interesting to look at ratio of norms or pseudo-norms (ratios are scale-independent), instead of norms, which are 1-homogeneous, see at the end.
Why does $\ell_2$ move toward outliers more than  $\ell_1$? Mostly before errors to the square amplify the relative weight of large distances, hence toward potential outliers.
More precisely: if you have a set of numbers $x_k$, and seek a single number $\overline{x}$ as  a central tendency to represent them all, you can find it by minimizing a suitable cost function. Minimizing the $\ell_2$ (Euclidean) norm ($\sum_k (x_k-x)^2$) yields $\overline{x}$ to be the sample average. Minimizing the $\ell_1$ (Taxicab) norm ($\sum_k |x_k-x|$) yields $\overline{x}$ to be the median (when properly defined).  This concept can be extended to (polynomial) regression, the case of central tendency representing a polynomial of degree 0. Least-square minimization is most common, least-absolute deviation is thought to be more robust. The sensitivity to outliers can be related to the derivative of the cost function. With $\ell_2$, the derivative relates to the signed distance to the objective (hence it is amplified by long-distance outliers). With $\ell_1$, the derivative relates to the sign of the position with respect to the  objective (hence it does not matter whether an outlier is far or not).
A simple example is a set of samples and one outlier: $2n$ ($n>0$) times the number $a$, and an outlier $b$. The median yields $a$ (insensitive of the outlier), the mean $\frac{2na+b}{2n+1}$, which can get as high (or low) as you want with suitable $b$. Very sensitive to only one outlier. This is the simplest example for robust statistics.
For far, we talked about cost, or "data fidelity term": a function that measures how far observed data is from a model.
Depending on the relative dimension of the data and the model, many impose further conditions, to build simpler models. One of them is sparsity, a key concept, yet complicated in practice. A signal, a model is sparse if its number of non-zero samples/coefficients/parameters of small. This amounts to the minimization of an $\ell_0$ penalty, which is intractable in general. But under some conditions, it can be equivalent to an associated $\ell_1$ penalty  (which is tractable), for which @Omnomnomnom gave a good explanation.
Let me add that claiming that $\ell_1$ yields sparser solution is still debated in a lot in applications (signal processing, statistics). Indeed, norms are $1$-homogeneous, while the parsimony index $\ell_0$ is not (it is $0$-homogeneous). So if you multiply a vector by $a>0$, its  $\ell_1$  and  $\ell_2$ norms are modified, while the vector sparsity index has not changed.
Additional discussions are in Why L1 norm for sparse models. Recently, some works have shown interest in norm ratios (such as $\ell_1/\ell_2$), that may provide interesting proxies (ie tractable) for $\ell_0$ penalties (see for instance Euclid in a Taxicab: Sparse Blind Deconvolution with Smoothed l1/l2 Regularization, or SPOQ ℓp-Over-ℓq Regularization for Sparse Signal Recovery applied to Mass Spectrometry).
{"set_name": "stack_exchange", "score": 3, "question_id": 447370}