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.

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

...
Wikipedia