Celebratio Mathematica — Daubechies

[1] I. Daubechies: “An application of hyperdifferential operators to holomorphic quantization,” Lett. Math. Phys. 2 : 6 (1977–1978), pp. 459–469. MR 513112 Zbl 0446.35082 article

[2] D. Aerts and I. Daubechies: “About the structure-preserving maps of a quantum mechanical propositional system,” Helv. Phys. Acta 51 : 5–6 (1978), pp. 637–660. MR 542797 article

[3] D. Aerts and I. Daubechies: “Physical justification for using the tensor product to describe two quantum systems as one joint system,” Helv. Phys. Acta 51 : 5–6 (1978), pp. 661–675. MR 542798 article

[4] D. Aerts and I. Daubechies: “A characterization of subsystems in physics,” Lett. Math. Phys. 3 : 1 (1979), pp. 11–17. MR 527173 Zbl 0451.03025 article

[5] D. Aerts and I. Daubechies: “A mathematical condition for a sublattice of a propositional system to represent a physical subsystem, with a physical interpretation,” Lett. Math. Phys. 3 : 1 (1979), pp. 19–27. MR 527174 Zbl 0451.03026 article

[6] D. Aerts and I. Daubechies: “A connection between propositional systems in Hilbert spaces and von Neumann algebras,” Helv. Phys. Acta 52 : 2 (1979), pp. 184–199. MR 553688 article

[7] I. C. Daubechies: Representation of quantum mechanical operators by kernels on Hilbert spaces of analytic functions. Ph.D. thesis, Vrije Universiteit Brussel, 1980. Advised by J. Reignier and A. Grossmann. phdthesis

Jean Reignier	Related
Alexander Grossmann	Related

[8] I. Daubechies: Weylkwantisatie bestudeerd langs de koherente toestanden om [Weyl quantization studied along the coherent states], 1980. Contest for Traveling Fellowships of the Belgian Government, 1980. misc

[9] I. Daubechies: “Coherent states and projective representation of the linear canonical transformations,” J. Math. Phys. 21 : 6 (1980), pp. 1377–1389. MR 574700 Zbl 0453.22012 article

[10] I. Daubechies and A. Grossmann: “An integral transform related to quantization,” J. Math. Phys. 21 : 8 (1980), pp. 2080–2090. MR 579204 article

[11] I. Daubechies: “On the distributions corresponding to bounded operators in the Weyl quantization,” Comm. Math. Phys. 75 : 3 (1980), pp. 229–238. MR 581947 Zbl 0451.47059 article

[12] J. R. Klauder and I. Daubechies: “Measures for path integrals,” Phys. Rev. Lett. 48 : 3 (1982), pp. 117–120. MR 639863 article

[13] I. Daubechies and J. R. Klauder: “Constructing measures for path integrals,” J. Math. Phys. 23 : 10 (1982), pp. 1806–1822. MR 676020 article

[14] J. R. Klauder and I. Daubechies: “Wiener measures for quantum mechanical path integrals,” pp. 245–247 in Stochastic processes in quantum theory and statistical physics (Marseille, France, 29 June–4 July 1981). Edited by S. Albeverio, P. Combe, and M. Sirugue-Collin. Lecture Notes in Physics 173. Springer (Berlin), 1982. Zbl 0496.60066 incollection

Sergio Angelo Albeverio	Related
Philippe Combe	Related
Madeleine Sirugue-Collin	Related
John Rider Klauder	Related

[15] I. Daubechies, A. Grossmann, and J. Reignier: “An integral transform related to quantization, II: Some mathematical properties,” J. Math. Phys. 24 : 2 (1983), pp. 239–254. MR 692298 article

Jean Reignier	Related
Alexander Grossmann	Related

[16] I. Daubechies and J. R. Klauder: “Measures for more quadratic path integrals,” Lett. Math. Phys. 7 : 3 (1983), pp. 229–234. MR 706212 Zbl 0521.60078 article

[17] I. Daubechies: “Continuity statements and counterintuitive examples in connection with Weyl quantization,” J. Math. Phys. 24 : 6 (1983), pp. 1453–1461. MR 708664 Zbl 0541.44001 article

[18] I. Daubechies and E. H. Lieb: “One-electron relativistic molecules with Coulomb interaction,” Comm. Math. Phys. 90 : 4 (1983), pp. 497–510. MR 719430 Zbl 0946.81522 article

As an approximation to a relativistic one-electron molecule, we study the operator \[ H = (-\Delta + m^2)^{1/2} - e^2\sum_{j=1}^K Z_j|x-R_j|^{-1} \] with \( Z_j\geq 0 \), \( e^{-2} = 137.04 \). \( H \) is bounded below if and only if \[ e^2Z_j \leq \frac{2}{\pi} ,\] all \( j \). Assuming this condition, the system is unstable when \[ e^2\sum Z_j > \frac{2}{\pi} \] in the sense that \[ E_0 = \inf\operatorname{spec}(H)\to -\infty \] as the \( R_j\to 0 \), all \( j \). We prove that the nuclear Coulomb repulsion more than restores stability; namely \[ E_0+0.069\,e^2\sum_{i < j}Z_iZ_j\,|R_i-R_j|^{-1} \geq 0 .\] We also show that \( E_0 \) is an increasing function of the internuclear distances \( |R_i-R_j| \).

[19] I. Daubechies: “An uncertainty principle for fermions with generalized kinetic energy,” Comm. Math. Phys. 90 : 4 (December 1983), pp. 511–520. MR 719431 Zbl 0946.81521 article

[20] D. Aerts and I. Daubechies: “Simple proof that the structure preserving maps between quantum mechanical propositional systems conserve the angles,” Helv. Phys. Acta 56 : 6 (1983), pp. 1187–1190. MR 734581 article

[21] I. Daubechies: Weylkwantisatie bestudeerd via een integraaltransformatie met behulp van het koherentetoestanden-formalisme [Weyl quantization studied via an integral transformation using the coherent state formalism], 1984. Paper awarded the 1984 Louis Empain Prize (Belgium) for Physics, 1984. misc

[22] I. Daubechies and J. R. Klauder: “Quantum-mechanical path integrals with Wiener measure for all polynomials Hamiltonians,” Phys. Rev. Lett. 52 : 14 (1984), pp. 1161–1164. Part II was published in J. Math. Phys 26 (1985). MR 736821 article

[23] I. Daubechies: “One-electron molecules with relativistic kinetic energy: Properties of the discrete spectrum,” Comm. Math. Phys. 94 : 4 (1984), pp. 523–535. MR 763750 article

[24] I. Daubechies and E. H. Lieb: “Relativistic molecules with Coulomb interaction,” pp. 143–148 in Differential equations (Birmingham, AL, 21–26 March 1983). Edited by I. W. Knowles and R. T. Lewis. North-Holland Mathematics Studies 92. North-Holland (Amsterdam), 1984. MR 799344 Zbl 0565.35101 incollection

Ian Walker Knowles	Related
Elliott Hershel Lieb	Related
Roger Timothy Lewis	Related

[25] I. Daubechies and J. R. Klauder: “Quantum-mechanical path integrals with Wiener measure for all polynomials Hamiltonians, II,” J. Math. Phys. 26 (1985), pp. 2239–2256. Part I was published in Phys. Rev. Lett. 52:14 (1984). MR 801118 Zbl 0979.81517 article

The coherent-state representation of quantum-mechanical propagators as well-defined phase-space path integrals involving Wiener measure on continuous phase-space paths in the limit that the diffusion constant diverges is formulated and proved. This construction covers a wide class of self-adjoint Hamiltonians, including all those which are polynomials in the Heisenberg operators; in fact, this method also applies to maximal symmetric Hamiltonians that do not possess a self-adjoint extension. This construction also leads to a natural covariance of the path integral under canonical transformations. An entirely parallel discussion for spin variables leads to the representation of the propagator for an arbitrary spin-operator Hamiltonian as well-defined path integrals involving Wiener measure on the unit sphere, again in the limit that the diffusion constant diverges.

[26] I. Daubechies, A. Grossmann, and Y. Meyer: “Painless nonorthogonal expansions,” J. Math. Phys. 27 (1986), pp. 1271–1283. MR 836025 Zbl 0608.46014 article

In a Hilbert space \( \mathscr{H} \), discrete families of vectors \( \{h_j\} \) with the property that \[ f = \sum_j\langle h_j | f\rangle\,h_j \] for every \( f \) in \( \mathscr{H} \) are considered. This expansion formula is obviously true if the family is an orthonormal basis of \( \mathscr{H} \), but also can hold in situations where the \( h_j \) are not mutually orthogonal and are “overcomplete.” The two classes of examples studied here are

appropriate sets of Weyl–Heisenberg coherent states, based on certain (non-Gaussian) fiducial vectors, and
analogous families of affine coherent states.

It is believed, that such “quasiorthogonal expansions” will be a useful tool in many areas of theoretical physics and applied mathematics.

Yves F. Meyer	Related
Alexander Grossmann	Related

[27] I. Daubechies and J. R. Klauder: “True measures for real time path integrals,” pp. 425–432 in Path integrals from meV to MeV (Bielefeld, Germany, 5–9 August 1985). Edited by M. C. Gutzwiller, A. Inomata, J. R. Klauder, and L. Streit. Bielefeld Encounters in Physics and Mathematics 7. World Scientific (Singapore), 1986. MR 859247 incollection

John Rider Klauder	Related
Martin Charles Gutzwiller	Related
Akira Inomata	Related
Ludwig Streit	Related

[28] I. Daubechies and T. Paul: “Wavelets: Some applications,” pp. 675–686 in VIII international congress on mathematical physics (Marseille, France, 16–26 July 1987). Edited by M. Mebkhout and R. Sénéor. World Scientific (Singapore), 1987. incollection

Roland Sénéor	Related
Thierry Paul	Related
Mohammed Mebkhout	Related

[29] I. Daubechies: “Discrete sets of coherent states and their use in signal analysis,” pp. 73–82 in Differential equations and mathematical physics (Birmingham, AL, 3–8 March 1986). Edited by I. W. Knowles and Y. Saito. Lecture Notes in Mathematics 1285. 1987. MR 921254 Zbl 0648.41017 incollection

Yoshimi Saitō	Related
Ian Walker Knowles	Related

[30] I. Daubechies, J. R. Klauder, and T. Paul: “Wiener measures for path integrals with affine kinematic variables,” J. Math. Phys. 28 (1987), pp. 85–102. Zbl 0615.58008 article

Thierry Paul	Related
John Rider Klauder	Related

[31] I. Daubechies and A. Grossmann: “Frames in the Bargmann space of entire functions,” Commun. Pure Appl. Math. 41 : 2 (1988), pp. 151–164. MR 924682 Zbl 0632.30049 article

We look at the decomposition of arbitrary \( f \) in \( L^2(R) \) in terms of the family of functions \[ \phi_{mn}(x) = \pi^{-1/4}\exp\bigl\{-\tfrac{1}{2}imnab + i\max - \tfrac{1}{2}(x-nb)^2\bigr\} ,\] with \( a,b > 0 \). We derive bounds and explicit formulas for the minimal expansion coefficients in the case where \( ab = 2\pi/N \), \( N \) an integer \( \geq 2 \). Transported to the Hilbert space \( F \) of entire functions introduced by V. Bargmann, these results are expressed as inequalities of the form \[ \mathbf{m}\|f\|^2 \leqq \sum_{m,n\in\mathbb{Z}} |f(z_{mn})|^2\exp\bigl\{-\tfrac{1}{2}|z_{mn}|^2\bigr\} \leqq \mathbf{M}\|f\|^2, \] where \( z_{mn} = ma + inb \), \( \mathbf{m} \), \( \textbf{M} > 0 \), and \( \|\cdot\| \) is the norm in \( F \), \[ \|f\|^2 = (2\pi)^{-1}\iint_{\mathbb{R}^2}dx\,dy\,|f(x+iy)|^2\exp\bigl\{-\tfrac{1}{2}(x^2 + y^2)\bigr\}. \] We conjecture that these inequalities remain true for all \( a,b \) such that \( ab < 2\pi \).

[32] I. Daubechies: “Orthonormal bases of compactly supported wavelets,” Commun. Pure Appl. Math. 41 : 7 (October 1988), pp. 909–996. Part II was published in Siam J. Math. Anal. 24:2 (1993), as was Part III. MR 951745 Zbl 0644.42026 article

[33] I. Daubechies and T. Paul: “Time-frequency localisation operators–a geometric phase space approach, II: The use of dilations,” Inverse Probl. 4 : 3 (1988), pp. 661–680. Part I was published in IEEE Trans. Inf. Theory 34:4 (1988). MR 965642 Zbl 0701.42004 article

[34] I. Daubechies: “Time-frequency localization operators: A geometric phase space approach,” IEEE Trans. Inf. Theory 34 : 4 (1988), pp. 605–612. Part II was published in Inverse Probl. 4:3 (1988). MR 966733 Zbl 0672.42007 article

The author defines a set of operators which localize in both time and frequency. These operators are similar to but different from the low-pass time-limiting operator, the singular functions of which are the prolate spheroidal wave functions. The author’s construction differs from the usual approach in that she treats the time-frequency plane as one geometric whole (phase space) rather than as two separate spaces. For disk-shaped or ellipse-shaped domains in time-frequency plane, the associated localization operators are remarkably simple. Their eigenfunctions are Hermite functions, and the corresponding eigenvalues are given by simple explicit formulas involving the incomplete gamma functions.

[35] I. Daubechies: “Wavelets: A tool for time-frequency analysis,” pp. 98 in Sixth multidimensional signal processing workshop (Pacific Grove, CA, 6–8 September 1989). IEEE (Piscataway, NJ), 1989. Abstract only. incollection

