Scattering in Flatland: Efficient Representations via Wave Atoms

Laurent Demanet, Lexing Ying

TL;DR

This paper introduces a novel method for efficiently representing and solving acoustic scattering problems in 2D. By using "wave atoms," a specialized basis, they can compress complex integral operators into sparse matrices, significantly reducing computational cost. This approach offers a theoretical guarantee of efficiency and is demonstrated to be effective through numerical experiments.

What Problem Does This Paper Address?

Solving acoustic scattering problems often involves dealing with integral equations that have "oscillatory kernels." These kernels, when discretized, lead to dense matrices that are computationally expensive to work with, especially for large problems (high wave number $k$). Traditional methods like local Fourier bases or wavelet packets have limitations in terms of efficiency or theoretical guarantees. This paper aims to bridge this gap by proposing a new representation for these kernels that is both theoretically sound and computationally efficient, particularly for applications requiring repeated solutions with varying boundary conditions.

Methods

The core of this paper lies in the use of wave atoms as a basis for representing the integral operators associated with acoustic scattering. Wave atoms are a type of time-frequency localized basis that exhibit a unique "parabolic scaling" property, allowing them to efficiently capture oscillatory patterns. The authors leverage the "non-standard form" of wave atom expansion, where the operator is represented by its coefficients in this basis. By thresholding small coefficients to zero, they achieve a sparse representation of the operator. This sparse representation then allows for significantly faster application of the operator, which is crucial for iterative solvers. The paper provides a theoretical framework proving that this wave atom representation can compress the operators into matrices with a number of non-negligible entries that grows favorably with the wave number $k$ and the desired accuracy $\epsilon$.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and numerical experiments using synthetic geometric objects (ellipse, kite-shaped object, star-shaped object) as scatterers.

Key Insights and Ideas

  • Wave atoms offer a superior representation for oscillatory kernels: Unlike standard wavelets or wavelet packets, wave atoms possess a sharp time-frequency localization and a parabolic scaling that make them particularly well-suited for capturing the behavior of oscillatory kernels in scattering problems.
  • Non-standard wave atom expansion leads to provable sparsity: The paper demonstrates that by using the non-standard wave atom representation, the integral operators can be compressed into matrices with a number of significant coefficients that scales favorably with the problem size ($k$) and desired accuracy ($\epsilon$). This is a key theoretical contribution.
  • Efficiency for repeated solves: The ability to create a sparse representation of the operator means that once this representation is built, applying it to different right-hand sides (e.g., different incoming waves) becomes computationally very cheap. This is highly beneficial for applications like radar cross-section computation.
  • Adaptive strategies are not always necessary: The proposed wave atom approach is non-adaptive, meaning it doesn't require a complex search for the "best" basis. This simplifies the implementation and provides a guaranteed good representation.

Key Results

The paper presents theoretical results showing that the acoustic single-layer and double-layer potentials can be represented by matrices with $O(k^{1+\delta})$ non-negligible entries for any $\delta > 0$, with an accuracy $\epsilon$. This is a significant improvement over dense matrices which would require $O(k^2)$ entries. Numerical experiments on various geometric shapes (ellipse, kite, star) confirm these theoretical predictions. The tables presented show that the number of non-negligible coefficients grows slowly with $k$ and is relatively insensitive to the accuracy $\epsilon$, while the estimated operator error is close to the desired accuracy.

Limitations and Future Work

  • Smoothness assumption: The theoretical results rely on assumptions about the smoothness and geometric regularity of the scatterer.
  • Logarithmic factors: The authors mention that it is not known if factors like $k^{1/\infty}$ and $\epsilon^{-1/\infty}$ in their bounds could be replaced by simpler logarithmic factors.
  • Numerical experiments: While the numerical experiments support the theory, they are conducted on specific shapes and wave numbers. Further testing on more complex geometries and a wider range of parameters would be valuable.
  • Future work: The authors suggest that this wave atom representation could be of interest for applications where the same scattering problem needs to be solved for many boundary conditions, such as radar cross-section computation. They also hint at potential extensions to 3D problems.

Summary updated

Abstract

This paper presents a numerical compression strategy for the boundary integral equation of acoustic scattering in two dimensions. These equations have oscillatory kernels that we represent in a basis of wave atoms, and compress by thresholding the small coefficients to zero.This phenomenon was perhaps first observed in 1993 by Bradie, Coifman, and Grossman, in the context of local Fourier bases (Bradie et al. in Appl. Comput. Harmon. Anal. 1:94–99, 1993). Their results have since then been extended in various ways. The purpose of this paper is to bridge a theoretical gap and prove that a well-chosen fixed expansion, the non-standard wave atom form, provides a compression of the acoustic single- and double-layer potentials with wave number k as O(k)-by-O(k) matrices with C ε δ k 1+δ non-negligible entries, with δ>0 arbitrarily small, and ε the desired accuracy. The argument assumes smooth, separated, and not necessarily convex scatterers in two dimensions. The essential features of wave atoms that allow this result to be written as a theorem are a sharp time-frequency localization that wavelet packets do not obey, and a parabolic scaling (wavelength of the wave packet) ∼ (essential diameter)2. Numerical experiments support the estimate and show that this wave atom representation may be of interest for applications where the same scattering problem needs to be solved for many boundary conditions, for example, the computation of radar cross sections.
BibTeX
@inproceedings{demanet2010scattering,
  author = {Laurent Demanet and Lexing Ying},
  title = {{Scattering in Flatland: Efficient Representations via Wave Atoms}},
  booktitle = {Found. Comput. Math},
  year = {2010},
  url = {https://openreview.net/forum?id=XYz1VFYtjTzt},
}
Figure