A sparse approximation is a sparse vector that approximately solves a system of equations. Techniques for finding sparse approximations have found wide use in applications such as image processing, audio processing, biology, and document analysis.
Contents
Noiseless observations
Consider a linear system of equations
Sparsity implies that only a few (
The sparse decomposition problem is represented as,
where
Noisy observations
Often the observations
where
Variations
There are several variations to the basic sparse approximation problem.
Structured sparsity
In the original version of the problem, any atoms in the dictionary can be picked. In the structured (block) sparsity model, instead of picking atoms individually, groups of atoms are to be picked. These groups can be overlapping and of varying size. The objective is to represent
Collaborative sparse coding
The original version of the problem is defined for only a single point
Algorithms
There are several algorithms that have been developed for solving sparse approximation problem.
Matching pursuit
Matching pursuit is a greedy iterative algorithm for approximatively solving the original
Orthogonal matching pursuit
Orthogonal Matching Pursuit is similar to Matching Pursuit, except that an atom once picked, cannot be picked again. The algorithm maintains an active set of atoms already picked, and adds a new atom at each iteration. The residual is projected on to a linear combination of all atoms in the active set, so that an orthogonal updated residual is obtained. Both Matching Pursuit and Orthogonal Matching Pursuit use the
LASSO
The LASSO method solves the
Projected Gradient Descent
Projected Gradient Descent methods operate in a similar fashion with the Gradient Descent: the current gradient provides the information to point to new search directions. Since we are looking for a sparse solution, the putative solutions are projected onto the sparse scaffold of
Other methods
There are several other methods for solving sparse decomposition problems
Applications
Sparse approximation has been used in image processing, biology, document analysis, and audio analysis for representation, compression, and estimation.
Audio Analysis
In the audio domain, sparse approximation has been applied to the analysis of speech, environmental sounds, and music. For classification of everyday sound samples, Adiloglu et al. decomposed sounds in terms of a dictionary of Gammatone functions. Applying matching pursuit, they yielded a point pattern of time-frequency components. They then defined a dissimilarity of two sounds via a one-to-one correspondence between the most prominent atoms of two sounds. Scholler and Purwins have used sparse approximation for the classification of drum sounds based on atom counts resulting from a sparse approximation with a learned sound dictionary including the optimisation of the atom length.