Here is a paper called For Most Large Underdetermined Systems of Equations, the Minimal L1-norm Near-Solution Approximates the Sparsest Near-Solution. However, I did not quite get its definition of sparse, and under what conditions, the minimal L1 norm solution is not the sparsest one. Actually I construct a matrix (in Matlab):
A = [1 0 1 1 1 0 0 0 0 0; ...
0 1 1 1 0 1 0 0 0 0;...
0 1/4 0 7/16 0 0 0 0 0 0;...
1/3 0 7/9 0 2 0 0 0 0 0;...
1/9 1/8 119/216 0 0 4 0 0 0 0];
and,
b = [9 8 2 3 4]';
According to the paper, the L1 norm is to $min||x||_1$ subject to $||b - Ax||_2 \leq \epsilon$. Suppose its solution is $\hat x_{\epsilon}$. It also mentioned whenever there exists a sparse solution $x_0$, $Ax_0 = b$, and there are at most $(1+M^{-1})/4$ nonzero elements ($M$ is the maximal coherence between any two columns of $A$), then it satisfies,
$||\hat x_{\epsilon} - x_0||_2\leq 3\epsilon$
When I tried to solved such L1 norm linear equation (L1 magic package), I got the solution
[1 0 3.4286 4.5714 0 0 0 0 0 0]';
Yes this is sparser than L2 norm solution:
[2 1 3 4 0 0 0 0 0 0]';
But in fact this is also a solution of the original matrix equation:
[9 8 0 0 0 0 0 0 0 0]';
and it is sparser. The reason why L1 norm minimization does not pick this vector as the solution is because its L1 norm is larger ($17$ compared with $9$).
Did I miss something? I did not find the definition of sparse in the paper, is it possible that my linear equation construction doesn't meet some of the conditions mentioned in the paper?
I look forward to hear a reasonable analysis on what's going on with my simulation. Thanks.