Sparse approximation

Sparse approximation (also known as sparse representation) theory deals with sparse solutions for systems of linear equations. Techniques for finding these solutions and exploiting them in applications have found wide use in image processing, signal processing, machine learning, medical imaging, and more.
Sparse decomposition.
Noiseless observations.
Consider a linear system of equations formula_1, where formula_2 is an underdetermined formula_3 matrix formula_4 and formula_5. The matrix formula_2 (typically assumed to be full-rank) is referred to as the dictionary, and formula_7 is a signal of interest. The core sparse representation problem is defined as the quest for the sparsest possible representation formula_8 satisfying formula_1. Due to the underdetermined nature of formula_2, this linear system admits in general infinitely many possible solutions, and among these we seek the one with the fewest non-zeros. Put formally, we solve 
where formula_12 is the formula_13 pseudo-norm, which counts the number of non-zero components of formula_8. This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in combinatorial optimization.
Sparsity of formula_8 implies that only a few (formula_16) components in it are non-zero. The underlying motivation for such a sparse decomposition is the desire to provide the simplest possible explanation of formula_7 as a linear combination of as few as possible columns from formula_2, also referred to as atoms. As such, the signal formula_7 can be viewed as a molecule composed of a few fundamental elements taken from formula_2.
While the above posed problem is indeed NP-Hard, its solution can often be found using approximation algorithms. One such option is a convex relaxation of the problem, obtained by using the formula_21-norm instead of formula_13, where formula_23 simply sums the absolute values of the entries in formula_8. This is known as the basis pursuit (BP) algorithm, which can be handled using any linear programming solver. An alternative approximation method is a greedy technique, such as the matching pursuit (MP), which finds the location of the non-zeros one at a time.
Surprisingly, under mild conditions on formula_2 (using the spark (mathematics), the mutual coherence or the restricted isometry property) and the level of sparsity in the solution, formula_26, the sparse representation problem can be shown to have a unique solution, and BP and MP are guaranteed to find it perfectly.
Noisy observations.
Often the observed signal formula_7 is noisy. By relaxing the equality constraint and imposing an formula_28-norm on the data-fitting term, the sparse decomposition problem becomes 
or put in a Lagrangian form, 
where formula_31 is replacing the formula_32.
Just as in the noiseless case, these two problems are NP-Hard in general, but can be approximated using pursuit algorithms. More specifically, changing the formula_13 to an formula_21-norm, we obtain 
which is known as the basis pursuit denoising. Similarly, matching pursuit can be used for approximating the solution of the above problems, finding the locations of the non-zeros one at a time until the error threshold is met. Here as well, theoretical guarantees suggest that BP and MP lead to nearly optimal solutions depending on the properties of formula_2 and the cardinality of the solution formula_26.
Another interesting theoretical result refers to the case in which formula_2 is unitary. Under this assumption, the problems posed above (with either formula_13 or formula_21) admit closed-form solutions in the form of non-linear shrinkage.
Variations.
There are several variations to the basic sparse approximation problem.
Structured sparsity: In the original version of the problem, any of the atoms in the dictionary can be picked. In the structured (block) sparsity model, instead of picking atoms individually, groups of them are to be picked. These groups can be overlapping and of varying size. The objective is to represent formula_7 such that it is sparse while forcing this block-structure.
Collaborative (joint) sparse coding: The original version of the problem is defined for a single signal formula_7. In the collaborative (joint) sparse coding model, a set of signals is available, each believed to emerge from (nearly) the same set of atoms from formula_2. In this case, the pursuit task aims to recover a set of sparse representations that best describe the data while forcing them to share the same (or close-by) support.
Other structures: More broadly, the sparse approximation problem can be cast while forcing a specific desired structure on the pattern of non-zero locations in formula_8. Two cases of interest that have been extensively studied are tree-based structure, and more generally, a Boltzmann distributed support.
Algorithms.
As already mentioned above, there are various approximation (also referred to as pursuit) algorithms that have been developed for addressing the sparse representation problem:
We mention below a few of these main methods.
Applications.
Sparse approximation ideas and algorithms have been extensively used in signal processing, image processing, machine learning, medical imaging, array processing, data mining, and more. In most of these applications, the unknown signal of interest is modeled as a sparse combination of a few atoms from a given dictionary, and this is used as the regularization of the problem. These problems are typically accompanied by a dictionary learning mechanism that aims to fit formula_2 to best match the model to the given data. The use of sparsity-inspired models has led to state-of-the-art results in a wide set of applications. Recent work suggests that there is a tight connection between sparse representation modeling and deep-learning.