n-term approximation

Summary

$n$-term approximation approximates a function or vector by a linear combination of at most $n$ elements. These elements are chosen freely from a fixed family, called a dictionary, such as a basis. The best error with $n$ terms, $\sigma_n(f)$, measures how well $f$ can be compressed with respect to that dictionary. The set of $n$-term combinations is not a linear space, so this is a basic model of nonlinear approximation. It underlies wavelet compression, sparse approximation and greedy algorithms such as matching pursuit.