Sparse Recovery Best Algorithms
Usually the classic problem is given by:

$$\begin{align*}
\arg \min_{x} \quad &amp; \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \\
\text{subject to} \quad &amp; {\left\| x \right\|}_{0} \leq k
\end{align*}$$

Where $ {\left\| \cdot \right\|}_{0} $ is the Cardinality Measure which counts the number of non zero elements in the argument.

The above is NP Hard problem which means we can only use Greedy / Approximation methods.  

Since can't talk about the optimal solver the question best isn't well defined.
Usually it can be defined only once you can say something about how close you need to be to the optimal solution. 

In the greedy set of algorithms the least computational demanding are those based on thresholding. Yet usually you'd use the OMP if not the LS-OMP.

On the approximation side, usually people replace the Pseudo Norm by $ {L}_{1} $. If this approximation is good for you then probably the Coordinate Descent method is the most efficient.

There is a great course on eDx - Sparse Representations in Signal and Image Processing: Fundamentals by Michael Elad which answers your exact question at on Section 3 Slides (See slide #25).