Sparse approximation

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.

Sparse decomposition

Noiseless observations

Consider a linear system of equations $x = D\alpha$, where $D$ is an underdetermined $m\times p$ matrix $(m \ll p)$ and $x \in \mathbb{R}^m,\alpha \in \mathbb{R}^p$. $D$, called as the dictionary or the design matrix, is given. The problem is to estimate the signal $\alpha$, subject to the constraint that it is sparse. The underlying motivation for sparse decomposition problems is that even though the observed values are in high-dimensional $(m)$ space, the actual signal is organized in some lower-dimensional subspace $(k \ll m)$.

Sparsity implies that only a few components of $\alpha$ are non-zero and the rest are zero. This implies that $x$ can be decomposed as a linear combination of only a few $m\times 1$ vectors in $D$, called atoms. $D$ itself is over-complete $(m \ll p)$. Such vectors are called as the basis of $x$. However, unlike other dimensionality reducing decomposition techniques such as Principal Component Analysis, the basis vectors are not required to be orthogonal.

The sparse decomposition problem is represented as,

$\min_{\alpha \in \mathbb{R}^p} \|\alpha\|_0 \text{ such that } x = D\alpha,$

where $\|\alpha\|_0 = \#\{ i : \alpha_i \neq 0, \, i=1,\ldots,p \}$ is a pseudo-norm, $l_0$, which counts the number of non-zero components of $\alpha = [\alpha_1,\ldots,\alpha_p]^T$. This problem is NP-Hard with a reduction to NP-complete subset selection problems in combinatorial optimization. A convex relaxation of the problem can instead be obtained by taking the $l_1$ norm instead of the $l_0$ norm, where $\|\alpha\|_1 = \sum_{i=1}^p |\alpha_i|$. The $l_1$ norm induces sparsity under certain conditions.^[1]

Noisy observations

Often the observations $x$ are noisy. By imposing an $l_2$ norm on the data-fitting term and relaxing the equality constraint, the sparse decomposition problem is given by,

$\min_{\alpha \in \mathbb{R}^p} \frac{1}{2} \|x - D\alpha \|_2^2 + \lambda \|\alpha\|_1,$

where $\lambda$ is a slack variable and $\|\alpha\|_1$ is the sparsity-inducing term. The slack variable balances the trade-off between fitting the data perfectly, and employing a sparse solution.

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 $x$ such that it is sparse in the number of groups selected. Such groups appear naturally in many problems. For example, in object classification problems the atoms can represent images, and groups can represent category of objects.

Collaborative sparse coding

The original version of the problem is defined for only a single point $x$ and its noisy observation. Often, a single point can have more than one sparse representation with similar data fitting errors. In the collaborative sparse coding model, more than one observation of the same point is available. Hence, the data fitting error is defined as the sum of the $l_2$ norm for all points.

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 $l_0$ pseudo-norm problem. Matching pursuit works by finding a basis vector in $D$ that maximizes the correlation with the residual (initialized to $x$), and then recomputing the residual and coefficients by projecting the residual on all atoms in the dictionary using existing coefficients. Matching pursuit suffers from the drawback that an atom can be picked multiple times which is addressed in orthogonal matching pursuit.

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 $l_0$ norm.

LASSO

The LASSO method solves the $l_1$ norm version of the problem. In LASSO, instead of projecting the residual on some atom as in Matching Pursuit, the residual is moved by a small step in the direction of the atom iteratively.

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 $k$ vectors.^{[2] [3]} Because the projection can often be viewed as a thresholding operator, the described algorithm is also known as Iterative Thresholding algorithm. ^[4] The specific form of the thresholding operator is closely related to the chosen penalty function. For $\ell_0$ norm, the corresponding thresholding operator is known as hard thresholding. For $\ell_1$ norm, the corresponding thresholding operator is known as soft thresholding.

Other methods

There are several other methods for solving sparse decomposition problems^[5]

• Homotopy method
• Coordinate descent
• First order/proximal methods
• Dantzig selector^[6]

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.^[7] 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 ^[8] 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.

See also

• Compressed sensing
• Spectral estimation
• K-SVD

References

1. Donoho, D.L. (2006). "For most large underdetermined systems of linear equations the minimal l1-norm solution is also the sparsest solution" (PDF). Communications on pure and applied mathematics (Wiley Online Library) 56 (6): 797–829. doi:10.1002/cpa.20132.
2. Deanna Needell and Joel Tropp. "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples" (PDF).
3. Anastasios Kyrillidis and Volkan Cevher. "Recipes for hard thresholding methods".
4. Yu Wang, Jinshan Zeng, Zhimin Peng, Xiangyu Chang and Zongben Xu. "On Linear Convergence of Adaptively Iterative Thresholding Algorithms for Compressed Sensing".
5. Francis Bach, Julien Mairal, Jean Ponce and Guillermo Sapiro. "Sparse Coding and Dictionary Learning for Image Analysis" (PDF).
6. Candes, Emmanuel; Tao, Terence (2007). "The Dantzig selector: Statistical estimation when p is much larger than n". Annals of Statistics 35 (6): 2313–2351. arXiv:math/0506081. doi:10.1214/009053606000001523. MR 2382644.
7. Adiloglu, Kamil; Annies, Robert; Wahlen, Elio; Purwins, Hendrik; Obermayer, Klaus (2012). "A Graphical Representation and Dissimilarity Measure for Basic Everyday Sound Events". IEEE Journal of Selected Topics in Signal Processing 20 (5): 1542–1552. doi:10.1109/TASL.2012.2184752.
8. Scholler, Simon; Purwins, Hendrik (2011). "Sparse Approximations for Drum Sound Classification". IEEE Journal of Selected Topics in Signal Processing 5 (5): 933 – 940. doi:10.1109/JSTSP.2011.2161264.