0.4 Approximation

Nonlinear approximation

A related question often arises in settings involving signal dictionaries. Rather than finding the best approximation to asignal $f$ using a fixed collection of $K$ elements from the dictionary $\Psi$ , one may often seek the best $K$ -term representation to $f$ among all possible expansions that use $K$ terms from the dictionary. Compared to linear approximation, this type of nonlinearapproximation  [link] , [link] utilizes the ability of the dictionary to adapt: different elements may be important forrepresenting different signals.

The $K$ -term nonlinear approximation problem corresponds to the optimization

Measuring approximation quality

One common measure for the quality of a dictionary $\Psi$ in approximating a signal class is the fidelity of its $K$ -term representations. Often one examines theasymptotic rate of decay of the $K$ -term approximation error as $K$ grows large. Defining

Nonlinear approximation of piecewise smooth functions

Let $f\in {\mathcal{C}}^H$ be a 1-D function. Supposing the wavelet dictionary has more than $H$ vanishing moments, then $f$ can be well approximated using its $K$ largest coefficients (most of which are at coarse scales). As $K$ grows large, the nonlinear approximation error will decay We use the notation $f\left(\alpha \right)\lesssim g\left(\alpha \right)$ , or $f\left(\alpha \right)=O\left(g\right(\alpha \left)\right)$ , if there exists a constant $C$ , possibly large but not dependent on the argument $\alpha$ , such that $f\left(\alpha \right)\le Cg\left(\alpha \right)$ . as ${\sigma }_K{\left(f\right)}_2\lesssim K^{-H}$ .