0
$\begingroup$

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.

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

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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