Skip to main content
1 of 3
Paglia
  • 837
  • 1
  • 6
  • 16

Can I 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

Paglia
  • 837
  • 1
  • 6
  • 16