4
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ "More sparse" means "with more zero entries", as you correctly assume. Your example, however, does not contradict the results of the paper. Those results are probabilistic, so they are not guaranteed to hold for every matrix, but only for a "large enough subset" of them, asymptotically in their size (in a sense that is made formal inside the paper). I am afraid that you will need to grab a large bottle of coffee and go through all the definitions and theorems of the paper to understand it fully. $\endgroup$
    – Federico Poloni
    Jan 11, 2014 at 7:24
  • $\begingroup$ @FedericoPoloni Thank you Federico. Am I correct that the L1 norm always find out the vector with the sum of its elements minimal, rather than a sparser vector with very large elements inside? $\endgroup$
    – lennon310
    Jan 11, 2014 at 14:29
  • $\begingroup$ The sum of their absolute values, not simply their sum. But apart from that, yes, you are correct. $\endgroup$
    – Federico Poloni
    Jan 12, 2014 at 0:59

0

Reset to default

You must log in to answer this question.