3
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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.) $\endgroup$ – Dirk Oct 8 '14 at 13:44
  • $\begingroup$ Thank you @Dirk, this seems really interesting... I will check $\endgroup$ – Paglia Oct 8 '14 at 13:55
1
$\begingroup$

No. It is not true. The theorem you state "assumes" the existence and uniqueness of the solution and proves that in this case, you this particular solution cannot have more non-zero components than the number of measurements. The existence is proven under RIP (Chapter 6, e.g. Theorems 6.9 and 6.15), null space properties (Chapter 4, e.g. Theorem 4.4), incoherence properties (Chapter 5, e.g. Theorem 5.16), ... and I think that's it as of today.

EDIT: As suggested in a comment here is a counter example:

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.

$\endgroup$
  • $\begingroup$ Thank you for the suggestions! By the way, do you now an explicit counterexample? $\endgroup$ – Paglia Oct 8 '14 at 8:07
  • $\begingroup$ 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. $\endgroup$ – Jean-Luc Bouchot Oct 8 '14 at 12:28
  • $\begingroup$ 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. $\endgroup$ – Paglia Oct 8 '14 at 13:29
  • $\begingroup$ Now I see what you mean. I do not have an example on the top of my head right now, no. Sorry! $\endgroup$ – Jean-Luc Bouchot Oct 9 '14 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.