# $\ell_0$ 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. 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.

• Is there a reason to define $supp$ first instead of directly defining $\:||\cdot||_0\:$? $\;\;$ – user57159 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.

• 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