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 
 A: 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$$

A: 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.
A: 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).
