# Proving an Algorithm that generates minimal $\|x\|_0$ for the underdetermined system $Ax=b$

Let $A \in \mathbb {F}^{m \times n}$ with $m< n,$ $b \in \mathbb{F}^m$ and let $x$ be unknown in $\mathbb{F}^n.$ Assume $0<p<1.$ Then $$\arg \min\limits_{x: Ax=b} \|x\|_0 = \lim\limits_{p \to 0} \{\arg \min\limits_{x:Ax=b} \|x\|_p^p\}$$

The reason I'm asking this question is that I am anticipating it as a possible objection that could be raised during my final defense. If this question I ask above is, in fact, true, I can take care of it easily by showing that attempts to "approximate" $\|x\|_0$ for an underdetermined system of linear equations via taking examples from a sequence of minimizers decreasing in $p$ to $0$ is itself intractable, because simply finding $\arg \min\limits_{x: Ax=b} \|x\|_p^p$ is itself NP Hard (via reducing from the partition problem as given in Foucart).

My problem, however, is whether this should even be a concern; is the limit above valid, or, if the way I stated this is in error, could it slightly be modified to be valid? I know that $$\lim\limits_{p \to 0} \|x\|_p^p = \|x\|_0$$ (crudely, nonzero numbers proceed to 1 while zeros stay zero) but i do not know how to show this rigorously as my analysis is rusty, and I do not know whether even showing this part would provide aid to my main problem at all.

Any help would be deeply appreciated!

• It is not true that $\|x \|_p \to \|x\|_0$, as can be seen by the different scaling behaviour on both sides. What is true is $\|x\|_p^p \to \|x\|_0$. – PhoemueX Mar 12 '17 at 9:06
• I would expect this to be true: under some strong conditions on the matrix, such as if $\delta_{2s+2} < 1$ then for $p \leq p^*$, with $p^*$ small enough (depending on $\delta$ I suppose), the recovered solution to the $\ell_p$ constrained problem is indeed the sparsest, see Thm 2.1 and discussions math.tamu.edu/~foucart/publi/FL08final.pdf . This would need to be written nicely though, since I'm not sure how the application $p \mapsto x^*_p$ behaves at $p = 0$. In general (i.e. non compressed sensing problems) I do not expect this to be true. – Jean-Luc Bouchot Mar 12 '17 at 9:34
• PhoemueX, thanks for pointing that out! It has been fixed. – Thomas Rasberry Mar 13 '17 at 18:46
• I am missing something here... you are asking whether the result in the gray box is true? You have written it in your thesis but you haven't proved it nor provided a reference, and now you are afraid that the committee will object during the defense? Is this correct? – Federico Poloni Mar 13 '17 at 19:22
• Yes, I am asking whether this is true. I have not written it in my thesis since I can neither prove nor source it, but merely wonder if the question ought to be anticipated during my final oral exam, and if so, how to prepare. From what I have seen here, the answer is "no," except perhaps under very specific conditions. – Thomas Rasberry Mar 13 '17 at 19:33