Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
1  
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

2 Answers 2

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:

Lecture notes screen shot

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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