Find the Sparse Representation in MATLAB - Basis Pursuit

Question

I have a dictionary(Matrix) D and an input(Vector) Y. Now I want to solve this problem:

What is the Sparse Representation of input Y according to dictionary D.

this problem is an important question in Sparsity field and solves with this optimization

or this

What is the best solution to solve this in matlab???

Note that the dictionary D is a matrix by n*d and input Y is vector by n, and we have both of them. epsilon and lambda are constant.

Answer 1

You should look under the LASSO or basis pursuit denoising or ISTA/FISTA.

See for example the following papers/books:

• "Atomic Decomposition by Basis Pursuit", Chen, Donoho and Saunders (SIAM Review Vol. 43,No. 1,pp. 129–159, 2001) [Example code here under BPD]
• "Regression Shrinkage and Selection via the Lasso", Tibshirani (J. R. Stat. Soc. B, 1996, vol 58, no. 1, pp. 267-288) [Implemented in MATLAB as lasso()]
• M. Elad, "Sparse and Redundant Representations", Springer, 2010 (Chapter 5)
• "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems", Beck and Teboulle, SIAM J. Imaging Sciences, vol 2, No 1, pp. 183-202. (Beck's website has some code somewhere)

There are many implementations on MATLAB Central and toolboxes which you can find with a simple google of the term. Alternatively, if the problem is small, you can try the code here (using CVX or otherwise). There is also the old l1magic package.

Here is also a list of some packages.

Answer 2

Note it firstly depends on your data. Is it only only vector or a batch.

There are efficient algorithms for batch processing like OMP or LARS etc.

Next as i mentioned it depends on how much sparse is your signal in dictionary.

1) If it is highly sparse any thresholding based algorithm should do fine. Even maching pursuit will also be ok e.g. OMP, OLS etc. These are fast and computationally efficient. Although you will not be solving L1 but the reconstruction will be equivalent.

2) In other cases you can use LARS-least angle regression based solver. C based fast matlab packages are avialble freely. YALL1-your algoritm for L1 package is also good. It can solbe various variations of sparse coding problems even group sparsity based problems.

If you can tell me what specific data or problem you are addressing, may be one can suggest more and better options.