# Finding sparsest solution of a linear system

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.

• There has been a lot of work on these topics in the last few years -- Google 'l1 minimisation' and 'compressive sensing' to make a start on it ... – J.J. Green Dec 29 '14 at 15:15
• Some good heuristics go under the name "pursuit", e.g. (regularized) (orthogonal) matching pursuit or basis pursuit. – Dirk Dec 29 '14 at 18:00
• Search for: 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. – Suvrit Jan 27 '15 at 17:40

The literature denotes $D$ as the dictionary and $X$ as the sparse representation set and so it expresses a set of signals $Y$ as:
$$$Y \approx DX$$$
and ensures the quality of both the dictionary and the sparse representations with a sparsity constraint (such as the number of non-zero entries known as the $l_0$-norm) or a target error $\epsilon$.