In the simplest case, a family wavelets is generated by dilating and translating a single function of one variable: \[ h_{a,b}(x) = |a|^{-1/2}h\Bigl(\frac{x-b}{a}\Bigr) .\] The parameters \( a \) and \( b \) may vary continuously, or be restricted to a discrete lattice of values \[ a = a_0^n, \quad b = na_0^mb_0 .\] If the dilation and translation steps \( a_0 \) and \( b_0 \) are not too large, then any \( L^2 \)-function can be completely characterized by its inner products with the elements of such a discrete lattice of wavelets. Moreover, one can construct numerically stable algorithms for the reconstruction of a function from these inner products (the “wavelet coefficients”). For special choices of the wavelet \( h \) decomposition and reconstruction can be done very fast, via a tree algorithm. The wavelet coefficients of a function give a time-frequency decomposition of the function, with higher time resolution for high-frequency than for low-frequency components.

[36] I. Daubechies: “Orthogonal bases of wavelets with finite support: Connection with discrete filters,” pp. 38–66 in Wavelets: Time-frequency methods and phase space (Marseille, France, 14–18 December 1987). Edited by J.-M. Combes, A. Grossmann, and P. Tchamitchian. Springer (Berlin), 1989. Zbl 0850.42013 incollection

Philippe Tchamitchian	Related
Jean-Michel Combes	Related
Alexander Grossmann	Related

[37] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies: “Image coding using vector quantization in the wavelet transform domain,” pp. 2297–2300 in International conference on acoustics, speech, and signal processing (Albuquerque, NM, 3–6 April 1990), vol. 4. IEEE (Piscataway, NJ), 1990. incollection

A two-step scheme for image compression that takes into account psychovisual features in space and frequency domains is proposed. A wavelet transform is first used in order to obtain a set of orthonormal subclasses of images; the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains the number of pixels required to describe the image at a constant. Second, according to Shannon’s rate-distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise-shaping bit-allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. The wavelet transform is particularly well adapted to progressive transmission.

Pierre Mathieu	Related
Michel Barlaud	Related
Marc Antonini	Related

[38] I. Daubechies: “The wavelet transform, time-frequency localization and signal analysis,” IEEE Trans. Inf. Theory 36 : 5 (1990), pp. 961–1005. MR 1066587 Zbl 0738.94004 article

Two different procedures for effecting a frequency analysis of a time-dependent signal locally in time are studied. The first procedure is the short-time or windowed Fourier transform; the second is the wavelet transform, in which high-frequency components are studied with sharper time resolution than low-frequency components. The similarities and the differences between these two methods are discussed. For both schemes a detailed study is made of the reconstruction method and its stability as a function of the chosen time-frequency density. Finally, the notion of time-frequency localization is made precise, within this framework, by two localization theorems.

[39] I. Daubechies: “The wavelet transform: A method for time-frequency localization,” Chapter 8, pp. 366–417 in Advances in Spectrum Analysis and Array Processing, vol. 1. Edited by S. S. Haykin. Prentice-Hall Signal Processing Series. Prentice-Hall (Englewood Cliffs, NJ), 1991. incollection

[40] I. Daubechies, S. Jaffard, and J.-L. Journé: “A simple Wilson orthonormal basis with exponential decay,” SIAM J. Math. Anal. 22 : 2 (1991), pp. 554–572. An erratum to this article was published in SIAM J. Math. Anal. 22:3 (1991). MR 1084973 Zbl 0754.46016 article

Following a basic idea of Wilson [“Generalized Wannier functions”, preprint] orthonormal bases for \( L^2(\mathbb{R}) \) which are a variation on the Gabor scheme are constructed. More precisely, \( \phi \in L^2(\mathbb{R}) \) is constructed such that the \( \psi_{ln} \), \( l\in\mathbb{N} \), \( n\in\mathbb{Z} \), defined by \begin{align*} \psi_{0n} (x) &= \phi (x - n), \\ \psi_{ln} (x) &= \begin{cases} \sqrt 2\,\phi \bigl(x - n/2\bigr)\cos (2\pi lx) & l \ne 0,\ l+n \in 2\mathbb{Z}, \\ \sqrt 2\,\phi\bigl(x - n/2\bigr) \sin (2\pi lx) & l \ne 0,\ l+n \in 2\mathbb{Z}{+}1, \end{cases} \end{align*} constitute an orthonormal basis. Explicit examples are given in which both \( \phi \) and its Fourier transform \( \hat{\phi} \) have exponential decay. In the examples \( \phi \) is constructed as an infinite superposition of modulated Gaussians, with coefficients that decrease exponentially fast. It is believed that such orthonormal bases could be useful in many contexts where lattices of modulated Gaussian functions are now used.

Jean-Lin Journé	Related
Stéphane Jaffard	Related

[41] I. Daubechies, S. Jaffard, and J.-L. Journé: “Erratum: A simple Wilson orthonormal basis with exponential decay,” SIAM J. Math. Anal. 22 : 3 (1991), pp. 878. Erratum to article published in SIAM J. Math. Anal. 22:2 (1991). MR 1101314 Zbl 0794.46008 article

Jean-Lin Journé	Related
Stéphane Jaffard	Related

[42] I. Daubechies: “Phase space path integrals, coherent states and Wiener measure,” pp. 157–176 in Proceedings of the joint Concordia–Sherbrooke seminar series on functional integration methods in stochastic quantum mechanics (Sherbrooke and Montréal, QC, 18 September–4 December 1987). Supplemento Rendiconti del Circolo Matematico di Palermo, II. Serie 25 25. Circolo Matematico di Palermo, 1991. MR 1108242 Zbl 0731.60107 incollection

[43] I. Daubechies and J. C. Lagarias: “Two-scale difference equations, I: Existence and global regularity of solutions,” SIAM J. Math. Anal. 22 : 5 (1991), pp. 1388–1410. MR 1112515 Zbl 0763.42018 article

A two-scale difference equation is a functional equation of the form \[ f(x) = \sum_{n=0}^N c_n f(\alpha x - \beta_n) ,\] where \( \alpha > 1 \) and \( \beta_0 < \beta_1 < \cdots < \mbox{} \) \( \beta_n \), are real constants, and \( c_n \) are complex constants. Solutions of such equations arise in spline theory, in interpolation schemes for constructing curves, in constructing wavelets of compact support, in constructing fractals, and in probability theory. This paper studies the existence and uniqueness of \( L^1 \)-solutions to such equations. In particular, it characterizes \( L^1 \)-solutions having compact support. A time-domain method is introduced for studying the special case of such equations where \( \{\alpha,\beta_0,\dots \), \( \beta_n\} \) are integers, which are called lattice two-scale difference equations. It is shown that if a lattice two-scale difference equation has a compactly supported solution in \( C^m(\mathbb{R}) \), then \[ m < \frac{\beta_n - \beta_0}{\alpha - 1} - 1 .\]

[44] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies: “Image coding using wavelet transform,” IEEE Trans. Image Proc. 1 : 2 (April 1992), pp. 205–220. article

A scheme for image compression that takes into account psychovisual features both in the space and frequency domains is proposed. This method involves two steps. First, a wavelet transform used in order to obtain a set of biorthogonal subclasses of images: the original image is decomposed at different scales using a pyramidal algorithm architecture. The decomposition is along the vertical and horizontal directions and maintains constant the number of pixels required to describe the image. Second, according to Shannon’s rate distortion theory, the wavelet coefficients are vector quantized using a multiresolution codebook. To encode the wavelet coefficients, a noise shaping bit allocation procedure which assumes that details at high resolution are less visible to the human eye is proposed. In order to allow the receiver to recognize a picture as quickly as possible at minimum cost, a progressive transmission scheme is presented. It is shown that the wavelet transform is particularly well adapted to progressive transmission.

Pierre Mathieu	Related
Michel Barlaud	Related
Marc Antonini	Related

[45] I. Daubechies and J. R. Klauder: “Squeezed states and path integrals,” pp. 247–259 in Workshop on squeezed states and uncertainty relations (College Park, MD, 28–30 March 1991). Edited by D. Han, Y. S. Kim, and W. W. Zachary. NASA Conference Publications 3135. NASA (Washington, DC), 1992. incollection

Daesoo Han	Related
Young Suh Kim	Related
Woodford W. Zachary	Related
John Rider Klauder	Related

[46] I. Daubechies and J. C. Lagarias: “Sets of matrices all infinite products of which converge,” Linear Algebra Appl. 161 (January 1992), pp. 227–263. A corrigendum/addendum to this article was published in Linear Algebra Appl. 327:1–3 (2007). MR 1142737 Zbl 0746.15015 article

An infinite product \[ \prod_{i=1}^{\infty}\mathrm{M}_i \] of matrices converges (on the right) if \[ \lim_{i\to\infty}\mathrm{M}_1\cdots\mathrm{M}_i \] exists. A set \[ \Sigma = \{\mathrm{A}_i:i\geq 1\} \] of \( n{\times}n \) matrices is called an RCP set (right-convergent product set) if all infinite products with each element drawn from \( \Sigma \) converge. Such sets of matrices arise in constructing self-similar objects like von Koch’s snowflake curve, in various interpolation schemes, in constructing wavelets of compact support, and in studying nonhomogeneous Markov chains. This paper gives necessary conditions and also some sufficient conditions for a set \( \Sigma \) to be an RCP set. These are conditions on the eigenvalues and left eigenspaces of matrices in \( \Sigma \) and finite products of these matrices. Necessary and sufficient conditions are given for a finite set \( \Sigma \) to be an RCP set having a limit function \[ \mathrm{M}_{\Sigma}(\mathbf{d}) = \prod_{i=1}^{\infty}\mathrm{A}_{d_i} ,\] where \( \mathbf{d} = (d_1, \dots, d_n,\dots) \), which is a continuous function on the space of all sequences \( \mathrm{d} \) with the sequence topology. Finite RCP sets of column-stochastic matrices are completely characterized. Some results are given on the problem of algorithmically deciding if a given set \( \Sigma \) is an RCP set.

[47] I. Daubechies: Ten lectures on wavelets. CBMS-NSF Regional Conference Series in Applied Mathematics 61. SIAM (Philadelphia), 1992. A Russian translation was published in 2001. MR 1162107 Zbl 0776.42018 book

[48] A. Cohen, I. Daubechies, and J.-C. Feauveau: “Biorthogonal bases of compactly supported wavelets,” Commun. Pure Appl. Math. 45 : 5 (1992), pp. 485–560. MR 1162365 Zbl 0776.42020 article

Orthonormal bases of compactly supported wavelet bases correspond to subband coding schemes with exact reconstruction in which the analysis and synthesis filters coincide. We show here that under fairly general conditions, exact reconstruction schemes with synthesis filters different from the analysis filters give rise to two dual Riesz bases of compactly supported wavelets. We give necessary and sufficient conditions for biorthogonality of the corresponding scaling functions, and we present a sufficient conditions for the decay of their Fourier transforms. We study the regularity of these biorthogonal bases. We provide several families of examples, all symmetric (corresponding to “linear phase” filters). In particular we can construct symmetric biorthogonal wavelet bases with arbitraily high preassigned regularity; we also show how to construct symmetric biorthogonal wavelet bases “close” to a (nonsymmetric) orthonormal basis.

Albert Cohen	Related
Jean-Christophe Feauveau	Related

[49] I. Daubechies and J. C. Lagarias: “Two-scale difference equations, II: Local regularity, infinite products of matrices, and fractals,” SIAM J. Math. Anal. 23 : 4 (1992), pp. 1031–1079. MR 1166574 Zbl 0788.42013 article

This paper studies solutions of the functional equation \[ f(x) = \sum_{n=0}^N c_n f(kx-n), \] where \( k\geqq 2 \) is an integer, and \[ \sum_{n=0}^N c_n = k .\] Part I showed that equations of this type have at most one \( L^1 \)-solution up to a multiplicative constant, which necessarily has compact support in \( [0 \), \( N/k-1] \). This paper gives a time-domain representation for such a function \( f(x) \) (if it exists) in terms of infinite products of matrices (that vary as \( x \) varies). Sufficient conditions are given on \( \{c_n\} \) for a continuous nonzero \( L^1 \)-solution to exist. Additional conditions sufficient to guarantee \( f\in C^r \) are also given. The infinite matrix product representations is used to bound from below the degree of regularity of such an \( L^1 \)-solution and to estimate the Hölder exponent of continuity of the highest-order well-defined derivative of \( f(x) \). Such solutions \( f(x) \) are often smoother at some points than others. For certain \( f(x) \) a hierarchy of fractal sets in \( \mathbb{R} \) corresponding to different Hölder exponents of continuity for \( f(x) \) is described.

[50] A. Cohen and I. Daubechies: “A stability criterion for biorthogonal wavelet bases and their related subband coding scheme,” Duke Math. J. 68 : 2 (November 1992), pp. 313–335. MR 1191564 Zbl 0784.42022 article

[51] N. Moayeri, I. Daubechies, Q. Song, and H. S. Wang: “Wavelet transform image coding using trellis coded vector quantization,” pp. 405–408 in ICASSP-92 (San Francisco, 23–26 March 1992), vol. 4. IEEE (Piscataway, NJ), 1992. incollection

A combination of trellis coded quantization (TCQ) and its vector alphabet generalization TCVQ is used to code the coefficients resulting from a biorthogonal wavelet transform in an image. TCVQ is a vector trellis coder with fixed rate, very good rate-distortion performance, and yet reasonable implementation complexity. The experimental results show that the Lena image can be coded by this coding system at the rate of \( 0.265 \) bpp to yield a peak signal-to-noise ratio (PSNR) of about 29 dB. This PSNR is about 3 dB larger than that obtained by a coding system of the same rate that uses VQ to obtain the wavelet transform coefficients. Naturally, the performance of the TCQ/TCVQ wavelet transform coder can be improved if entropy-coded TCQ and TCVQ coders are employed.

Nader Moayeri	Related
Q. Song	Related
H. S. Wang	Related

[52] Wavelets and their applications. Edited by M. B. Ruskai, G. Beylkin, R. Coifman, I. Daubechies, S. Mallat, Y. Meyer, and L. Raphael. Jones and Bartlett (Boston, MA), 1992. Zbl 0782.00087 book

Mary Beth Ruskai	Related
Yves F. Meyer	Related
Ronald Raphael Coifman	Related
Gregory Beylkin	Related
Louise Arakelian Raphael	Related
Stéphane Georges Mallat	Related

