# Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem

$$\min \|x\|_1 \quad s.t. \;\; A x = b,$$

admits an $m$-sparse solution in general?

The only result that I've found so far is Theorem 3.1 in [1]. It states that if the solution is unique, then it is also $m$-sparse.

[1] S. Foucart, H. Rauhut. A Mathematical introduction to Compressive Sensing

• Question reformulated in terms of the optimality system: $x^*$ is an $\ell^1$-minimal solution if $Ax^*=b$ and there exists $w$ such that $A^T w \in\partial\|x\|_1$. This says: there is no $m$-sparse solution if the range of $A^T$ (which is $m$-dimensional) does not intersect the $m$-dimensional faces of the unit cube. Answers to this question show that for $m\geq n/2$ this can not happen. (Unfortunately, $m$ and $n$ are swapped in the linked question.) – Dirk Oct 8 '14 at 13:44
• Thank you @Dirk, this seems really interesting... I will check – Paglia Oct 8 '14 at 13:55

Consider the case where $N = 2$, $m = 1$ and take $A = [1,1] \in \mathbb{R}^{1 \times 2}$. Your optimization problem becomes, take $b \in \mathbb{R}^m$ as you wish, say $3$ $$\min \|(x,y)\|_1 \quad s.t. \;\; x+y = 3,$$
In this case, you have infinitely many solutions $\{(x,y): x = 3-y, 0 \leq y \leq 3 \}$. They all have a $\ell^1$ norm equal to $3$ and yet only $2$ of them are $1$-sparse.
• Consider the case where $N = 2$, $m = 1$ and take $A = [1,1] \in \mathbb{R}^{1 \times 2}$. Your optimization problem becomes, take $b \in \mathbb{R}^m$ as you wish, say $3$ $$\min \|(x,y)\|_1 \quad s.t. \;\; x+y = 3,$$ In this case, you have infinitely many solutions $\{(x,y): x = 3-y, 0 \leq y \leq 3 \}$. They all have a $\ell^1$ norm equal to $3$ and yet only $2$ of them are $1$-sparse. – Jean-Luc Bouchot Oct 8 '14 at 12:28
• I am confused... In your counterexample there actually exists 1-sparse solutions, even if they are only 2. I am wondering if there are cases where $m$-sparse solutions of the problem do not exist. – Paglia Oct 8 '14 at 13:29