I want to find the solution with most zero-components for the following problem:

$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional constraints.

It's a known fact that it's NP-Complete. So I want to find

1) a heuristic for it, or

2) another NP-Complete Problem to reduce the following problem (in order to apply the heuristics known for the second problem and then go back to the original one).

I've been thinking about some intuitive or expectable properties of the sparse solutions but have not yet proved any. So I prefer editing once I am sure about them. I've identified the $2^n$ subproblems of choosing a subset of $\{1,...,n\}$ (set of indexes for variables who will be 0) and finding $x$, i.e. $\left \| Ax-b \right \|_{2}^{2}\leq \varepsilon $, and that in finding a sparse solution it is equivalent to fix a component to zero and to put the column in $A$ with the zame index to a zero-vector. Have been thinking this would be an initial step towards finding an appropriate heuristic or reduction (for example, by taking the categories of problems with the same cardinality of the subset chosen).

I would appreciate some help of your part.

Iterative Hard Thresholding--- that works as a reasonable heuristic (with some guarantees under compressed sensing style assumptions); in any case, something that you can code up in 3 lines of Matlab. $\endgroup$ – Suvrit Jan 27 '15 at 17:40