[53] I. Daubechies: “Orthonormal bases of compactly supported wavelets, II: Variations on a theme,” SIAM J. Math. Anal. 24 : 2 (1993), pp. 499–519. Part I was published in Commun. Pure Appl. Math. 41:7 (1988). MR 1205539 Zbl 0792.42018 article

[54] A. Cohen and I. Daubechies: “Orthonormal bases of compactly supported wavelets, III: Better frequency resolution,” SIAM J. Math. Anal. 24 : 2 (1993), pp. 520–527. Part I was published in Commun. Pure Appl. Math. 41:7 (1988). MR 1205540 Zbl 0792.42019 article

[55] A. Cohen, I. Daubechies, B. Jawerth, and P. Vial: “Multiresolution analysis, wavelets and fast algorithms on an interval,” C. R. Acad. Sci., Paris, Sér. I 316 : 5 (1993), pp. 417–421. MR 1209259 Zbl 0768.42015 article

Albert Cohen	Related
Björn David Jawerth	Related
Pierre Vial	Related

[56] I. Daubechies and A. J. E. M. Janssen: “Two theorems on lattice expansions,” IEEE Trans. Inf. Theory 39 : 1 (1993), pp. 3–6. MR 1211486 Zbl 0764.42018 article

It is shown that there is a tradeoff between the smoothness and decay properties of the dual functions, occurring in the lattice expansion problem. More precisely, it is shown that if \( g \) and \( \tilde{g} \) are dual, then

at least one of \( H^{1/2}g \) and \( H^{1/2}\tilde{g} \) is not in \( L^2(\mathbb{R}) \), and
at least one of \( Hg \) and \( \tilde{g} \) is not in \( L^2(\mathbb{R}) \). Here, \( H \) is the operator \[ \frac{1}{4\pi^2} \frac{d^2}{dt^2} + t^2 .\]

The first result is a generalization of a theorem first stated by Balian and independently by Low, which was recently rigorously proved by Coifman and Semmes; a new, much shorter proof was very recently given by Battle. Battle suggests a theorem of type (1), but our result is stronger in the sense that certain implicit assumptions made by Battle are removed. Result (2) is new and relies heavily on the fact that, when \( G\in W^{2,2}(S) \) with \[ S = \bigl[-\tfrac12, \tfrac12\bigr]\times \bigl[-\tfrac12, \tfrac12\bigr] \] and \( G(0)=0 \), then \( 1/G\notin L^2(S) \). The latter result was not known to us and may be of independent interest.

[57] A. Cohen and I. Daubechies: “Non-separable bidimensional wavelet bases,” Rev. Mat. Iberoam. 9 : 1 (1993), pp. 51–137. MR 1216125 Zbl 0792.42021 article

We build orthonormal and biorthogonal wavelet bases of \( L^2(\mathbb{R}^2) \) with dilation matrices of determinant 2. As for the one dimensional case, our construction uses a scaling function which solves a two-scale difference equation associated to a FIR filter. Our wavelets are generated from a single compactly supported mother function. However, the regularity of these functions cannot be derived by the same approach as the one dimensional case. We review existing techniques to evaluate the regularity of wavelets, and we introduce new methods which allow to estimate the smoothness of non-separable wavelets and scaling funtions in the most general situations. We illustrate these with several examples.

[58] I. Daubechies: Wavelets making waves in mathematics and engineering, 1993. 60 minute colour videotape (American Mathematical Society, Providence, RI). MAA joint invited address, Baltimore, MD, 9 January 1992. MR 1228207 Zbl 0789.42028 misc

[59] A. Cohen and I. Daubechies: “On the instability of arbitrary biorthogonal wavelet packets,” SIAM J. Math. Anal. 24 : 5 (1993), pp. 1340–1354. MR 1234020 Zbl 0792.42020 article

[60] A. Cohen, I. Daubechies, and P. Vial: “Wavelets on the interval and fast wavelet transforms,” Appl. Comput. Harmon. Anal. 1 : 1 (1993), pp. 54–81. MR 1256527 Zbl 0795.42018 article

Albert Cohen	Related
Pierre Vial	Related

[61] Different perspectives on wavelets (San Antonio, TX, 11–12 January 1993). Edited by I. Daubechies. American Mathematical Society (Providence, RI), 1993. MR 1267994 Zbl 0782.00059 book

[62] I. Daubechies: “Wavelet transforms and orthonormal wavelet bases,” pp. 1–33 in Different perspectives on wavelets (San Antonio, TX, 11–12 January 1993). Edited by I. Daubechies. Proceedings of Symposia in Applied Mathematics 47. American Mathematical Society (Providence, RI), 1993. MR 1267995 Zbl 0802.42025 incollection

[63] I. Daubechies: “Wavelets on the interval,” pp. 95–107 in Progress in wavelet analysis and applications: Proceedings of the 3rd international conference on wavelets and applications (Toulouse, France, 8–13 June 1992). Edited by Y. Meyer and S. Roques. Editions Frontières (Gif-sur-Yvette, France), 1993. MR 1282934 Zbl 0925.42017 incollection

Sylvie Roques	Related
Yves F. Meyer	Related

[64] I. Daubechies: “Orthonormal bases of coherent states: The canonical case and the \( ax+b \)-group,” pp. 103–117 in Coherent states: Past, present, and future (Oak Ridge, TN, 14–17 June 1993). Edited by D. H. Feng, J. R. Klauder, and M. R. Strayer. World Scientific (Singapore), 1994. incollection

Michael R. Strayer	Related
John Rider Klauder	Related
Da Hsuan Feng	Related

[65] I. Daubechies: “Two recent results on wavelets: Wavelet bases for the interval, and biorthogonal wavelets diagonalizing the derivative operator,” pp. 237–257 in Recent advances in wavelet analysis. Edited by L. L. Schumaker and G. Webb. Wavelet Analysis and its Applications 3. Academic Press (Boston), 1994. MR 1244608 Zbl 0829.42021 incollection

Larry Lee Schumaker	Related
Glenn Webb	Related

[66] I. Daubechies and J. C. Lagarias: “On the thermodynamic formalism for multifractal functions,” pp. 1033–1070 in Special issue dedicated to Elliott H. Lieb, published as Rev. Math. Phys. 6 : 5A. Issue edited by M. Aizenman and H. Araki. World Scientific (Singapore), 1994. Also published in The state of matter (1994). MR 1301365 Zbl 0843.58091 incollection

The thermodynamic formalism for “multifractal” functions \( \phi(x) \) is a heuristic principle that states that the singularity spectrum \( f(\alpha) \) (defined as the Hausdorff dimension of the set \( S_{\alpha} \) of points where \( \phi \) has Hölder exponent \( \alpha \)) and the moment scaling exponent \( \tau(q) \) (giving the power law behavior of \[ \int|\phi(x+t)-\phi(x)|^q\,dx \] for small \( |t| \)) should be related by the Legendre transform, \[ \tau(q) = 1 + \inf_{\alpha\geq 0}[q\alpha-f(\alpha)] .\] The range of validity of this heuristic principle is unknown. Here this principle is rigorously verified for a family of “toy examples” that are solutions of refinement equations. These example functions exhibit oscillations on all scales, and correspond to multifractal signed measures rather than multifractal measures; moreover, their singularity spectra \( f(\alpha) \) are not concave.

Jeffrey Clark Lagarias	Related
Michael Aizenman	Related
Elliott Hershel Lieb	Related
Huzihiro Araki	Related

[67] I. Daubechies and Y. Huang: “A decay theorem for refinable functions,” Appl. Math. Lett. 7 : 4 (July 1994), pp. 1–4. MR 1350385 Zbl 0851.42027 article

[68] I. Daubechies: “Affine coherent states and wavelets,” pp. 35–42 in On Klauder’s path: A field trip: Essays in honor of John R. Klauder. Edited by G. G. Emch, G. C. Hegerfeldt, and L. Streit. World Scientific (Singapore), 1994. MR 1350560 Zbl 0942.81559 incollection

Gérard Gustav Emch	Related
Gerhard C. Hegerfeldt	Related
John Rider Klauder	Related
Ludwig Streit	Related

[69] I. Daubechies and J. C. Lagarias: “On the thermodynamic formalism for multifractal functions,” pp. 213–264 in The state of matter: A volume dedicated to E. H. Lieb (Copenhagen, July 1992). Edited by M. Aizenman and H. Araki. Advanced Series in Mathematical Physics 20. World Scientific (Singapore), 1994. Also published in Rev. Math. Phys. 6:5A (1994). MR 1462145 incollection

Jeffrey Clark Lagarias	Related
Michael Aizenman	Related
Elliott Hershel Lieb	Related
Huzihiro Araki	Related

[70] I. Daubechies: “Wavelets: An overview, with recent applications,” pp. 5 in Proceedings of 1995 IEEE international symposium on information theory (Whistler, BC, 17–22 September 1995). IEEE (Piscataway, NJ), 1995. Abstract only. incollection

Wavelets have emerged in the last decade as a synthesis from many disciplines, ranging from pure mathematics (where forerunners were used to study singular integral operators) to electrical engineering (quadrature mirror filters), borrowing in passing from quantum physics, from geophysics and from computer aided design. The author presents an overview of the ideas in wavelet theory, and shows how it fits into the different disciplines in which it is rooted. Some recent applications are discussed, including a nonlinear “squeezing” of the wavelet transform, inspired by auditory models, with applications to speech processing; and a discussion of the nonlinear approximation and why wavelets are so successful in the nonlinear approximation.

[71] I. Daubechies and Y. Huang: “How does truncation of the mask affect a refinable function?,” Constr. Approx. 11 : 3 (1995), pp. 365–380. MR 1350674 Zbl 0874.42025 article

[72] I. Daubechies, H. J. Landau, and Z. Landau: “Gabor time-frequency lattices and the Wexler–Raz identity,” J. Fourier Anal. Appl. 1 : 4 (1995), pp. 437–478. MR 1350701 Zbl 0888.47018 article

Gabor time-frequency lattices are sets of functions of the form \[ g_{m\alpha,n\beta}(t)=e^{-2\pi i\,\alpha mt}g(t-n\beta) \] generated from a given function \( g(t) \) by discrete translations in time and frequency. They are potential tools for the decomposition and handling of signals that, like speech or music, seem over short intervals to have well-defined frequencies that, however, change with time. It was recently observed that the behavior of a lattice \( (m\alpha \), \( n\beta) \) can be connected to that of a dual lattice \( (m/\beta \), \( n/\alpha) \). Here we establish this interesting relationship and study its properties. We then clarify the results by applying the theory of von Neumann algebras. One outcome is a simple proof that for \( g_{m\alpha,n\beta} \) to span \( L^2 \) the lattice \( (m\alpha \), \( n\beta) \) must have at least unit density. Finally, we exploit the connection between the two lattices to construct expansions having improved convergence and localization properties.

Henry Jacob Landau	Related
Zeph A. Landau	Related

[73] I. Daubechies: “Wavelets and other phase space localization methods,” pp. 57–74 in Proceedings of the International Congress of Mathematicians (Zürich, 3–11 August 1994), vol. 1. Edited by S. D. Chatterji. Birkhäuser (Babel), 1995. MR 1403915 Zbl 0845.42012 incollection

[74] I. Daubechies: “Using Fredholm determinants to estimate the smoothness of refinable functions,” pp. 89–112 in Approximation theory VIII (College Station, TX, 8–12 January 1995), vol. 2: Wavelets and multilevel approximation. Edited by C. K. Chui and L. L. Schumaker. World Scientific (Singapore), 1995. MR 1471776 Zbl 0927.42016 incollection

Larry Lee Schumaker	Related
Charles Kam-tai Chui	Related

[75] I. Daubechies: “Better dual functions for Gabor time-frequency lattices,” pp. 113–116 in Approximation theory VIII (College Station, TX, 8–12 January 1995), vol. 2: Wavelets and multilevel approximation. Edited by C. K. Chui and L. L. Schumaker. World Scientific (Singapore), 1995. MR 1471777 Zbl 0927.42017 incollection

Larry Lee Schumaker	Related
Charles Kam-tai Chui	Related

[76] H. C. Von Baeyer: “Wave of the future,” Discover (May 1995), pp. 68–74. article

[77] I. Daubechies: “Where do wavelets come from? A personal point of view,” Proc. IEEE 84 : 4 (April 1996), pp. 510–513. article

The development of wavelets is an example where ideas from many different fields combined to merge into a whole that is more than the sum of its parts. The subject area of wavelets, developed mostly over the last 15 years, is connected to older ideas in many other fields, including pure and applied mathematics, physics, computer science, and engineering. The history of wavelets can therefore be represented as a tree with roots reaching deeply and in many directions. In this picture, the trunk would correspond to the rapid development of “wavelet tools” in the second half of the 1980’s, with shared efforts by researchers from many different fields; the crown of the tree, with its many branches, would correspond to different directions and applications in which wavelets are now becoming a standard part of the mathematical tool kit, alongside other more established techniques. The author gives here a highly personal version of the development of wavelets.

[78] A. Cohen, I. Daubechies, and A. Ron: “How smooth is the smoothest function in a given refinable space?,” Appl. Comput. Harmon. Anal. 3 : 1 (January 1996), pp. 87–89. MR 1374399 Zbl 0901.46024 article

Albert Cohen	Related
Amos Ron	Related

[79] A. Cohen and I. Daubechies: “A new technique to estimate the regularity of refinable functions,” Rev. Mat. Iberoam. 12 : 2 (1996), pp. 527–591. MR 1402677 Zbl 0879.65102 article

[80] I. Daubechies and S. Maes: “A nonlinear squeezing of the continuous wavelet transform based on auditory nerve models,” Chapter 20, pp. 527–546 in Wavelets in medicine and biology. Edited by A. Aldroubi and M. Unser. CRC Press (Boca Raton, FL), 1996. Zbl 0848.92003 incollection

Akram Aldroubi	Related
Stéphane H. Maes	Related
Michael A. Unser	Related

