Emerging applications of geometric multiscale analysis

David L. DonohoarXiv 2002 · DOI · arXiv

Abstract

Classical multiscale analysis based on wavelets has achieved significant success in data compression, noise removal, and fast algorithms. However, wavelets are fundamentally adapted to point singularities. In higher dimensions, many phenomena exhibit intermediate-dimensional singularities, such as edges in images or filaments in point clouds. This paper explores the evolution of harmonic analysis toward Geometric Multiscale Analysis (GMA), focusing on architectures like ridgelets and curvelets that utilize anisotropic scaling to efficiently represent geometric structures.

Introduction

In the 1990s, wavelets revolutionized signal processing by providing a sparse representation for functions with point-like singularities. However, as David Donoho argued in his 2002 International Congress of Mathematicians plenary lecture, traditional wavelets encounter a "curse of dimensionality" when applied to 2D and 3D data. While they are "unreasonably effective" for 1D signals, they fail to capture the essential geometry of higher-dimensional objects, such as the smooth curves (edges) that dominate natural images.

Geometric Multiscale Analysis (GMA) represents a shift from isotropic scaling—where basis functions scale equally in all directions—to anisotropic scaling, which allows for "needle-like" structures that can align with the geometry of the data.

The Limitations of Isotropic Wavelets

The core challenge lies in the mathematical architecture of classical wavelets. Wavelets are isotropic; they scale like squares. This makes them ideal for representing isolated point singularities. However, a real-world 2D image is characterized by curvilinear singularities (edges). To a wavelet, an edge appears as a long sequence of independent point singularities. Consequently, representing even a simple smooth curve requires a vast number of wavelet coefficients, leading to inefficient compression and noisy reconstructions.

Donoho identifies the need for a new "intellectual patrimony" of architectures that can "see" geometry, specifically singularities of intermediate dimensions, such as lines in 2D or surfaces in 3D.

Architectures of Geometric Multiscale Analysis

The paper outlines two primary methodological paths for GMA:

1. Transform-Based GMA (The "Calderón" Path)

This approach focuses on directional wavelet transforms that utilize parabolic dilations:

  • Ridgelets: These are wavelets constant along lines, perfectly adapted to singularities that are globally flat (hyperplanes).
  • Curvelets: Recognizing that real-world edges are rarely perfectly straight, curvelets employ parabolic scaling. Unlike wavelets (where $width \approx length$), curvelets scale such that $width \approx length^2$. As these functions become smaller, they become increasingly directional and "needle-like," allowing them to align perfectly with the tangent of a smooth curve.
  • Directional Framelets: These provide a digital discretization that organizes data by orientation before location, improving the practical utility of the curvelet construction.

2. Combinatorial/Geometric GMA

Inspired by Peter Jones’ "Traveling Salesman" theorem, this approach uses anisotropic strips to measure the "flatness" of a set of points across different scales. This is particularly effective for detecting filaments or clusters buried in noisy point clouds, such as those found in astronomical data.

Theoretical Insights and Performance

The shift to GMA provides a massive jump in efficiency, often referred to as the "Sparsity Gap." For a function containing a $C^2$ smooth edge:

  • Wavelets yield an approximation error of $O(N^{-1})$.
  • Curvelets achieve an error of $O(N^{-2} \log^3 N)$.

This efficiency stems from Parabolic Scaling. The relationship $width \approx length^2$ is the unique scaling that allows a basis function to remain "flat" enough to match a curved edge at a specific scale. Furthermore, these directional molecules are invariant under smooth coordinate changes (diffeomorphism invariance), meaning the representation remains sparse even if the image is warped.

Beyond mathematics, Donoho suggests a biological connection: the human visual cortex (specifically the V1 region) may perform a directional transform based on parabolic scaling rather than simple Gabor or wavelet analysis.

Key Results and Applications

  1. Optimal Denoising: In the presence of white noise, curvelet-based thresholding recovers edges at a rate of $O(\epsilon^{4/3})$, significantly outperforming the $O(\epsilon)$ rate of traditional wavelets.
  2. Operator Sparsity: Fourier Integral Operators (FIOs), which are essential for seismic imaging and radar, are highly sparse in the curvelet domain. This allows for the development of fast algorithms for hyperbolic partial differential equations (PDEs).
  3. Nonlinear Approximation: Curvelet thresholding is proven to be nearly optimal for representing images with edges, establishing a new benchmark for image processing.

Conclusion and Future Outlook

While GMA offers a "new vista" for mathematical analysis, challenges remain. At the time of this lecture, digital implementations were in their infancy, and extending the robust 2D theory to 3D (for sheets and filaments) presented significant complexity. Nevertheless, GMA provides a powerful framework for defining functional spaces and representing complex operators, offering applied mathematicians, statisticians, and engineers a more sophisticated toolkit for the geometric nature of modern data.

Summary updated

Abstract

Classical multiscale analysis based on wavelets has a number of successful applications, e.g. in data compression, fast algorithms, and noise removal. Wavelets, however, are adapted to point singularities, and many phenomena in several variables exhibit intermediate-dimensional singularities, such as edges, filaments, and sheets. This suggests that in higher dimensions, wavelets ought to be replaced in certain applications by multiscale analysis adapted to intermediate-dimensional singularities. My lecture described various initial attempts in this direction. In particular, I discussed two approaches to geometric multiscale analysis originally arising in the work of Harmonic Analysts Hart Smith and Peter Jones (and others): (a) a directional wavelet transform based on parabolic dilations; and (b) analysis via anistropic strips. Perhaps surprisingly, these tools have potential applications in data compression, inverse problems, noise removal, and signal detection; applied mathematicians, statisticians, and engineers are eagerly pursuing these leads.
BibTeX
@misc{donoho2002emerging,
  author = {David L. Donoho},
  title = {{Emerging applications of geometric multiscale analysis}},
  year = {2002},
  eprint = {math/0212395},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/math/0212395},
  howpublished = {arXiv},
}
Figure