1
$\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. 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.

  • 0
    @Demer: No, it was just for completeness I guess.2012-07-13

2 Answers 2

1

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.

  • 0
    @Clark under those circumstances it not only gives similar results, it is provably $\ell_0$ minimal2013-01-20
-1

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