Sparse approximation

Sparse approximation is the problem of finding a signal or vector estimate with sparseness property, that is having a small number of nonzero elements, that satisfies (approximately) a system of equations.

For example, consider a linear system of equations y = Ax, where y \in \Real^{M}, A \in \Real^{M \times N}, x \in \Real^{N}, and M < N. In general, this problem is ill-posed as there are infinitely many x that solve this system.

One way to enforce sparsity is to require the 0-norm to be small, such as: \min_x \|x\|_0, such that y = A x. However, it is known that this problem is NP-complete.