0.4 Approximation

To this point, we have discussed signal representations and models as basic tools for signal processing. In the following modules, we discuss the actual application of these tools to taskssuch as approximation and compression, and we continue to discuss the geometric implications.

Linear approximation

One common prototypical problem in signal processing is to find the best linear approximation to a signal $x$ . By “best linear approximation,” we mean the best approximation to $x$ from among a class of signals comprising a linear (or affine) subspace. Thissituation may arise, for example, when we have a noisy observation of a signal believed to obey a linear model. If we choose an ${\ell }_2$ error criterion, the solution to this optimization problem has a particularly strong geometric interpretation.

To be more concrete, suppose $S$ is a $K$ -dimensional linear subspace of ${\mathbb{R}}^N$ . (The case of an affine subspace follows similarly.) If we seek

The linear approximation problem arises frequently in settings involving signal dictionaries. In some settings, such as the caseof an oversampled bandlimited signal, certain coefficients in the vector $\alpha$ may be assumed to be fixed at zero. In the case where the dictionary $\Psi$ forms an orthonormal basis, the linear approximation estimate of the unknown coefficients has aparticularly simple form: rows of the matrix $A$ in [link] are obtained by selecting and transposing the columns of $\Psi$ whose expansion coefficients are unknown, andconsequently, the unknown coefficients can be estimated simply by taking the inner products of $x$ against the appropriate columns of $\Psi$ .

For example, in choosing a fixed subset of the Fourier or wavelet dictionaries, one may rightfully choose the lowest frequency(coarsest scale) basis functions for the set $S$ because, as discussed in Linear Models from Low-Dimensional Signal Models , the coefficients generally tend to decay at higher frequencies (finer scales). Forsmooth functions, this strategy is appropriate and effective; functions in Sobolev smoothness spaces are well-approximated usinglinear approximations from the Fourier or wavelet dictionaries [link] . For piecewise smooth functions, however, even the wavelet-domainlinear approximation strategy would miss out on significant coefficients at fine scales. Since the locations of suchcoefficients are unknown a priority, it is impossible to propose a linear wavelet-domain approximation scheme that couldsimultaneously capture all piecewise smooth signals. As an example, [link] (a) shows the linear approximation of the Cameraman test image obtained by keeping only the lowest-frequency scaling and wavelet coefficients. No high-frequency information is available to clearly represent features such as edges.