[81] F. Auger, E. Chassande-Mottin, I. Daubechies, and P. Flandrin: Partition du plan temps-fréquence et réallocation [Partition of the time-frequency plan and reassigment], 1997. Online conference proceedings, GRETSI, Grenoble, France, 18–21 September 1997. misc

Patrick Flandrin	Related
Éric Chassande-Mottin	Related
François Auger	Related

[82] A. R. Calderbank, I. Daubechies, W. Sweldens, and B.-L. Yeo: “Lossless image compression using integer to integer wavelet transforms,” pp. 596–599 in 1st international conference on image processing (Santa Barbara, CA, 26–29 October 1997), vol. 1. IEEE (Piscataway, NJ), 1997. incollection

Wim Sweldens	Related
A. Robert Calderbank	Related
Boon-Lock Yeo	Related

[83] E. Chassande-Mottin, I. Daubechies, F. Auger, and P. Flandrin: “Differential reassignment,” IEEE Sig. Proc. Lett. 4 : 10 (October 1997), pp. 293–294. article

Patrick Flandrin	Related
Éric Chassande-Mottin	Related
François Auger	Related

[84] A. Cohen, I. Daubechies, and G. Plonka: “Regularity of refinable function vectors,” J. Fourier Anal. Appl. 3 : 3 (1997), pp. 295–324. MR 1448340 Zbl 0914.42025 article

Albert Cohen	Related
Gerlind Plonka-Hoch	Related

[85] I. Daubechies: “From the original framer to present-day time-frequency and time-scale frames,” J. Fourier Anal. Appl. 3 : 5 (1997), pp. 485–486. Dedicated to the memory of Richard J. Duffin. MR 1491928 Zbl 0903.42013 article

[86] “1997 Satter Prize,” Notices Am. Math. Soc. 44 : 3 (March 1997), pp. 348–349. article

[87] M. Unser and I. Daubechies: “On the approximation power of convolution-based least squares versus interpolation,” IEEE Trans. Signal Process. 45 : 7 (1997), pp. 1697–1711. Zbl 0879.94005 article

There are many signal processing tasks for which convolution-based continuous signal representations such as splines and wavelets provide an interesting and practical alternative to the more traditional sine-based methods. The coefficients of the corresponding signal approximations are typically obtained by direct sampling (interpolation or quasi-interpolation) or by using least squares techniques that apply a prefilter prior to sampling. We compare the performance of these approaches and provide quantitative error estimates that can be used for the appropriate selection of the sampling step \( h \). Specifically, we review several results in approximation theory with a special emphasis on the Strang–Fix conditions, which relate the general \( O(h^L) \) behavior of the error to the ability of the representation to reproduce polynomials of degree \( n=L-1 \). We use this theory to derive pointwise error estimates for the various algorithms and to obtain the asymptotic limit of the \( L_2 \)-error as \( h \) tends to zero. We also propose a new improved \( L_2 \)-error bound for the least squares case. In the process, we provide all the relevant bound constants for polynomial splines. Some of our results suggest the existence of an intermediate range of sampling steps where the least squares method is roughly equivalent to an interpolator with twice the order. We present experimental examples that illustrate the theory and confirm the adequacy of our various bound and limit determinations.

[88] I. Daubechies: “Preface,” pp. 5 in R. Carmona, W.-L. Hwang, and B. Torrésani: Practical time-frequency analysis: Gabor and wavelet transforms with an implementation in S. Wavelet Analysis and Its Applications 9. Academic Press (San Diego, CA), 1998. incollection

Wen-Liang Hwang	Related
René A. Carmona	Related
Bruno S. Torrésani	Related

[89] I. Daubechies: “Recent results in wavelet applications,” J. Electron. Imaging 7 : 4 (October 1998), pp. 719–724. Also published as part of Wavelet Applications V (1998). article

[90] I. Daubechies: “Recent results in wavelet applications,” pp. 2–9 in Wavelet applications V (Orlando, FL, 14–16 April 1998). Edited by H. H. Szu. Proceedings of the Society of Photo-Optical Instrumentation Engineers 3391. 1998. Also published om J. Electron. Imaging 7:4 (1998). incollection

[91] E. Kort: “Ingrid Daubechies,” pp. 34–38 in Notable women in mathematics: A biographical dictionary. Edited by C. Morrow and T. Perl. Greenwood Press (Westport, CT), 1998. incollection

Charlene Morrow	Related
Edith M. Kort	Related
Teri Hoch Perl	Related

[92] A. R. Calderbank, I. Daubechies, W. Sweldens, and B.-L. Yeo: “Wavelet transforms that map integers to integers,” Appl. Comput. Harmon. Anal. 5 : 3 (July 1998), pp. 332–369. MR 1632537 Zbl 0941.42017 article

Invertible wavelet transforms that map integers to integers have important applications in lossless coding. In this paper we present two approaches to build integer to integer wavelet transforms. The first approach is to adapt the precoder of Laroia et al., which is used in information transmission; we combine it with expansion factors for the high and low pass band in subband filtering. The second approach builds upon the idea of factoring wavelet transforms into so-called lifting steps. This allows the construction of an integer version of every wavelet transform. Finally, we use these approaches in a lossless image coder and compare the results to those given in the literature.

Wim Sweldens	Related
A. Robert Calderbank	Related
Boon-Lock Yeo	Related

[93] I. Daubechies and W. Sweldens: “Factoring wavelet transforms into lifting steps,” J. Fourier Anal. Appl. 4 : 3 (1998), pp. 247–269. This was later published (without an abstract) in Wavelets in the geosciences (2000). MR 1650921 Zbl 0913.42027 article

This article is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists, and expressed by the formula \[ \mathrm{SL}\bigl(n;\mathbf{R}[z,z^{-1}]\bigr)=E\bigl(n;\mathbf{R}[z,z^{-1}]\bigr) ;\] it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e., non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers.

[94] D. L. Donoho, M. Vetterli, R. A. DeVore, and I. Daubechies: “Data compression and harmonic analysis,” IEEE Trans. Inf. Theory 44 : 6 (1998), pp. 2435–2476. MR 1658775 Zbl 1125.94311 article

In this paper we review some recent interactions between harmonic analysis and data compression. The story goes back of course to Shannon’s \( R(D) \) theory in the case of Gaussian stationary processes, which says that transforming into a Fourier basis followed by block coding gives an optimal lossy compression technique; practical developments like transform-based image compression have been inspired by this result. In this paper we also discuss connections perhaps less familiar to the information theory community, growing out of the field of harmonic analysis. Recent harmonic analysis constructions, such as wavelet transforms and Gabor transforms, are essentially optimal transforms for transform coding in certain settings. Some of these transforms are under consideration for future compression standards.

We discuss some of the lessons of harmonic analysis in this century. Typically, the problems and achievements of this field have involved goals that were not obviously related to practical data compression, and have used a language not immediately accessible to outsiders. Nevertheless, through an extensive generalization of what Shannon called the “sampling theorem”, harmonic analysis has succeeded in developing new forms of functional representation which turn out to have significant data compression interpretations. We explain why harmonic analysis has interacted with data compression, and we describe some interesting recent ideas in the field that may affect data compression in the future.

Ronald Alvin DeVore	Related
David Leigh Donoho	Related
Martin Vetterli	Related

[95] I. C. Daubechies and A. C. Gilbert: “Harmonic analysis, wavelets and applications,” pp. 159–226 in Hyperbolic equations and frequency interactions. Edited by L. Caffarelli and W. E. IAS/Park City Mathematics Series 5. American Mathematical Society (Providence, RI), 1999. MR 1662830 Zbl 0931.42017 incollection

Anna C. Gilbert	Related
Luis Ángel Caffarelli	Related
Weinan E	Related

[96] I. Daubechies, I. Guskov, and W. Sweldens: “Regularity of irregular subdivision,” Constr. Approx. 15 : 3 (1999), pp. 381–426. MR 1687779 Zbl 0957.42022 article

Igor Guskov	Related
Wim Sweldens	Related

[97] I. Daubechies, I. Guskov, P. Schröder, and W. Sweldens: “Wavelets on irregular point sets,” R. Soc. Lond. Philos. Trans. Ser. A, Math. Phys. Eng. Sci. 357 : 1760 (1999), pp. 2397–2413. MR 1721247 Zbl 0945.42019 article

Peter Schröder	Related
Igor Guskov	Related
Wim Sweldens	Related

[98] I. Daubechies and S. Maes: “An application of a formula of Alberto Calderón to speaker identification,” Chapter 10, pp. 163–181 in Harmonic analysis and partial differential equations: Essays in honor of Alberto P. Calderón’s 75th birthday (Chicago, February 1996). Edited by M. Christ, C. E. Kenig, and C. Sadosky. Chicago Lectures in Mathematics. University of Chicago Press, 1999. MR 1743861 Zbl 1006.92500 incollection

Alberto Pedro Calderón	Related	Volume
Stéphane H. Maes	Related
Cora Sadosky	Related
Francis Michael Christ	Related
Carlos Eduardo Kenig	Related

[99] Z. Cvetkovic and I. Daubechies: “Single-bit oversampled A/D conversion with exponential accuracy in the bit-rate,” pp. 343–352 in Proceedings: Data compression conference 2000 (Snowbird, UT, 28–30 March 2000). Edited by J. A. Storer and M. Cohn. IEEE Computer Society Press (Los Alamitos, CA), 2000. Also published in IEEE Trans. Inform. Theory 53:11 (2007). incollection

James A. Storer	Related
Martin Cohn	Related
Zoran Dusan Cvetković	Related

[100] D. Haunsperger and S. Kennedy: “Coal miner’s daughter,” Math Horizons 7 : 4 (April 2000), pp. 5–9, 28–30. article

Stephen Francis Kennedy	Related
Deanna B. Haunsperger	Related

[101] A. Jackson: “Ingrid Daubechies receives NAS Award in Mathematics,” Notices Am. Math. Soc. 47 : 5 (May 2000), pp. 571. article

[102] R. Balan, I. Daubechies, and V. Vaishampayan: “The analysis and design of windowed Fourier frame based multiple description source coding schemes,” IEEE Trans. Inform. Theory 46 : 7 (2000), pp. 2491–2536. MR 1806816 Zbl 0998.94011 article

In this paper the windowed Fourier encoding-decoding scheme applied to the multiple description compression problem is analyzed. In the general case, four window functions are needed to define the encoder and decoder, although this number can be reduced to three or two by using time-shift or frequency-shift division schemes. The encoding coefficients are next divided into two groups according to the eveness of either the modulation or translation index. The distortion on each channel is analyzed using the Zak transform. For the optimal windows, explicit representation formulas are obtained and nonlocalization results are proved. Asymptotic formulas of the total distortion and transmission rate are established and the redundancy is shown to trade off between these two.

Radu Victor Balan	Related
Vinay A. Vaishampayan	Related

[103] I. Daubechies and W. Sweldens: “Factoring wavelet transforms into lifting steps,” pp. 131–157 in Wavelets in the geosciences: Collection of the lecture notes of the school of wavelets in the geosciences (Delft, Netherlands, 4–9 October 1998). Edited by R. Klees and R. Haagmans. Lectures in Earth Sciences 90. Springer (Berlin), 2000. This was earlier published (with an abstract) in J. Fourier Anal. Appl. 4:3 (1998). Zbl 0963.65154 incollection

Roland Klees	Related
Wim Sweldens	Related
Roger Haagmans	Related

[104] I. Daubechies and J. C. Lagarias: “Corrigendum/addendum to: ‘Sets of matrices all infinite products of which converge’,” Linear Algebra Appl. 327 : 1–3 (April 2001), pp. 69–83. Corrigendum/addendum to article published in Linear Algebra Appl. 161 (1992). MR 1823340 Zbl 0978.15024 article

[105] I. Daubechies, I. Guskov, and W. Sweldens: “Commutation for irregular subdivision,” Constr. Approx. 17 : 4 (2001), pp. 479–514. MR 1845265 Zbl 0994.42019 article

Igor Guskov	Related
Wim Sweldens	Related

[106] A. Cohen, W. Dahmen, I. Daubechies, and R. DeVore: “Tree approximation and optimal encoding,” Appl. Comput. Harmon. Anal. 11 : 2 (2001), pp. 192–226. MR 1848303 Zbl 0992.65151 article

Tree approximation is a new form of nonlinear approximation which appears naturally in some applications such as image processing and adaptive numerical methods. It is somewhat more restrictive than the usual \( n \)-term approximation. We show that the restrictions of tree approximation cost little in terms of rates of approximation. We then use that result to design encoders for compression. These encoders are universal (they apply to general functions) and progressive (increasing accuracy is obtained by sending bit stream increments). We show optimality of the encoders in the sense that they provide upper estimates for the Kolmogorov entropy of Besov balls.

Albert Cohen	Related
Ronald Alvin DeVore	Related
Wolfgang A. Dahmen	Related

[107] I. Daubechies: Desyat’ lektsij po vejvletam [Ten lectures on wavelets]. Edited by A. P. Petukhov. Regulyarnaya i Khaoticheskaya Dinamika (Moscow), 2001. Russian translation of 1992 original. Zbl 1006.42030 book

[108] Z. Cvetkovic, I. Daubechies, and B. F. Logan: “Interpolation of bandlimited functions from quantized irregular samples,” pp. 412–421 in Proceedings: Data compression conference (Snowbird, UT, 2–4 April 2002). Edited by J. A. Storer and M. Cohn. IEEE (Piscataway, NJ), 2002. incollection

The problem of reconstructing a \( \pi \)-bandlimited signal \( f \) from its quantized samples taken at an irregular sequence of points \( t_k \), \( k = \dots, -2 \), \( -1,0 \), \( 1,\dots \) arises in oversampled analog-to-digital conversion. The input signal can be reconstructed from the quantized samples \( f(t_k) \) by estimating samples \( f(n/\lambda) \), \( n = \dots,-2 \), \( -1,0 \), \( 1,\dots \), where \( \lambda \) is the average uniform density of the sequence \( (t_k) \), assumed here to be greater than one, followed by linear low-pass filtering. We study three techniques for estimating samples \( f(n/\lambda) \) from quantized irregular samples \( f(t_k) \), including Lagrangian interpolation, and two other techniques which result in a better overall accuracy of oversampled A/D conversion.

