0.3 Approximation and processing in bases

Analog-to-digital signal conversion is the first step of digital signal processing. Chapter 3 explains that it amounts toprojecting the signal over a basis of an approximation space. Most often, the resultingdigital representation remains much too large and needs to be further reduced. A digital image typically includes more than ${10}^6$ samples and a CD music recording has $40\times {10}^3$ samples per second. Sparse representations that reduce the number of parameters can beobtained by thresholding coefficients in an appropriate orthogonal basis. Efficient compression and noise-reduction algorithms are then implementedwith simple operators in this basis.

Stochastic versus deterministic signal models

A representation is optimized relative to a signal class, corresponding to all potential signals encountered in an application.This requires building signal models that carry available prior information.

A signal $f$ can be modeled as a realization of a random process $F$ , the probability distribution of which is known a priori. A Bayesian approach thentries to minimize the expected approximation error. Linear approximations are simpler because they onlydepend on the covariance. Chapter 9 shows that optimal linearapproximations are obtained on the basis of principal components that are the eigenvectorsof the covariance matrix. However, the expected errorof nonlinear approximations depends on the full probability distribution of $F$ . This distribution is most often not known forcomplex signals, such as images or sounds, because their transient structuresare not adequately modeled as realizations of known processes such as Gaussian ones.

To optimize nonlinear representations, weaker but sufficiently powerful deterministic models can be elaborated.A deterministic model specifies a set Θ , where the signal belongs. This set is defined by any prior information—for example, on thetime-frequency localization of transients in musical recordings or on the geometric regularity of edges in images.Simple models can also define Θ as a ball in a functional space, with a specific regularity norm such as a total variation norm.A stochastic model is richer because it provides the probability distribution in Θ . When this distribution is not available,the average error cannot be calculated and is replaced by the maximum error over Θ . Optimizing the representation then amounts to mini-mizing this maximum error, which is called a minimax optimization.

Sampling with linear approximations

Analog-to-digital signal conversion is most often implemented with a linear approximationoperator that filters and samples the input analog signal. From these samples, a linear digital-to-analog converter recovers a projection of the originalanalog signal over an approximation space whose dimension depends on the sampling density.Linear approximations project signals in spaces of lowest possible dimensions to reduce computations and storage cost, while controlling theresulting error.