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.

  • 5
    $\begingroup$ 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 ... $\endgroup$
    – J.J. Green
    Dec 29 '14 at 15:15
  • 3
    $\begingroup$ Some good heuristics go under the name "pursuit", e.g. (regularized) (orthogonal) matching pursuit or basis pursuit. $\endgroup$
    – Dirk
    Dec 29 '14 at 18:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – Suvrit
    Jan 27 '15 at 17:40

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.