Benjamin F. Logan, Jr.	Related
Martin Cohn	Related
Zoran Dusan Cvetković	Related
James A. Storer	Related

[109] I. Daubechies, R. DeVore, C. S. Güntürk, and V. A. Vaishampayan: “Beta expansions: A new approach to digitally correct A/D conversion,” pp. 784–787 in 2002 IEEE international symposium on circuits and systems: Proceedings (Phoenix-Scottsdale, AZ, 26–29 May 2007), vol. 2. IEEE (Piscataway, NJ), 2002. incollection

We introduce a new architecture for pipelined (and also algorithmic) A/D converters that give exponentially accurate conversion using inaccurate comparators. An error analysis of a sigma-delta converter with an imperfect comparator and a constant input reveals a self-correction property that is not inherited by the successive refinement quantization algorithm that underlies both pipelined multistage A/D converters and algorithmic A/D converters. Motivated by this example, we introduce a new A/D converter, the beta converter, which has the same self-correction property as a sigma-delta converter but which exhibits higher order (exponential) accuracy with respect to the bit rate as compared to a sigma-delta converter, which exhibits only polynomial accuracy.

Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related
Vinay A. Vaishampayan	Related

[110] A. R. Calderbank and I. Daubechies: “The pros and cons of democracy,” pp. 1721–1725 in Shannon theory: Perspective, trends, and applications: Special issue dedicated to Aaron D. Wyner, published as IEEE Trans. Inform. Theory 48 : 6. Issue edited by H. J. Landau, J. E. Mazo, S. Shamai, and J. Ziv. IEEE (New York), June 2002. MR 1902984 Zbl 1061.94014 incollection

Henry Jacob Landau	Related
A. Robert Calderbank	Related
Aaron D. Wyner	Related
Shlomo Shamai	Related
James E. Mazo	Related
Jacob Ziv	Related

[111] I. Daubechies and B. Han: “The canonical dual frame of a wavelet frame,” Appl. Comput. Harmon. Anal. 12 : 3 (2002), pp. 269–285. MR 1912147 Zbl 1013.42023 article

[112] A. Cohen, I. Daubechies, O. G. Guleryuz, and M. T. Orchard: “On the importance of combining wavelet-based nonlinear approximation with coding strategies,” IEEE Trans. Inform. Theory 48 : 7 (2002), pp. 1895–1921. MR 1929999 Zbl 1061.94004 article

This paper provides a mathematical analysis of transform compression in its relationship to linear and nonlinear approximation theory. Contrasting linear and nonlinear approximation spaces, we show that there are interesting classes of functions/random processes which are much more compactly represented by wavelet-based nonlinear approximation. These classes include locally smooth signals that have singularities, and provide a model for many signals encountered in practice, in particular for images. However, we also show that nonlinear approximation results do not always translate to efficient compress on strategies in a rate-distortion sense. Based on this observation, we construct compression techniques and formulate the family of functions/stochastic processes for which they provide efficient descriptions in a rate-distortion sense. We show that this family invariably leads to Besov spaces, yielding a natural relationship among Besov smoothness, linear/nonlinear approximation order, and compression performance in a rate-distortion sense. The designed compression techniques show similarities to modern high-performance transform codecs, allowing us to establish relevant rate-distortion estimates and identify performance limits.

Albert Cohen	Related
Onur G. Guleryuz	Related
Michael T. Orchard	Related

[113] I. Daubechies and F. Planchon: “Adaptive Gabor transforms,” Appl. Comput. Harmon. Anal. 13 : 1 (July 2002), pp. 1–21. MR 1930173 Zbl 1032.94001 article

[114] R. Balan and I. Daubechies: “Optimal stochastic encoding and approximation schemes using Weyl–Heisenberg sets,” Chapter 11, pp. 259–320 in Advances in Gabor analysis. Edited by H. G. Feichtinger and T. Strohmer. Applied and Numerical Harmonic Analysis. Birkhäuser (Boston), 2003. MR 1955939 Zbl 1033.94001 incollection

Thomas Strohmer	Related
Radu Victor Balan	Related
Hans Georg Feichtinger	Related

[115] I. Daubechies, B. Han, A. Ron, and Z. Shen: “Framelets: MRA-based constructions of wavelet frames,” Appl. Comput. Harmon. Anal. 14 : 1 (January 2003), pp. 1–46. MR 1971300 Zbl 1035.42031 article

Zuowei Shen	Related
Amos Ron	Related
Bin Han	Related

[116] A. Cohen, W. Dahmen, I. Daubechies, and R. DeVore: “Harmonic analysis of the space BV,” Rev. Mat. Iberoamericana 19 : 1 (2003), pp. 235–263. MR 1993422 Zbl 1044.42028 article

Albert Cohen	Related
Ronald Alvin DeVore	Related
Wolfgang A. Dahmen	Related

[117] I. Daubechies and R. DeVore: “Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order,” Ann. Math. (2) 158 : 2 (2003), pp. 679–710. MR 2018933 Zbl 1058.94004 article

[118] C. Rudin, I. Daubechies, and R. E. Schapire: “The dynamics of AdaBoost: Cyclic behavior and convergence of margins,” J. Mach. Learn. Res. 5 (2003–2004), pp. 1557–1595. MR 2248027 Zbl 1222.68293 article

In order to study the convergence properties of the AdaBoost algorithm, we reduce AdaBoost to a nonlinear iterated map and study the evolution of its weight vectors. This dynamical systems approach allows us to understand AdaBoost’s convergence properties completely in certain cases; for these cases we find stable cycles, allowing us to explicitly solve for AdaBoost’s output. Using this unusual technique, we are able to show that AdaBoost does not always converge to a maximum margin combined classifier, answering an open question. In addition, we show that “nonoptimal” AdaBoost (where the weak learning algorithm does not necessarily choose the best weak classifier at each iteration) may fail to converge to a maximum margin classifier, even if “optimal” AdaBoost produces a maximum margin. Also, we show that if AdaBoost cycles, it cycles among “support vectors”, i.e., examples that achieve the same smallest margin.

Cynthia Diane Rudin	Related
Robert Elias Schapire	Related

[119] I. Daubechies and B. Han: “Pairs of dual wavelet frames from any two refinable functions,” Constr. Approx. 20 : 3 (2004), pp. 325–352. MR 2057532 Zbl 1055.42025 article

Starting from any two compactly supported refinable functions in \( L_2(\mathbf{R}) \) with dilation factor \( d \), we show that it is always possible to construct \( 2d \) wavelet functions with compact support such that they generate a pair of dual \( d \)-wavelet frames in \( L_2(\mathbf{R}) \). Moreover, the number of vanishing moments of each of these wavelet frames is equal to the approximation order of the dual MRA; this is the highest possible. In particular, when we consider symmetric refinable functions, the constructed dual wavelets are also symmetric or antisymmetric. As a consequence, for any compactly supported refinable function \( \phi \) in \( L_2(\mathbf{R}) \), it is possible to construct, explicitly and easily, wavelets that are finite linear combinations of translates \( \phi(d{\,\cdot\,} - k) \), and that generate a wavelet frame with an arbitrarily preassigned number of vanishing moments. We illustrate the general theory by examples of such pairs of dual wavelet frames derived from \( B \)-spline functions.

[120] I. Daubechies, O. Runborg, and W. Sweldens: “Normal multiresolution approximation of curves,” Constr. Approx. 20 : 3 (2004), pp. 399–463. MR 2057535 Zbl 1051.42025 article

Wim Sweldens	Related
Olof Runborg	Related

[121] I. Daubechies, M. Defrise, and C. De Mol: “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Comm. Pure Appl. Math. 57 : 11 (2004), pp. 1413–1457. MR 2077704 Zbl 1077.65055 ArXiv math/0307152 article

We consider linear inverse problems where the solution is assumed to have a sparse expansion on an arbitrary preassigned orthonormal basis. We prove that replacing the usual quadratic regularizing penalties by weighted \( \ell^p \)-penalties on the coefficients of such expansions, with \( 1\leq p \) \( \leq 2 \), still regularizes the problem. Use of such \( \ell^p \)-penalized problems with \( p < 2 \) is often advocated when one expects the underlying ideal noiseless solution to have a sparse expansion with respect to the basis under consideration. To compute the corresponding regularized solutions, we analyze an iterative algorithm that amounts to a Landweber iteration with thresholding (or nonlinear shrinkage) applied at each iteration step. We prove that this algorithm converges in norm.

Christine De Mol	Related
Michel Defrise	Related

[122] C. Rudin, R. E. Schapire, and I. Daubechies: “Boosting based on a smooth margin,” pp. 502–517 in Learning theory: 17th annual conference on learning theory (Banff, AB, 1–4 July 2004). Edited by J. Shawe-Taylor and Y. Singer. Lecture Notes in Computer Science 3120. Springer (Berlin), 2004. MR 2177931 Zbl 1078.68724 incollection

We study two boosting algorithms, Coordinate Ascent Boosting and Approximate Coordinate Ascent Boosting, which are explicitly designed to produce maximum margins. To derive these algorithms, we introduce a smooth approximation of the margin that one can maximize in order to produce a maximum margin classifier. Our first algorithm is simply coordinate ascent on this function, involving a line search at each step. We then make a simple approximation of this line search to reveal our second algorithm. These algorithms are proven to asymptotically achieve maximum margins, and we provide two convergence rate calculations. The second calculation yields a faster rate of convergence than the first, although the first gives a more explicit (still fast) rate. These algorithms are very similar to AdaBoost in that they are based on coordinate ascent, easy to implement, and empirically tend to converge faster than other boosting algorithms. Finally, we attempt to understand AdaBoost in terms of our smooth margin, focusing on cases where AdaBoost exhibits cyclic behavior.

Robert Elias Schapire	Related
Cynthia Diane Rudin	Related
John Stewart Shawe-Taylor	Related
Yoram Singer	Related

[123] C. Rudin, I. Daubechies, and R. Schapire: “On the dynamics of boosting” in Advances in neural information processing systems 16: Proceedings of the 2003 conference (Vancouver and Whistler, BC, 8–13 December 2003). Edited by S. Thrun, L. K. Saul, and B. Schölkopf. MIT Press (Cambridge, MA), 2004. incollection

In order to understand AdaBoost’s dynamics, especially its ability to maximize margins, we derive an associated simplified nonlinear iterated map and analyze its behavior in low-dimensional cases. We find stable cycles for these cases, which can explicitly be used to solve for AdaBoost’s output. By considering AdaBoost as a dynamical system, we are able to prove Ratsch and Warmuth’s conjecture that AdaBoost may fail to converge to a maximal-margin combined classifier when given a ‘nonoptimal’ weak learning algorithm. AdaBoost is known to be a coordinate descent method, but other known algorithms that explicitly aim to maximize the margin (such as AdaBoost* and arc-gv) are not. We consider a differentiable function for which coordinate ascent will yield a maximum margin solution. We then make a simple approximation to derive a new boosting algorithm whose updates are slightly more aggressive than those of arc-gv.

Lawrence Kevin Saul	Related
Robert Elias Schapire	Related
Sebastian Thrun	Related
Bernhard Schölkopf	Related
Cynthia Diane Rudin	Related

[124] I. Daubechies: “Thought problems: An autobiographical essay,” pp. 358–361 in Complexities: Women in mathematics. Edited by B. A. Case and A. Leggett. Princeton University Press, 2005. incollection

Anne M. Leggett	Related
Bettye Anne Case	Related

[125] I. Daubechies and G. Teschke: “Variational image restoration by means of wavelets: Simultaneous decomposition, deblurring, and denoising,” Appl. Comput. Harmon. Anal. 19 : 1 (2005), pp. 1–16. MR 2147059 Zbl 1079.68104 article

Inspired by papers of Vese–Osher [Modeling textures with total variation minimization and oscillating patterns in image processing, Technical Report 02-19, 2002] and Osher–Solé–Vese [Image decomposition and restoration using total variation minimization and the \( H^{-1} \) norm, Technical Report 02-57, 2002] we present a wavelet-based treatment of variational problems arising in the field of image processing. In particular, we follow their approach and discuss a special class of variational functionals that induce a decomposition of images into oscillating and cartoon components and possibly an appropriate ‘noise’ component. In the setting of [Modeling textures with total variation minimization and oscillating patterns in image processing, Technical Report 02-19, 2002] and [Image decomposition and restoration using total variation minimization and the \( H^{-1} \) norm, Technical Report 02-57, 2002], the cartoon component of an image is modeled by a \( BV \) function; the corresponding incorporation of \( BV \) penalty terms in the variational functional leads to PDE schemes that are numerically intensive. By replacing the \( BV \) penalty term by a \( B_1^1(L_1) \) term (which amounts to a slightly stronger constraint on the minimizer), and writing the problem in a wavelet framework, we obtain elegant and numerically efficient schemes with results very similar to those obtained in [Modeling textures with total variation minimization and oscillating patterns in image processing, Technical Report 02-19, 2002] and [Image decomposition and restoration using total variation minimization and the \( H^{-1} \) norm, Technical Report 02-57, 2002]. This approach allows us, moreover, to incorporate general bounded linear blur operators into the problem so that the minimization leads to a simultaneous decomposition, deblurring and denoising.

[126] I. Daubechies, K. Drakakis, and T. Khovanova: “A detailed study of the attachment strategies of new autonomous systems in the AS connectivity graph,” Internet Math. 2 : 2 (2005), pp. 185–246. MR 2193159 Zbl 1087.05051 article

Konstantinos Drakakis	Related
Tanya Khovanova	Related

[127] E. Pierpaoli, S. Anthoine, K. Huffenberger, and I. Daubechies: “Reconstructing Sunyaev–Zel’dovich clusters in future cosmic microwave background experiments,” Mon. Not. R. Astron. Soc. 359 : 1 (May 2005), pp. 261–271. ArXiv astro-ph/0412197 article

