ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

0. Plenary Lectures

1991 MS Classification: Primary 94A12; Secondary 41A25, 46E35, 62G05 Stéphane Mallat, Ecole Polytechnique, Paris, France and Courant Institute, New York, USA Applied Mathematics Meets Signal Processing

1. Beyond Fourier The Fourier transform has long ruled over signal processing, leaving little room for new challenging mathematics. Until the 70’s, signals were mostly speech and sounds, which are well modeled by Gaussian processes. As a result, linear algorithms could be considered optimal among all non-linear procedures. Adding a hypothesis of stationarity narrows down to the exclusive class of convolution operators, and these are diagonalized by the Fourier transform. The situation has completely changed with the development of image processing. Images are poorly modeled by Gaussian processes, and non-linear algorithms can considerably outperform linear procedures. This eye opener showed the importance of non-linear and non-stationary operators. Signal processing has become a new application area of modern mathematics, which takes its roots in approximation theory, harmonic analysis [5], non-linear PDE [3], probability and statistics [2]. It is the source of new developments in all these domains, and also an entry to the more complex issues of computational vision and perception [6].

2. Compressed Representations The solution of many signal processing problems requires finding a representation that efficiently compresses the signals and operators involved. Besides data compression, this holds for estimation and inverse problems, as well as pattern recognition. This lecture considers particular examples that are closely related to the recent development of the wavelet theory [1,4,5], while emphasizing a general approach to non-linear problems. 2.1 Image Compression Let us decompose an image f ∈ L^{2}(R^{2}) in an orthonormal basis B = {g_{m}}_{m}

f = ∑_{m} ⟨f, g_{m}⟩ g_{m} .  (1)

A compressed code is constructed by approximating the inner-product ⟨f, g_{m}⟩ by quantized values Q(⟨f, g_{m}⟩) that are coded with R bits. The restored signal f̃ = ∑_{m} Q(⟨f, g_{m}⟩) g_{m} has a distortion d(f, R) = ∥f − f̃∥_{L^{2}} that must be minimized. This distortion is closely related to the non-linear approximation error ϵ(f, T) = ∥f − f_{T} ∥_{L^{2}} when thresholding at T the inner products of f:

f_{T} = ∑_{|⟨f,g_{m}⟩|>T} ⟨f, g_{m}⟩ g_{m}.

For f in a ball of a Banach space H, one can prove [4] that the decay rate of ϵ(f, T) for T → ∞ is maximized by choosing an unconditional basis of H. The basis B is an unconditional basis of H if the norm ∥f∥_{H} for f ∈ H is equivalent to a quasi-norm on the modulus of inner products {|⟨f, g_{m}⟩|}_{m} [5]. Little prior information is known on most images, but they often belong to the BV space of bounded variation functions:

∥f∥_{BV} = ∫ |∇f(x)| dx < +∞.

This motivates the use of wavelet bases. There exists no unconditional basis in BV but wavelet bases are unconditional bases of Besov spaces that give a close embedding of BV. Wavelet image coders are currently the most efficient, but could be improved by explicitly taking into account geometric image properties. 2.2 Signal Restoration and Identification Recent techniques to compress vectors and operators allow one to reduce many non-linear estimation and restoration problems to simple thresholdings in appropriate bases. Suppose that a signal f ∈ H is contaminated by an additive noise which is a Gaussian white process W of variance σ^{2}. The measured signal is

Z = f + W.  (2)

Removing the noise consists in finding an operator L such that the estimation F = L(Z) of f reduces the expected risk r(f, σ) = E{∥f − F ∥_{L^{2}}^{2}}. One can prove that r(f, σ) is closely related to the non-linear approximation error ϵ(f, T) [2]. The maximum risk r(f, σ) for f in a ball of H is thus nearly minimized by thresholding the decomposition coefficients of Z in an unconditional basis of H. Applications to bounded variation images are shown. The next level of difficulty occurs when the measured signal is also degraded by an operator K

Z = Kf + W,  (3)

with an inverse K^{−1} than is not bounded on the range of K. Examples on blurred satellite images illustrate this case. We must now find a representation that compresses both f and K. If K K^{∗} = D T where D is diagonal in an unconditional basis of H and T is bounded with a bounded inverse then a nearly optimal estimator F = L(Z) is also calculated with a thresholding strategy in this basis. When f has bounded variation and K is a blurring convolution operator, such a basis is constructed with wavelet packets [4].

More difficult estimation problems occur when the observed signal is only a realization of an underlying non-stationary and non-parameterized process that must be identified. Image textures are one such example. One can then estimate the covariance operator of this process, in which case the signal is represented by an operator as opposed to a vector. Estimating the covariance operator from a single realization requires finding a basis where it’s matrix is nearly diagonal, thus reducing the number of coefficients to be estimated. Locally stationary processes are examples whose covariances are pseudo-differential operators, which are estimated by searching for bases in where the matrix is nearly diagonal. However, let us emphasize that image texture discrimination is still an open problem.

References

[1] I. Daubechies. Ten Lectures on Wavelets. SIAM, Philadelphia, PA, 1992.

[2] D. Donoho and I. Johnstone. Ideal spatial adaptation via wavelet shrinkage. Biometrika, 81:425–455, December 1994.

[3] L. Alvarez, F. Guichard, P. L. Lions and J. M. Morel. Axioms and fundamental equations of image processing. Archieve for Rational Mechanic, 123:199–257, 1993.

[4] S. Mallat. A Wavelet Tour of Signal Processing. Academic Press, Boston, MA, 1998.

[5] Y. Meyer. Wavelets and Operators. Advanced Mathematics. Cambridge University Press, 1992.

[6] D. Mumford. Mathematical Theories of Shape: Do they model perception? SPIE: Geometric Methods in Computer Vision, 1570:2–10, 1991.