Sparse Recovery Best Algorithms

Question

In the big data era, in order to control the cost, complexity, and bandwidth of collecting and processing high-dimensional data systems, it is critical to exploit models that encapsulate prior information regarding the signals of interest The compresive sensing is a new signal processing technique which may use it instead of nyquist sampling theoreme, it's about sensing and compressing in the same time.

Compresed sensing has many applications indcluding MRI, RADARS,..this new technique rely on sparsity of the signal of interest.

In addition of sensing and compressing signal we need to reconstrut the signal when we would like to apply some process.., for this reason there are several algorithms that can be classified into 3 types: *Optimization Methodes *Greedy Methods *Thresholding-Based Methods Till here it's okay

my questions are : What is(are) the most efficient recovery algorithms ? What are the metrics used to define performance of a recovery algorithm ?

Answer 1

Usually the classic problem is given by:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \\ \text{subject to} \quad & {\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).