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

-
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