Find the Sparse Representation in MATLAB - Basis Pursuit 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.
 A: 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. 
A: 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.
A: There are 2 forms of the Basis Pursuit problem:
$$\begin{align*}
\text{The $ \lambda $ Form:} & \quad && \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \\
\text{The $ \epsilon$ Form:} && \quad & \arg \min_{x} {\left\| x \right\|}_{1} \\
& \text{subject to} &&  \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \leq \epsilon
\end{align*}$$
Both forms are equivalent.
When I say equivalence I mean:
$$ \forall \epsilon, \, \exists \lambda : x \left( \epsilon \right) = x \left( \lambda \right) $$
Namely by tweaking the value of $ \lambda $ you can always have the solution of one form match the other.
There are many modern and efficient solvers for the $ \lambda $ form.
You may have a look on my $ {L}_{1} $ Regularized Least Squares Solvers project for various solvers of the problem implemented in MATLAB.
In order to solve the $ \epsilon $ form utilizing $ \lambda $ solver you may have a look in my StackExchange Cross Validated Q291962 answer which also includes MATLAB code.
The basic idea is simple. Define a scalar function:
$$ f \left( \lambda \right) = \frac{1}{2} {\left\| A \hat{x} - b \right\|}_{2}^{2} - \epsilon $$
Where $ \hat{x} = \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} $.
Now just use any method to find the zero of $ f \left( \lambda \right) $ (For instance, use Bisection Method).  Since the function is non decresing monotonic in $ \lambda $ and negative for $ \lambda = $ and positive for $ \lambda \to \infty $ then a solution must exits and guaranteed to be found using simple methods.