We present a new method for component separation aimed at extracting Sunyaev–Zel’dovich (SZ) galaxy clusters from multifrequency maps of cosmic microwave background (CMB) experiments. This method is designed to recover non-Gaussian, spatially localized and sparse signals. We first characterize the cluster non-Gaussianity by studying it on simulated SZ maps. We then apply our estimator on simulated observations of the Planck and Atacama Cosmology Telescope (ACT) experiments. The method presented here outperforms multifrequency Wiener filtering, both in the reconstructed average intensity for given input and in the associated error. In the absence of point source contamination, this technique reconstructs the ACT (Planck) bright (big) cluster central \( y \) parameter with an intensity that is about 84 (43) per cent of the original input value. The associated error in the reconstruction is about 12 and 27 per cent for the 50 (12) ACT (Planck) clusters considered. For ACT, the error is dominated by beam smearing. In the Planck case, the error in the reconstruction is largely determined by the noise level: a noise reduction by a factor of 7 would imply almost perfect reconstruction and 10 per cent error for a large sample of clusters. We conclude that the selection function of Planck clusters will strongly depend on the noise properties in different sky regions, as well as the specific cluster extraction method assumed.

Elena Pierpaoli	Related
Kevin Huffenberger	Related
Sandrine Anthoine	Related

[128] I. Daubechies: “Correction d’erreurs et compression” [Error correction and compression], Mathématique et Pédagogie 157 (2006), pp. 5–33. article

[129] I. Loris, G. Nolet, I. Daubechies, and F. A. Dahlen: “Tomographic inversion using \( \ell_1 \)-norm regularization of wavelet coefficients,” Geophys. J. Int. 170 : 1 (2006), pp. 359–370. ArXiv physics/0608094 article

Francis Anthony Dahlen	Related
Auguste (Guust) Nolet	Related
Ignace Loris	Related

[130] J. Zou, A. Gilbert, M. Strauss, and I. Daubechies: “Theoretical and experimental analysis of a randomized algorithm for sparse Fourier transform analysis,” J. Comput. Phys. 211 : 2 (January 2006), pp. 572–595. MR 2173397 Zbl 1085.65128 ArXiv math/0411102 article

We analyze a sublinear RA\( \ell \)SFA (randomized algorithm for Sparse Fourier analysis) that finds a near-optimal \( B \)-term Sparse representation \( R \) for a given discrete signal \( S \) of length \( N \), in time and space \( \operatorname{poly}(B \), \( \log(N)) \), following the approach given in [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002]. Its time cost \( \operatorname{poly}(B \), \( \log(N)) \) should be compared with the superlinear \( \Omega(N\log N) \) time requirement of the Fast Fourier Transform (FFT). A straightforward implementation of the RA\( \ell \)SFA, as presented in the theoretical paper [A.C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, STOC, 2002], turns out to be very slow in practice. Our main result is a greatly improved and practical RA\( \ell \)SFA. We introduce several new ideas and techniques that speed up the algorithm. Both rigorous and heuristic arguments for parameter choices are presented. Our RA\( \ell \)SFA constructs, with probability at least \( 1-\delta \), a near-optimal \( B \)-term representation \( R \) in time \[ \operatorname{poly}(B)\log(N)\log(1/\delta)/\epsilon^2 \log(M) \] such that \[ \|S-R\|_2^2 \leq (1+\epsilon)\|S-R_{\mathrm{opt}}\|_2^2 .\] Furthermore, this RA\( \ell \)SFA implementation already beats the FFTW for not unreasonably large \( N \). We extend the algorithm to higher dimensional cases both theoretically and numerically. The crossover point lies at \( N\simeq \) \( 70{,}000 \) in one dimension, and at \( N\simeq \) 900 for data on a \( N{\times}N \) grid in two dimensions for small \( B \) signals where there is noise.

Anna C. Gilbert	Related
Jing Zou	Related
Martin J. Strauss	Related

[131] Fundamental papers in wavelet theory. Edited by C. Heil and D. F. Walnut. Princeton University Press, 2006. With a foreword by Ingrid Daubechies. Introduction by John J. Benedetto. MR 2229251 Zbl 1113.42001 book

John Joseph Benedetto	Related
David Francis Walnut	Related
Christopher Edward Heil	Related

[132] I. Daubechies, R. A. DeVore, C. S. Güntürk, and V. A. Vaishampayan: “A/D conversion with imperfect quantizers,” IEEE Trans. Inform. Theory 52 : 3 (2006), pp. 874–885. MR 2238058 Zbl 1231.94036 article

This paper analyzes mathematically the effect of quantizer threshold imperfection commonly encountered in the circuit implementation of analog-to-digital (A/D) converters such as pulse code modulation (PCM) and sigma–delta (\( \Sigma\Delta \)) modulation. \( \Sigma\Delta \) modulation, which is based on coarse quantization of oversampled (redundant) samples of a signal, enjoys a type of self-correction property for quantizer threshold errors (bias) that is not shared by PCM. Although “classical” \( \Sigma\Delta \) modulation is inferior to PCM in the rate-distortion sense, this robustness feature is believed to be one of the reasons why \( \Sigma\Delta \) modulation is preferred over PCM in A/D converters with imperfect quantizers. Motivated by these facts, other encoders are constructed in this paper that use redundancy to obtain a similar self-correction property, but that achieve higher order accuracy relative to bit rate compared to classical \( \Sigma\Delta \). More precisely, two different types of encoders are introduced that exhibit exponential accuracy in the bit rate (in contrast to the polynomial-type accuracy of classical \( \Sigma\Delta \)) while possessing the self-correction property.

Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related
Vinay A. Vaishampayan	Related

[133] I. Daubechies and Ö. Yılmaz: “Robust and practical analog-to-digital conversion with exponential precision,” IEEE Trans. Inform. Theory 52 : 8 (2006), pp. 3533–3545. MR 2242363 Zbl 1231.94037 article

Beta-encoders with error correction were introduced by Daubechies, DeVore, Guumlntuumlrk and Vaishampayan as an alternative to pulse-code modulation (PCM) for analog-to-digital conversion. An \( N \)-bit beta-encoder quantizes a real number by computing one of its \( N \)-bit truncated \( \beta \)-expansions where \( \beta\in(1,2) \) determines the base of expansion. These encoders have (almost) optimal rate-distortion properties like PCM; furthermore, they exploit the redundancy of beta-expansions and thus they are robust with respect to quantizer imperfections. However, these encoders have the shortcoming that the decoder needs to know the value of the base of expansion \( \beta \), a gain factor in the circuit used by the encoder, which is an impractical constraint. We present a method to implement beta-encoders so that they are also robust with respect to uncertainties of the value of beta. The method relies upon embedding the value of \( \beta \) in the encoded bitstream. We show that this can be done without a priori knowledge of beta by the transmitting party. Moreover the algorithm still works if the value of \( \beta \) changes (slowly) during the implementation.

[134] S. Anthoine, E. Pierpaoli, and I. Daubechies: “Deux méthodes de déconvolution et séparation simultanées: Application à la reconstruction des amas de galaxies” [Two approaches for the simultaneous separation and deblurring: Application to astrophysical data], Trait. Signal 23 : 5–6 (2006), pp. 439–447. Zbl 1245.94013 article

Elena Pierpaoli	Related
Sandrine Anthoine	Related

[135] S. Hughes and I. Daubechies: “Simpler alternatives to information theoretic similarity metrics for multimodal image alignment” in 2006 International conference on image processing (Atlanta, GA, 8–11 October 2006). Proceedings, International Conference on Image Processing. IEEE (Piscataway, NJ), 2007. incollection

Mutual information (MI) based methods for image registration enjoy great experimental success and are becoming widely used. However, they impose a large computational burden that limits their use; many applications would benefit from a reduction of the computational load. Although the theoretical justification for these methods draws upon the stochastic concept of mutual information, in practice, such methods actually seek the best alignment by maximizing a number that is (deterministically) computed from the two images. These methods thus optimize a fixed function, the “similarity metric,” over different candidate alignments of the two images. Accordingly, we study the important features of the computationally complex MI similarity metric with the goal of distilling them into simpler surrogate functions that are easier to compute. More precisely, we show that maximizing the MI similarity metric is equivalent to minimizing a certain distance metric between equivalence classes of images, where images \( f \) and \( g \) are said to be equivalent if there exists a bijection \( \phi \) such that \( f(x) = \phi(g(x)) \) for all \( x \). We then show how to design new similarity metrics for image alignment with this property. Although we preserve only this aspect of MI, our new metrics show equal alignment accuracy and similar robustness to noise, while significantly decreasing computation time. We conclude that even the few properties of MI preserved by our method suffice for accurate registration and may in fact be responsible for MI’s success.

[136] I. Daubechies, G. Teschke, and L. Vese: “Iteratively solving linear inverse problems under general convex constraints,” Inverse Probl. Imaging 1 : 1 (2007), pp. 29–46. MR 2262744 Zbl 1123.65044 article

We consider linear inverse problems where the solution is assumed to fulfill some general homogeneous convex constraint. We develop an algorithm that amounts to a projected Landweber iteration and that provides and iterative approach to the solution of this inverse problem. For relatively moderate assumptions on the constraint we can always prove weak convergence of the iterative scheme. In certain cases, i.e. for special families of convex constraints, weak convergence implies norm convergence. The presented approach covers a wide range of problems, e.g. Besov- or BV-restoration for which we present also numerical experiments in the context of image processing.

Luminita Aura Vese	Related
Gerd Teschke	Related

[137] I. Daubechies, O. Runborg, and J. Zou: “A sparse spectral method for homogenization multiscale problems,” Multiscale Model. Simul. 6 : 3 (2007), pp. 711–740. MR 2368964 Zbl 1152.65099 article

We develop a new sparse spectral method, in which the fast Fourier transform (FFT) is replaced by RA\( \mathcal{\ell} \)SFA (randomized algorithm of sparse Fourier analysis); this is a sublinear randomized algorithm that takes time \( O(B \log N) \) to recover a \( B \)-term Fourier representation for a signal of length \( N \), where we assume \( B \ll N \). To illustrate its potential, we consider the parabolic homogenization problem with a characteristic fine scale size \( \varepsilon \). For fixed tolerance the sparse method has a computational cost of \( O(|\log\varepsilon|) \) per time step, whereas standard methods cost at least \( O(\varepsilon^{-1}) \). We present a theoretical analysis as well as numerical results; they show the advantage of the new method in speed over the traditional spectral methods when \( \varepsilon \) is very small. We also show some ways to extend the methods to hyperbolic and elliptic problems.

Olof Runborg	Related
Jing Zou	Related

[138] C. Rudin, R. E. Schapire, and I. Daubechies: “Analysis of boosting algorithms using the smooth margin function,” Ann. Statist. 35 : 6 (2007), pp. 2723–2768. MR 2382664 Zbl 1132.68827 ArXiv 0803.4092 article

We introduce a useful tool for analyzing boosting algorithms called the “smooth margin function,” a differentiable approximation of the usual margin for boosting algorithms. We present two boosting algorithms based on this smooth margin, “coordinate ascent boosting” and “approximate coordinate ascent boosting,” which are similar to Freund and Schapire’s AdaBoost algorithm and Breiman’s arc-gv algorithm. We give convergence rates to the maximum margin solution for both of our algorithms and for arc-gv. We then study AdaBoost’s convergence properties using the smooth margin function. We precisely bound the margin attained by AdaBoost when the edges of the weak classifiers fall within a specified range. This shows that a previous bound proved by Rätsch and Warmuth is exactly tight. Furthermore, we use the smooth margin to capture explicit properties of AdaBoost in cases where cyclic behavior occurs.

Cynthia Diane Rudin	Related
Robert Elias Schapire	Related

[139] C. Rudin, R. E. Schapire, and I. Daubechies: “Precise statements of convergence for AdaBoost and arc-gv,” pp. 131–145 in Prediction and discovery: AMS-IMS-SIAM joint summer research conference on machine and statistical learning (Snowbird, UT, 25–29 June 2006). Edited by J. S. Verducci, X. Shen, and J. Lafferty. Contemporary Mathematics 443. American Mathematical Society (Providence, RI), 2007. Paper dedicated to Leo Breiman. Available open access here. MR 2433289 Zbl 1141.68722 incollection

We present two main results, the first concerning Freund and Schapire’s AdaBoost algorithm, and the second concerning Breiman’s arc-gv algorithm. Our discussion of AdaBoost revolves around a circumstance called the case of “bounded edges”, in which AdaBoost’s convergence properties can be completely understood. Specifically, our first main result is that if AdaBoost’s “edge” values fall into a small interval, a corresponding interval can be found for the asymptotic margin. A special case of this result closes an open theoretical question of Rätsch and Warmuth. Our main result concerning arc-gv is a convergence rate to a maximum margin solution. Both of these results are derived from an important tool called the “smooth margin”, which is a differentiable approximation of the true margin for boosting algorithms.

Robert Elias Schapire	Related
Leo Breiman	Related
Cynthia Diane Rudin	Related
Xiaotong Shen	Related
Joseph Stephen Verducci	Related
John D. Lafferty	Related

@incollection {key2433289m,
	AUTHOR = {Rudin, Cynthia and Schapire, Robert
		 E. and Daubechies, Ingrid},
	TITLE = {Precise statements of convergence for
		 {A}da{B}oost and arc-gv},
	BOOKTITLE = {Prediction and discovery: {AMS}-{IMS}-{SIAM}
		 joint summer research conference on
		 machine and statistical learning},
	EDITOR = {Verducci, Joseph S. and Shen, Xiaotong
		 and Lafferty, John},
	SERIES = {Contemporary Mathematics},
	NUMBER = {443},
	PUBLISHER = {American Mathematical Society},
	ADDRESS = {Providence, RI},
	YEAR = {2007},
	PAGES = {131--145},
	DOI = {10.1090/conm/443/08559},
	NOTE = {(Snowbird, UT, 25--29 June 2006). Paper
		 dedicated to Leo Breiman. Available
		 open access at http://web.mit.edu/rudin/www/docs/RudinScDa07a.pdf.
		 MR:2433289. Zbl:1141.68722.},
	ISSN = {0271-4132},
	ISBN = {9780821841952},
}

