Finding sparsest solution of a linear system

Question

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.

Answer 1

I think you'll find attempts at solving this problem mostly in dictionary learning papers.

The most popular approach today is solving the double optimization problem of learning a dictionary and providing a "good" sparse representation by performing multiple iterations that make use of a sparse coding algorithm in the first part (such as matching pursuit (MP), orthogonal matching pursuit (OMP), subspace pursuit (SP) etc.) followed by a secondary stage where the dictionary is refined by using the resulting sparse representations.

The literature denotes $D$ as the dictionary and $X$ as the sparse representation set and so it expresses a set of signals $Y$ as:

$\begin{equation} Y \approx DX \end{equation}$

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

To get a fast hands-on start with researching or providing a solution to this problem I suggest you start with the toolbox from Rubinstein that uses OMP for representation and K-SVD for dictionary learning.