Sparse approximation

Summary

Let $A$ be a matrix with more columns than rows and let $b$ be a vector. Sparse approximation looks for a vector $x$ with few nonzero entries such that $Ax$ is close to $b$. The columns of $A$ form a redundant dictionary, so $b$ has many representations, and one wants the sparsest. The exact problem is NP-hard in general. In practice one uses greedy methods such as matching pursuit, or convex relaxations such as basis pursuit and the Lasso. It is the core of signal compression, denoising and compressed sensing.