Timeline for $\ell_o$ Minimization (Minimizing the support of a vector)
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 2, 2014 at 18:27 | answer | added | Ed Klotz | timeline score: 1 | |
| Jul 11, 2012 at 2:52 | comment | added | Clark | Thanks Suvrit. That is actually similar to the formulation I have been looking using. I was hoping that someone had some published work on it, but perhaps not. | |
| Jul 10, 2012 at 9:54 | comment | added | Suvrit | You can trivially cast it as an integer programming problem by introducing an indicator vector $z$, so that $z^T1$ gives you the $\ell_0$-quasi-norm of $x$, and then recast in terms of $z$. The problem remains hard, but now the objective is linear. | |
| Jul 8, 2012 at 13:19 | comment | added | Clark | It is the number of non-zero elements in the vector. The support of a vector $s=supp(x)$ is a vector $x$ whose zero elements have been removed. The size of the support $|s| = \|x\|_0$ is the number of elements in the vector $s$. | |
| Jul 8, 2012 at 6:36 | comment | added | Dima Pasechnik | Sorry, what do you denote by $\|\dot\|_0$? | |
| Jul 7, 2012 at 20:58 | comment | added | Clark | The goal of any reformulation that would be interesting to me would include a linear objective function. While the problem is NP-hard, the reformulation could be susceptible to various heuristics or other approximations. I know any formulation will not be an "easy" one, but I still wanted to see if any existed. | |
| Jul 7, 2012 at 19:48 | comment | added | Dirk | Still a question remains: What is the aim of your reformulation? In other words: what is wrong with the $\ell^0$-minimization problem? As you have written: The problem is NP-hard and hence, there will be no "easy" reformulation with out any further assumption on $A$ (unless $P=NP$). | |
| Jul 7, 2012 at 16:03 | history | edited | Clark | CC BY-SA 3.0 |
added 24 characters in body
|
| Jul 7, 2012 at 14:30 | comment | added | Clark | An exact formulation is my major goal, but I would be interested to see a relaxation as well. | |
| Jul 7, 2012 at 14:09 | comment | added | Dirk | I am confused: Do you look for an exact reformulation or an LP relaxation? | |
| Jul 7, 2012 at 13:37 | history | asked | Clark | CC BY-SA 3.0 |