[140] Z. Cvetković, I. Daubechies, and B. F. Logan, Jr.: “Single-bit oversampled A/D conversion with exponential accuracy in the bit rate,” IEEE Trans. Inform. Theory 53 : 11 (2007), pp. 3979–3989. Also published in Proceedings: DCC 2000 (2000). MR 2446550 Zbl 1231.94041 article

A scheme for simple oversampled analog-to-digital (A/D) conversion using single-bit quantization is presented. The scheme is based on recording positions of zero-crossings of the input signal added to a deterministic dither function. This information can be represented in a manner such that the bit rate increases only logarithmically with the oversampling factor \( r \). The input band-limited signal can be reconstructed from this information locally with \( O(1/r) \) pointwise error, resulting in an exponentially decaying distortion-rate characteristic. In the course of studying the accuracy of the proposed A/D conversion scheme, some new results are established about reconstruction of band-limited signals from irregular samples using linear combination of functions with fast decay. Schemes for local interpolation of band-limited signals from quantized irregular samples are also proposed.

Benjamin F. Logan, Jr.	Related
Zoran Dusan Cvetković	Related

[141] I. Daubechies, R. DeVore, M. Fornasier, and S. Gunturk: “Iteratively re-weighted least squares minimization: Proof of faster than linear rate for sparse recovery,” pp. 26–29 in 2008 42nd annual conference on information sciences and systems (Princeton, NJ, 19–21 March 2008). IEEE (Piscataway, NJ), 2008. incollection

Given an \( m{\times}N \) matrix \( \Phi \), with \( m < N \), the system of equations \( \Phi x = y \) is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a “best” solution. One of the oldest is to select the one with minimal \( \ell_2 \) norm. It has been shown that in many applications a better choice is the minimal \( \ell_1 \) norm solution. This is the case in Compressive Sensing, when sparse solutions are sought.

The minimal \( \ell_1 \) norm solution can be found by using linear programming; an alternative method is Iterative Re-weighted Least Squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight \( w \), the solution with smallest \( \ell_2(w) \) norm; this weight is updated at every iteration step: if \( x^{(n)} \) is the solution at step \( n \), then \( w^{(n)} \) is defined by \[ w_i^{(n)} := \frac1{|x_i^{(n)}|},\quad i = 1,\dots,N .\]

We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix \( \Phi \) known as the Restricted Isometry Property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate \( \ell_1 \)-minimization, the exponential rate is linear; in adapted versions aimed at \( \ell_{\tau} \)-minimization with \( \tau < 1 \), we prove faster than linear rate.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

[142] C. R. Johnson, Jr., E. Hendriks, I. J. Berezhnoy, E. Brevdo, S. M. Hughes, I. Daubechies, J. Li, E. Postma, and J. Z. Wang: “Image processing for artist identification: Computerized analysis of Vincent van Gogh’s painting brushstrokes,” IEEE Signal Process. Mag. 25 : 4 (2008), pp. 37–48. article

J. Z. Wang	Related
C. Richard Johnson, Jr.	Related
Jia Li	Related
Igor J. Berezhnoy	Related
Eric Postma	Related
Ella Hendriks	Related
Eugene Brevdo	Related
Shannon M. Hughes	Related

[143] I. Daubechies, M. Fornasier, and I. Loris: “Accelerated projected gradient method for linear inverse problems with sparsity constraints,” J. Fourier Anal. Appl. 14 : 5–6 (2008), pp. 764–792. MR 2461606 Zbl 1175.65062 ArXiv 0706.4297 article

Regularization of ill-posed linear inverse problems via \( \ell_1 \) penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an \( \ell_1 \) penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to \( \ell_1 \)-constraints, using a gradient method, with projection on \( \ell_1 \)-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.

Massimo Fornasier	Related
Ignace Loris	Related

[144] D. Huylebrouck: “Interview met Ingrid Daubechies: De typische reflex van de wiskundige” [Interview with Ingrid Daubechies: The typical reflex of the mathematician], Nieuw Arch. Wiskd. (5) 9 : 3 (2008), pp. 198–203. Zbl 1239.01089 article

[145] B. Cornelis, A. Dooms, I. Daubechies, and P. Schelkens: Report on digital image processing for art historians, 2009. In online proceedings “SAMPTA’09: SAMPling Theory and Applications,” L. Fesquet and B. Torrésani, eds. (Marseille, France, 18–22 May 2009). misc

As art museums are digitizing their collections, a crossdisciplinary interaction between image analysts, mathematicians and art historians is emerging, putting to use recent advances made in the field of image processing (in acquisition as well as in analysis). An example of this is the Digital Painting Analysis (DPA) initiative, bringing together several research teams from universities and museums to tackle art related questions such as artist authentication, dating, etc. Some of these questions were formulated by art historians as challenges for the research teams. The results, mostly on van Gogh paintings, were presented at two workshops. As part of the Princeton team within the DPA initiative we give an overview of the work that was performed so far.

Bruno Cornelis	Related
Peter Schelkens	Related
Ann Dooms	Related

[146] I. Daubechies, E. Roussos, S. Takerkart, M. Benharrosh, C. Golden, K. D’Ardenne, W. Richter, J. D. Cohen, and J. Haxby: “Independent component analysis for brain fMRI does NOT select for independence,” Proc. Natl. Acad. Sci. USA 106 : 26 (2009), pp. 10415–10422. article

Sylvain Takerkart	Related
Jonathan D. Cohen	Related
James V. Haxby	Related
Michael S. Benharrosh	Related
Kimberlee D'Ardenne	Related
Wolfgang Richter	Related
Evangelos Roussos	Related
Cliona Golden	Related

[147] S. Jafarpour, G. Polatkan, E. Brevdo, S. Hughes, A. Brasoveanu, and I. Daubechies: “Stylistic analysis of paintings using wavelets and machine learning,” pp. 1220–1224 in 17th European signal processing conference (EUSIPCO 2009) (Glasgow, Scotland, 24–28 August 2009). IEEE (Piscataway, NJ), 2009. incollection

Güngör Polatkan	Related
Andrei Brasoveanu	Related
Eugene Brevdo	Related
Shannon M. Hughes	Related
Sina Jafarpour	Related

[148] Y. Lipman and I. Daubechies: Surface comparison with mass transportation. Preprint, December 2009. ArXiv 0912.3488 techreport

We use mass-transportation as a tool to compare surfaces (2-manifolds). In particular, we determine the “similarity” of two given surfaces by solving a mass-transportation problem between their conformal densities. This mass transportation problem differs from the standard case in that we require the solution to be invariant under global Möbius transformations. Our approach provides a constructive way of defining a metric in the abstract space of simply-connected smooth surfaces with boundary (i.e. surfaces of disk-type); this metric can also be used to define meaningful intrinsic distances between pairs of “patches” in the two surfaces, which allows automatic alignment of the surfaces. We provide numerical experiments on “real-life” surfaces to demonstrate possible applications in natural sciences.

[149] G. Polatkan, S. Jafarpour, A. Brasoveanu, S. Hughes, and I. Daubechies: “Detection of forgery in paintings using supervised learning,” pp. 2921–2924 in 2009 IEEE international conference on image processing (Cairo, 7–12 November 2009). Proceedings, International Conference on Image Processing. IEEE (Piscataway, NJ), 2009. incollection

This paper examines whether machine learning and image analysis tools can be used to assist art experts in the authentication of unknown or disputed paintings. Recent work on this topic has presented some promising initial results. Our reexamination of some of these recently successful experiments shows that variations in image clarity in the experimental datasets were correlated with authenticity, and may have acted as a confounding factor, artificially improving the results. To determine the extent of this factor’s influence on previous results, we provide a new “ground truth” data set in which originals and copies are known and image acquisition conditions are uniform. Multiple previously-successful methods are found ineffective on this new confounding-factor-free dataset, but we demonstrate that supervised machine learning on features derived from hidden-Markov-tree-modeling of the paintings’ wavelet coefficients has the potential to distinguish copies from originals in the new dataset.

Güngör Polatkan	Related
Andrei Brasoveanu	Related
Shannon M. Hughes	Related
Sina Jafarpour	Related

[150] J. Brodie, I. Daubechies, C. De Mol, D. Giannone, and I. Loris: “Sparse and stable Markowitz portfolios,” Proc. Natl. Acad. Sci. USA 106 : 30 (2009), pp. 12267–12272. Zbl 1203.91271 ArXiv 0708.0046 article

We consider the problem of portfolio selection within the classical Markowitz mean-variance framework, reformulated as a constrained least-squares regression problem. We propose to add to the objective function a penalty proportional to the sum of the absolute values of the portfolio weights. This penalty regularizes (stabilizes) the optimization problem, encourages sparse portfolios (i.e., portfolios with only few active positions), and allows accounting for transaction costs. Our approach recovers as special cases the no-short-positions portfolios, but does allow for short positions in limited number. We implement this methodology on two benchmark data sets constructed by Fama and French. Using only a modest amount of training data, we construct portfolios whose out-of-sample performance, as measured by Sharpe ratio, is consistently and significantly better than that of the naïve evenly weighted portfolio.

Ignace Loris	Related
Christine De Mol	Related
Domenico Giannone	Related
Joshua Brodie	Related

[151] I. Loris, H. Douma, G. Nolet, I. Daubechies, and C. Regone: “Nonlinear regularization techniques for seismic tomography,” J. Comput. Phys. 229 : 3 (February 2010), pp. 890–905. MR 2566369 Zbl 1182.86003 ArXiv 0808.3472 article

The effects of several nonlinear regularization techniques are discussed in the framework of 3D seismic tomography. Traditional, linear, \( \ell_2 \) penalties are compared to so-called sparsity promoting \( \ell_1 \) and \( \ell_0 \) penalties, and a total variation penalty. Which of these algorithms is judged optimal depends on the specific requirements of the scientific experiment. If the correct reproduction of model amplitudes is important, classical damping towards a smooth model using an \( \ell_2 \) norm works almost as well as minimizing the total variation but is much more efficient. If gradients (edges of anomalies) should be resolved with a minimum of distortion, we prefer \( \ell_1 \) damping of Daubechies-4 wavelet coefficients. It has the additional advantage of yielding a noiseless reconstruction, contrary to simple \( \ell_2 \) minimization (‘Tikhonov regularization’) which should be avoided. In some of our examples, the \( \ell_0 \) method produced notable artifacts. In addition we show how nonlinear \( \ell_1 \) methods for finding sparse models can be competitive in speed with the widely used \( \ell_2 \) methods, certainly under noisy conditions, so that there is no need to shun \( \ell_1 \) penalizations.

Huub Douma	Related
Ignace Loris	Related
Carl J. Regone	Related
Auguste (Guust) Nolet	Related

[152] I. Daubechies, R. DeVore, M. Fornasier, and C. S. Güntürk: “Iteratively reweighted least squares minimization for sparse recovery,” Comm. Pure Appl. Math. 63 : 1 (2010), pp. 1–38. MR 2588385 Zbl 1202.65046 ArXiv 0807.0575 article

Under certain conditions (known as the restricted isometry property, or RIP) on the \( m{\times}N \) matrix \( \Phi \) (where \( m < N \)), vectors \( x\in\mathbb{R}^N \) that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from \( y := \Phi x \) even though \( \Phi^{-1}(y) \) is typically an \( (N-m) \)-dimensional hyperplane; in addition, \( x \) is then equal to the element in \( \Phi^{-1}(y) \) of minimal \( \ell_1 \)-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining \( x \), as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector \( w \), the element in \( \Phi^{-1}(y) \) with smallest \( \ell_2(w) \)-norm. If \( x^{(n)} \) is the solution at iteration step \( n \), then the new weight \( w^{(n)} \) is defined by \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1/2} ,\] \( i = 1, \dots,N \), for a decreasing sequence of adaptively defined \( \epsilon_n \); this updated weight is then used to obtain \( x^{(n+1)} \) and the process is repeated. We prove that when \( \Phi \) satisfies the RIP conditions, the sequence \( x^{(n)} \) converges for all \( y \), regardless of whether \( \Phi^{-1}(y) \) contains a sparse vector. If there is a sparse vector in \( \Phi^{-1}(y) \), then the limit is this sparse vector, and when \( x^{(n)} \) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight \[ w_i^{(n)} := \bigl[|x_i^{(n)}|^2 + \epsilon_n^2\bigr]^{-1 + \tau/2} ,\] \( i = 1,\dots,N \), where \( 0 < \tau < 1 \), can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for \( \tau \) approaching 0.

Massimo Fornasier	Related
Ronald Alvin DeVore	Related
Cemalettin Sinan Güntürk	Related

[153] I. Daubechies, S. Güntürk, Y. Wang, and Ö. Yılmaz: “The Golden ratio encoder,” IEEE Trans. Inform. Theory 56 : 10 (2010), pp. 5097–5110. MR 2808667 Zbl 1366.94231 ArXiv 0809.1257 article

This paper proposes a novel Nyquist-rate analog-to-digital (A/D) conversion algorithm which achieves exponential accuracy in the bit-rate despite using imperfect components. The proposed algorithm is based on a robust implementation of a beta-encoder with \[ \beta = \phi = \frac{1 + \sqrt{5}}2 ,\] the golden ratio. It was previously shown that beta-encoders can be implemented in such a way that their exponential accuracy is robust against threshold offsets in the quantizer element. This paper extends this result by allowing for imperfect analog multipliers with imprecise gain values as well. Furthermore, a formal computational model for algorithmic encoders and a general test bed for evaluating their robustness is proposed.

Özgür Yılmaz	Related
Yang Wang	Related
Cemalettin Sinan Güntürk	Related

[154] I. Daubechies: “The work of Yves Meyer,” pp. 115–124 in Proceedings of the International Congress of Mathematicians (Hyderabad, India, 19–27 August 2010), vol. 1. Edited by R. Bhatia, P. A. Gastesi, A. Pal, G. Rangarajan, V. Srinivas, and M. Vanninathan. Hindustan Book Agency (New Delhi), 2010. MR 2827886 Zbl 1225.01059 incollection

