norms and sparsity

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

-
Are you dealing with L^2 norm of vectors of numerical data? Something like $\|x\|^2=x_1^2+...+x_n^2$ and for L^1 the taxi cab/Manhattan norm, am I right? –  Avitus Jul 19 '13 at 13:22
As Avitus suggested, it would help if you told us what kind of behaviour and in what context you have in mind, exactly, maybe with a simple example. –  tomasz Jul 19 '13 at 13:28
yes, I am dealing with numerical data. –  user86927 Jul 20 '13 at 5:48
The $L^2$ norm squares each component of a vector. If a component is large, then squaring it makes it huge, which is a disaster. The $L^2$ norm tries hard to avoid this. If a component is small, then squaring it makes it tiny and negligible. The $L^2$ norm doesn't mind if a vector has many small components. On the other hand, for the $L^1$ norm it's not such a disaster if one component of a vector is large. And having several small components isn't preferable to having a single large component. –  littleO Jul 20 '13 at 22:33

I think the overall context you're referring to is the problem of $L^0$ minimization, i.e. compressed sensing. So, the goal of your question is to find the relationship between the following problems:

$(P_0)\qquad \min \|x\|_0 \;s.t.\;Ax=y\\ (P_1)\qquad \min \|x\|_1 \;s.t.\;Ax=y\\ (P_2)\qquad \min \|x\|_2 \;s.t.\;Ax=y$

Since our goal is ultimately to solve $P_0$, the problem with $L^2$ minimization is as follows:

As you can see, it is generally unlikely that a matrix $A$ will have a $P_2$ solution that lies on any of the axes (i.e. a sparse solution). However, because of the "diamond-shape" of the set of equal $L^1$ norm, the $L^1$ solution is more likely to be sparse

As for your second question, here's an exercise from my own coursework that might help you understand this better

Consider $P_1$ as described above, where $x\in\mathbb R^N, A\in \mathbb R^{m\times N},y\in \mathbb R^m$, with $m\ll N.$ Then $(P_1)$ has a solution with at most $m$ non-zero entries. Accordingly, the solutions to the $P_1$ problem promote sparsity.

Actually proving this is an interesting exercise, and I can give you a hint there if you want it. The point is, we can guarantee a relatively sparse solution under $L^1$ minimization, which we can't generally do for $L^2$ minimization. In fact, if $A$ has the null-space property, we find that there is a unique solution like this.

Here's the hint that came with the problem:

Hint: suppose $\overline{x}\in\mathbb R^N$ is a solution to $(P_1)$ and $\|\overline{x}\|=k$ where $m<k\leq N$. It follows that $k$ columns of $A$ are linearly dependent. As a result, there exists a nonzero vector $h$ in $\mathbb R^N$ such that $Ah=0$.

Define $\widetilde{x}=\overline{x}+\epsilon h$ where $\epsilon\in\mathbb R$, then $A\widetilde{x}=y$, i.e., $\widetilde{x}$ is also a solution to $y=Ax$. Since $\overline{x}$ is a solution to $(P_1)$, we have $$\|\widetilde{x}\|_1=\|\overline{x}+\epsilon h\|_1 \geq \|\overline{x}\|_1$$
Therefore, we can choose $\epsilon$ such that

$$\|\overline{x}+\epsilon h\|_1=\|\overline{x}\|_1 \quad \text{ and } \quad \|\overline{x}+\epsilon h\|_0<\|\overline{x}\|_0$$

My solution to the problem

Let me know if there's anything you'd like clarified.

-
Thank you for your explanation. I see those figures everywhere when they explain the norms. Could you please explain how they represent L2 and L1 norms, respectively...! I fear, I may not be able to solve the exercise problem. Would you please provide me the solution, if possible...! Thanking you. –  user86927 Jul 20 '13 at 5:40
The two curves there are curves of constant norm. The circle is the curve given by $\|x\|_2=C$ for some $C\in \mathbb R^+$, and the first is the curve given by $\|x\|_1=C$. In both of these pictures, we have found the point that minimizes $\|x\|_p$ because we have found the curve $\|\vec x\|_p=C$ that is "tangent" to the line $\vec y=A \vec x$. That is, there can be no $x$ of smaller norm on that line. –  Omnomnomnom Jul 20 '13 at 18:34
I've added the hint. Let me know if that makes sense. The trick to actually doing the problem, if you'd still like to do it, is choosing the appropriate $\epsilon$ to complete the proof. –  Omnomnomnom Jul 20 '13 at 18:55
That first comment wasn't so clear. The curve on the right (the diamond) is the curve given by $\{x:\|x\|_1=C\}$, for some constant $C$. –  Omnomnomnom Jul 20 '13 at 21:08
Thank you for the hint. I could figure out and qualitatively understand the concept. But, I am stuck at the last expression. How the # non zero elements could be greater in x(bar). –  user86927 Jul 22 '13 at 10:41

The $L^2$ norm on any space focuses more on outliers because squaring a large number makes it much much larger compared to the smaller numbers than before; then these large numbers affect the average more, and taking the square root affects everything equally, so the outliers are still influential.

For instance, if you average $2$ and $100$, the second number is 50 times the first, and it pulls the average over to $51$. But $10000$ is $2500$ times bigger than $4$, so if we square them and average them, the $10000=100^2$ dominates even more, giving an average of $5002$, whose square root is 70.725, much closer to the outlier.

-
I got the point. But, do we take the average of numbers in calculating the norms..!? Please correct me if I am wrong. E.g. The L1 norm of v=(1,2,3) is 6 and L2 norm is 3.742. –  user86927 Jul 20 '13 at 5:55
You're right, for the 'normal' norms you don't average. I was thinking of general $L^2$ integrals, but it didn't come out very well. The other answer is much better! –  Brian Rushton Jul 20 '13 at 12:15