Timeline for Can one always find sparse solutions to an $\ell^1$-minimization problem?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 9, 2014 at 12:31 | comment | added | Jean-Luc Bouchot | Now I see what you mean. I do not have an example on the top of my head right now, no. Sorry! | |
| Oct 8, 2014 at 13:29 | comment | added | Paglia | 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. | |
| Oct 8, 2014 at 12:30 | history | edited | Jean-Luc Bouchot | CC BY-SA 3.0 |
Added a counter example
|
| Oct 8, 2014 at 12:28 | comment | added | Jean-Luc Bouchot | 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. | |
| Oct 8, 2014 at 8:07 | comment | added | Paglia | Thank you for the suggestions! By the way, do you now an explicit counterexample? | |
| Oct 8, 2014 at 7:13 | review | First posts | |||
| Oct 8, 2014 at 8:06 | |||||
| Oct 8, 2014 at 7:10 | history | answered | Jean-Luc Bouchot | CC BY-SA 3.0 |