Yves Meyer has made numerous contributions to mathematics, several of which will be reviewed here, in particular in number theory, harmonic analysis and partial differential equations.

His work in harmonic analysis led him naturally to take an interest in wavelets, when they emerged in the early 1980s; his synthesis of the advanced theoretical results in singular integral operator theory, established by himself and others, and of the requirements imposed by practical applications, led to enormous progress for wavelet theory and its applications. Wavelets and wavelet packets are now standard, extremely useful tools in many disciplines; their success is due in large measure to the vision, the insight and the enthusiasm of Yves Meyer.

Yves F. Meyer	Related
Vasudevan Srinivas	Related
Rajendra Bhatia	Related
Muthusamy Vanninathan	Related
Pablo Arés Gastesi	Related
Govindan Rangarajan	Related
Arup Kumar Pal	Related

[155] A. Anitha, A. Brasoveanu, M. F. Duarte, S. M. Hughes, I. Daubechies, J. Dik, K. Janssens, and M. Alfeld: “Virtual underpainting reconstruction from X-ray fluorescence imaging data,” pp. 1239–1243 in 2011 19th European signal processing conference (Barcelona, 29 August–2 September 2011). IEEE (Piscataway, NJ), 2011. incollection

This paper describes our work on the problem of reconstructing the original visual appearance of underpaintings (paintings that have been painted over and are now covered by a new surface painting) from noninvasive X-ray fluorescence imaging data of their canvases. This recently-developed imaging technique yields data revealing the concentrations of various chemical elements at each spatial location across the canvas. These concentrations in turn result from pigments present in both the surface painting and the underpainting beneath. Reconstructing a visual image of the underpainting from this data involves repairing acquisition artifacts in the dataset, underdetermined source separation into surface and underpainting features, identification and inpainting of areas of information loss, and finally estimation of the original paint colors from the chemical element data. We will describe methods we have developed to address each of these stages of underpainting recovery and show results on lost underpaintings.

Matthias Alfeld	Related
Anila Anitha	Related
Marco F. Duarte	Related
Koen Janssens	Related
Joris Dik	Related
Andrei Brasoveanu	Related
Shannon M. Hughes	Related

[156] D. M. Boyer, Y. Lipman, E. S. Clair, J. Puente, B. A. Patel, T. Funkhouser, J. Jernvall, and I. Daubechies: “Algorithms to automatically quantify the geometric similarity of anatomical surfaces,” Proc. Natl. Acad. Sci. USA 108 : 45 (2011), pp. 18221–18226. ArXiv 1110.3649 article

We describe approaches for distances between pairs of two-dimensional surfaces (embedded in three-dimensional space) that use local structures and global information contained in interstructure geometric relationships. We present algorithms to automatically determine these distances as well as geometric correspondences. This approach is motivated by the aspiration of students of natural science to understand the continuity of form that unites the diversity of life. At present, scientists using physical traits to study evolutionary relationships among living and extinct animals analyze data extracted from carefully defined anatomical correspondence points (landmarks). Identifying and recording these landmarks is time consuming and can be done accurately only by trained morphologists. This necessity renders these studies inaccessible to nonmorphologists and causes phenomics to lag behind genomics in elucidating evolutionary patterns. Unlike other algorithms presented for morphological correspondences, our approach does not require any preliminary marking of special features or landmarks by the user. It also differs from other seminal work in computational geometry in that our algorithms are polynomial in nature and thus faster, making pairwise comparisons feasible for significantly larger numbers of digitized surfaces. We illustrate our approach using three datasets representing teeth and different bones of primates and humans, and show that it leads to highly accurate results.

Biren A. Patel	Related
Jukka Jernvall	Related
Elizabeth M. St. Clair	Related
Yaron Lipman	Related
Jesus Puente	Related
Thomas Allen Funkhouser	Related
Douglas Martin Boyer	Related

[157] J. M. Bunn, D. M. Boyer, Y. Lipman, E. M. S. Clair, J. Jernvall, and I. Daubechies: “Comparing Dirichlet normal surface energy of tooth crowns, a new technique of molar shape quantification for dietary inference, with previous methods in isolation and in combination,” Am. J. Phys. Anthropol. 145 : 2 (June 2011), pp. 247–261. article

Inferred dietary preference is a major component of paleoecologies of extinct primates. Molar occlusal shape correlates with diet in living mammals, so teeth are a potentially useful structure from which to reconstruct diet in extinct taxa. We assess the efficacy of Dirichlet normal energy (DNE) calculated for molar tooth surfaces for reflecting diet. We evaluate DNE, which uses changes in normal vectors to characterize curvature, by directly comparing this metric to metrics previously used in dietary inference. We also test whether combining methods improves diet reconstructions. The study sample consisted of 146 lower (mandibular) second molars belonging to 24 euarchontan taxa. Five shape quantification metrics were calculated on each molar: DNE, shearing quotient, shearing ratio, relief index, and orientation patch count rotated (OPCR). Statistical analyses were completed for each variable to assess effects of taxon and diet. Discriminant function analysis was used to assess ability of combinations of variables to predict diet. Values differ significantly by diets for all variables, although shearing ratios and OPCR do not distinguish statistically between insectivores and folivores or omnivores and frugivores. Combined analyses were much more effective at predicting diet than any metric alone. Alone, relief index and DNE were most effective at predicting diet. OPCR was the least effective alone but is still valuable as the only quantitative measure of surface complexity. Of all methods considered, DNE was the least methodologically sensitive, and its effectiveness suggests it will be a valuable tool for dietary reconstruction.

Jukka Jernvall	Related
Elizabeth M. St. Clair	Related
Yaron Lipman	Related
Douglas Martin Boyer	Related
Jonathan M. Bunn	Related

[158] I. Daubechies, J. Lu, and H.-T. Wu: “Synchrosqueezed wavelet transforms: An empirical mode decomposition-like tool,” Appl. Comput. Harmon. Anal. 30 : 2 (2011), pp. 243–261. MR 2754779 Zbl 1213.42133 ArXiv 0912.2437 article

The EMD algorithm is a technique that aims to decompose into their building blocks functions that are the superposition of a (reasonably) small number of components, well separated in the time-frequency plane, each of which can be viewed as approximately harmonic locally, with slowly varying amplitudes and frequencies. The EMD has already shown its usefulness in a wide range of applications including meteorology, structural stability analysis, medical studies. On the other hand, the EMD algorithm contains heuristic and ad hoc elements that make it hard to analyze mathematically.

In this paper we describe a method that captures the flavor and philosophy of the EMD approach, albeit using a different approach in constructing the components. The proposed method is a combination of wavelet analysis and reallocation method. We introduce a precise mathematical definition for a class of functions that can be viewed as a superposition of a reasonably small number of approximately harmonic components, and we prove that our method does indeed succeed in decomposing arbitrary functions in this class. We provide several examples, for simulated as well as real data.

Jianfeng Lu	Related
Hau-Tieng Wu	Related

[159] Y. Lipman and I. Daubechies: “Conformal Wasserstein distances: Comparing surfaces in polynomial time,” Adv. Math. 227 : 3 (2011), pp. 1047–1077. Part II was published in Math. Comp. 82:281 (2013). MR 2799600 Zbl 1217.53026 ArXiv 1103.4408 article

[160] M. Cook: “Ingrid Chantal Daubechies,” Mitt. Dtsch. Math.-Ver. 19 : 1 (2011), pp. 34–35. MR 2830402 article

[161] H.-T. Wu, P. Flandrin, and I. Daubechies: “One or two frequencies? The synchrosqueezing answers,” Adv. Adapt. Data Anal. 3 : 1–2 (April 2011), pp. 29–39. MR 2835580 Zbl 1234.94018 article

Hau-Tieng Wu	Related
Patrick Flandrin	Related

[162] L. Platiša, B. Cornelis, T. Ružić, A. Pižurica, A. Dooms, M. Martens, M. De Mey, and I. Daubechies: “Spatiogram features to characterize pearls in paintings,” pp. 801–804 in 18th IEEE international conference on image processing (Brussels, 11–14 September 2011). IEEE (Piscataway, NJ), 2011. incollection

Objective characterization of jewels in paintings, especially pearls, has been a long lasting challenge for art historians. The way an artist painted pearls reflects his ability to observing nature and his knowledge of contemporary optical theory. Moreover, the painterly execution may also be considered as an individual characteristic useful in distinguishing hands. In this work, we propose a set of image analysis techniques to analyze and measure spatial characteristics of the digital images of pearls, all relying on the so called spatiogram image representation. Our experimental results demonstrate good correlation between the new metrics and the visually observed image features, and also capture the degree of realism of the visual appearance in the painting. In that sense, these results set the basis in creating a practical tool for art historical attribution and give strong motivation for further investigations in this direction.

Bruno Cornelis	Related
Aleksandra Pižurica	Related
Maximiliaan P. J. Martens	Related
Ljiljana Platiša	Related
Marc De Mey	Related
Tijana Ružić	Related
Ann Dooms	Related

[163] T. Ružić, B. Cornelis, L. Platiša, A. Pižurica, A. Dooms, W. Philips, M. Martens, M. De Mey, and I. Daubechies: “Virtual restoration of the Ghent Altarpiece using crack detection and inpainting,” pp. 417–428 in Advanced concepts for intelligent vision systems: 13th international conference (Ghent, Belgium, 22–25 August 2011). Edited by J. Blanc-Talon, R. Kleihorst, W. Philips, D. Popescu, and P. Scheunders. Lecture Notes in Computer Science 6915. Springer (Berlin), 2011. incollection

In this paper, we present a new method for virtual restoration of digitized paintings, with the special focus on the Ghent Altarpiece (1432), one of Belgium’s greatest masterpieces. The goal of the work is to remove cracks from the digitized painting thereby approximating how the painting looked like before ageing for nearly 600 years and aiding art historical and palaeographical analysis. For crack detection, we employ a multiscale morphological approach, which can cope with greatly varying thickness of the cracks as well as with their varying intensities (from dark to the light ones). Due to the content of the painting (with extremely many fine details) and complex type of cracks (including inconsistent whitish clouds around them), the available inpainting methods do not provide satisfactory results on many parts of the painting. We show that patch-based methods outperform pixel-based ones, but leaving still much room for improvements in this application. We propose a new method for candidate patch selection, which can be combined with different patch-based inpainting methods to improve their performance in crack removal. The results demonstrate improved performance, with less artefacts and better preserved fine details.

Bruno Cornelis	Related
Wilfried Philips	Related
Paul Scheunders	Related
Aleksandra Pižurica	Related
Maximiliaan P. J. Martens	Related
Ljiljana Platiša	Related
Daniel C. Popescu	Related
Marc De Mey	Related
Richard Kleihorst	Related
Jacques Blanc-Talon	Related
Tijana Ružić	Related
Ann Dooms	Related

@incollection {key41995092,
	AUTHOR = {Ru\v{z}i\'c, Tijana and Cornelis, Bruno
		 and Plati\v{s}a, Ljiljana and Pi\v{z}urica,
		 Aleksandra and Dooms, Ann and Philips,
		 Wilfried and Martens, Maximiliaan and
		 De Mey, Marc and Daubechies, Ingrid},
	TITLE = {Virtual restoration of the {G}hent {A}ltarpiece
		 using crack detection and inpainting},
	BOOKTITLE = {Advanced concepts for intelligent vision
		 systems: 13th international conference},
	EDITOR = {Blanc-Talon, Jacques and Kleihorst,
		 Richard and Philips, Wilfried and Popescu,
		 Dan and Scheunders, Paul},
	SERIES = {Lecture Notes in Computer Science},
	NUMBER = {6915},
	PUBLISHER = {Springer},
	ADDRESS = {Berlin},
	YEAR = {2011},
	PAGES = {417--428},
	DOI = {10.1007/978-3-642-23687-7_38},
	NOTE = {(Ghent, Belgium, 22--25 August 2011).},
	ISSN = {0302-9743},
	ISBN = {9783642236860},
}

[164] F. J. Simons, I. Loris, G. Nolet, I. C. Daubechies, S. Voronin, J. S. Judd, P. A. Vetter, J. Charléty, and C. Vonesch: “Solving or resolving global tomographic models with spherical wavelets, and the scale and sparsity of seismic heterogeneity,” Geophys. J. Int. 187 : 2 (November 2011), pp. 969–988. ArXiv 1104.3151 article

We propose a class of spherical wavelet bases for the analysis of geophysical models and for the tomographic inversion of global seismic data. Its multiresolution character allows for modelling with an effective spatial resolution that varies with position within the Earth. Our procedure is numerically efficient and can be implemented with parallel computing. We discuss two possible types of discrete wavelet transforms in the angular dimension of the cubed sphere. We describe benefits and drawbacks of these constructions and apply them to analyse the information in two published seismic wave speed models of the mantle, using the statistics of wavelet coefficients across scales. The localization and sparsity properties of wavelet bases allow finding a sparse solution to inverse problems by iterative minimization of a combination of the \( \ell_2 \) norm of the data residuals and the \( \ell_1 \) norm of the model wavelet coefficients. By validation with realistic synthetic experiments we illustrate the likely gains from our new approach in future inversions of finite-frequency seismic data.

Ignace Loris	Related
Jean Charléty	Related
J. Stephen Judd	Related
Frederik J. Simons	Related
Philip Adam Vetter	Related
Cédric Vonesch	Related
Sergey Voronin	Related
Auguste (Guust) Nolet	Related

[165] F. J. Simons, I. Loris, E. Brevdo, and I. C. Daubechies: “Wavelets and wavelet-like transforms on the sphere and their application to geophysical data inversion,” pp. electronic only, p.81380X in Wavelets and sparsity XIV (San Diego, CA, 21–24 August 2011). Edited by M. Papadakis, D. Van De Ville, and V. K. Goyal. Proceedings of SPIE 8138. SPIE (Bellingham, WA), 2011. ArXiv 1109.1718 incollection

Complete Bibliography