Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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. 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$.

P.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
Is there a reason to define $supp$ first instead of directly defining $\:||\cdot||_0\:$? $\;\;$ – Ricky Demer Jul 13 '12 at 4:27
@Demer: No, it was just for completeness I guess. – Clark Jul 13 '12 at 13:05

Consider the following two problems $$ \min:\|x\|_0 \text{ subject to } Ax = b \tag{P0} $$ $$ \min:\|x\|_1 \text{ subject to } Ax = b \tag{P1} $$ The theory of compressed assert that the optimal solution to the linear program $(P1)$ is an optimal solution to $(P0)$ i.e., the sparsest vector, given the following conditions on $A.$ Let $B = (b_{j,k})$ be an $n \times n$ orthogonal matrix (but not necessarily orthonormal). Let the coherence of $B$ denoted by $$\mu = \max_{j,k} | b_{j,k} |.$$ Let $A$ be the $m \times n$ matrix formed by taking any random $m$ rows of $B.$ If $m \in O(\mu^2 |s| \log n)$ then $(P1)$ is equivalent to $(P0).$ More in the papers referenced in the Wikipedia article on compressed sensing.

share|cite|improve this answer
Please note there are 2-3 other alternative formulations of the conditions (e.g. RIP property, random matrices with iid entries.) And also, I omitted many details. – user2468 Jul 13 '12 at 17:58
Thanks J.D. I have looked at the $\ell_1$ problem, but I feel as though it's more of a special case, than an exact formulation. The $\ell_0$ problem gives the exact solution, and under these special circumstances (RIP, Gaussian elements, etc.) the $\ell_1$ gives similar results. I was more interested to see if there were any mixed-integer/combinatorial formulations. – Clark Jul 13 '12 at 22:57
@Clark under those circumstances it not only gives similar results, it is provably $\ell_0$ minimal – Tim Seguine Jan 20 '13 at 14:39

the problem can be modeled by an integer formulation: introduce binary variables y and implications $x > 0 \longrightarrow y = 1$ (for example with $M$ constraints $x\le My$). Then minimize the sum of y

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.