MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

Thanks in advance, Clark

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.

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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