Wikipedia / Sparse approximation
Wikipedia / 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 is an underdetermined matrix, 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
pseudo-norm, which counts the number. This problem is known to be NP-hard with a reduction to NP-complete subset selection problems in combinatorial optimization.
.
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. 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.
(using the spark (mathematics), the mutual coherence or the restricted isometry property, the sparse representation problem can be shown to have a unique solution, and BP and MP are guaranteed to find it perfectly.
Noisy observations
is noisy. By relaxing the equality constraint and imposing an \ell_2-norm on the data-fitting term, the sparse decomposition problem becomes
or put in a Lagrangian form,
.
-norm, we obtain
which is known as the basis pursuit denoising. Similarly, matching pursuit. is a unitary matrix) admit closed-form solutions in the form of non-linear shrinkage.
Variations
There are several variations to the basic sparse approximation problem.
Structured sparsity such that it is sparse while forcing this block-structure.
Collaborative (joint) sparse coding. 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. 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.
Matching pursuit), and then updating this residual to take the new atom and its coefficient into account. Matching pursuit might pick the same atom multiple times.
Orthogonal matching pursuit is very similar to matching pursuit, with one major difference: in each of the algorithm's step, all the non-zero coefficients are updated by a least squares. As a consequence, the residual is orthogonal to the already chosen atoms, and thus an atom cannot be picked more than once.
Stage-wise greedy methods: Improved variations over the above are algorithms that operate greedily while adding two critical features: (i) the ability to add groups of non-zeros at a time (instead of one non-zero per round); and (ii) including a pruning step in each round in which several of the atoms are discarded from the support. Representatives of this approach are the Subspace-Pursuit algorithm and the CoSaMP.
Basis pursuit-norm. Note that this only defines a new objective, while leaving open the question of the algorithm to use for getting the desired solution. Commonly considered such algorithms are the IRLS, LARS, and iterative soft-shrinkage methods.
There are several other methods for solving sparse decomposition problems: homotopy method, coordinate descent, iterative hard-thresholding, first order proximal methods, which are related to the above-mentioned iterative soft-shrinkage algorithms, and Dantzig selector.
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 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.