# $\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has been spent looking for a representation different from the one above (formed as a linear/integer program). I know there are approximation methods (Basis Pursuit, Matching Pursuit, the $\ell_1$ problem), but I haven't found an exact formulation in any of my searching and sparse representation literature. I have developed a formulation for the problem, but I would love to compare with anything else that is available. Does anyone know of such a formulation?

P.S. I'm aware that the $\|x\|_0$ problem is NP-hard, and as such, probably will not yield an exact formulation as an LP (unless P=NP). I was more referring to an exact formulation or an LP relaxation.

-
I am confused: Do you look for an exact reformulation or an LP relaxation? –  Dirk Jul 7 '12 at 14:09
An exact formulation is my major goal, but I would be interested to see a relaxation as well. –  Clark Jul 7 '12 at 14:30
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$). –  Dirk Jul 7 '12 at 19:48
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. –  Clark Jul 7 '12 at 20:58
Sorry, what do you denote by $\|\dot\|_0$? –  Dima Pasechnik Jul 8 '12 at 6:36

You can formulate this as an integer program. Let z be a vector of binary variables, and let Uj be upper bounds on the x variables. Hopefully you can derive some reasonably tight lower bounds based on the constraints Ax = b, but if not, use a suitably large value for each Uj. Then the following MIP will give you the minimal support that satisfies Ax = b:

min e'z // e is a vector of all ones Ax = b xj = Uj*zj <= 0 x >= 0, 0 <= z <= 1, z binary.

Note that I assumed x >= 0 here. If some or all of the x variables have lower bounds below 0, you can introduce nonnegative variables u and v, then let x = u - v do the some MIP formulation for the constraints Au - Av = b, adding a binary for each u and v variable.

-