Nonlinear Solution of Linear Inverse Problems by Wavelet–Vaguelette Decomposition

David L. DonohoApplied and Computational Harmonic Analysis 1995 · DOI

TL;DR

This paper introduces the Wavelet-Vaguelette Decomposition (WVD) as a powerful alternative to traditional Singular Value Decomposition (SVD) for solving ill-posed linear inverse problems. The WVD, combined with nonlinear shrinkage of its coefficients, achieves optimal estimation rates, particularly for spatially inhomogeneous objects, outperforming linear methods like SVD.

What Problem Does This Paper Address?

Many scientific fields, from medical imaging to astronomy, rely on solving linear inverse problems. These problems are often "ill-posed," meaning that small errors in the observed data can lead to large errors in the recovered solution. Traditional methods like Singular Value Decomposition (SVD) are widely used but struggle with recovering spatially inhomogeneous objects. The authors aim to develop a new method that can handle these challenges more effectively, achieving optimal recovery rates even when the object's properties vary significantly across space.

Methods

The core of the paper is the Wavelet-Vaguelette Decomposition (WVD). This is a generalization of the SVD that leverages orthonormal wavelet bases. Instead of decomposing the operator itself (like SVD), WVD decomposes both the operator and the function space in a way that allows for simultaneous "diagonalization."

The key steps involve:

  • Wavelet Bases: Using orthonormal wavelet bases (like Daubechies wavelets) to represent functions efficiently, especially those with localized features.
  • Vaguelettes: Introducing a related set of functions called "vaguelettes," which are nearly orthogonal and play a role analogous to singular functions in SVD.
  • WVD Construction: For specific classes of "homogeneous" linear operators (like integration, fractional integration, and the Radon transform), the paper shows how to construct a WVD. This involves finding specific wavelet and vaguelette bases that are "quasi-singular" with respect to the operator.
  • Nonlinear Shrinkage: The crucial step for solving the inverse problem is to apply nonlinear shrinkage (thresholding) to the WVD coefficients. This is analogous to "soft thresholding" in wavelet denoising.

The paper proves that this nonlinear WVD shrinkage approach can achieve the minimax rate of convergence for recovering objects in Besov spaces, which are well-suited to modeling spatially inhomogeneous functions. This is a significant theoretical advantage over linear methods, which cannot achieve these optimal rates for such function classes.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and optimality results, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • WVD as a Unified Framework: The WVD provides a powerful framework that simultaneously diagonalizes the linear operator and the function space, offering a more holistic approach than SVD.
  • Vaguelettes are Key: The introduction of vaguelettes, which are closely related to wavelets but adapted to the operator, is crucial for constructing the WVD.
  • Nonlinear Shrinkage is Optimal: The paper strongly advocates for nonlinear shrinkage (thresholding) of WVD coefficients. This is not just a heuristic but is proven to be essential for achieving optimal estimation rates, especially for complex, spatially varying objects.
  • Limitations of Linear Methods: The paper clearly demonstrates that traditional linear methods, including SVD-based approaches, are fundamentally suboptimal for recovering spatially inhomogeneous functions, particularly those belonging to Besov spaces with $p < 2$.
  • "Almost Orthogonality" is Sufficient: The WVD relies on "near-orthogonality" of vaguelette systems, not strict orthogonality, which is a more flexible condition and allows for broader applicability.

Key Results

  • Optimal Recovery Rates: The WVD with nonlinear shrinkage achieves the minimax rate of convergence for recovering functions in Besov spaces, including those modeling spatial inhomogeneity.
  • Suboptimality of Linear Methods: Linear methods are shown to be suboptimal for recovering functions in Besov spaces with $p < 2$.
  • WVD for Specific Operators: The paper constructs WVDs for integration, fractional integration, and the Radon transform, demonstrating the practical applicability of the framework.
  • Theoretical Equivalence: The paper establishes theoretical equivalences between risks in different noise models (e.g., white noise, discrete white noise), simplifying the analysis of optimality.

Limitations and Future Work

  • Scale-Invariant Operators: The WVD approach is primarily developed for "scale-invariant" or "dilation-homogeneous" operators. The authors acknowledge that it might not directly apply to problems with a "sharp scale preference" (e.g., convolution with a boxcar kernel).
  • Generalization to Inhomogeneous Operators: While the paper touches upon inhomogeneous operators and bases, a full treatment is not provided.
  • Empirical Validation: The paper is heavily theoretical. Future work would involve applying these methods to real-world datasets and comparing their performance empirically against existing methods.
  • Specific Applications: The paper outlines the theoretical framework and optimality results. Future work would focus on applying these techniques to specific scientific problems where these types of inverse problems arise.

Summary updated

BibTeX
@inproceedings{donoho1995nonlinear,
  author = {David L. Donoho},
  title = {{Nonlinear Solution of Linear Inverse Problems by Wavelet–Vaguelette Decomposition}},
  booktitle = {Applied and Computational Harmonic Analysis},
  year = {1995},
  doi = {10.1006/acha.1995.1008},
}
Figure