Compressive wave computation

This paper presents a method for computing the solution to the time-dependent wave equation from the knowledge of a largely incomplete set of eigenfunctions of the Helmholtz operator, chosen at random. While a linear superposition of eigenfunctions can fail to properly synthesize the solution if a single term is missing, it is shown that solving a sparsity-promoting ℓ 1 minimization problem can vastly enhance the quality of recovery. This phenomenon may be seen as “compressive sampling in the Helmholtz domain.” An error bound is formulated for the one-dimensional wave equation with coefficients of small bounded variation. Under suitable assumptions, it is shown that the number of eigenfunctions needed to evolve a sparse wavefield defined on N points, accurately with very high probability, is bounded by C()logNloglogN where C(η) is related to the desired accuracy η and can be made to grow at a much slower rate than N when the solution is sparse. To the authors’ knowledge, the partial differential equation estimates that underlie this result are new and may be of independent mathematical interest. They include an L [superscript 1] estimate for the wave equation, an L [infinity symbol]−L[superscript 2] estimate of the extension of eigenfunctions, and a bound for eigenvalue gaps in Sturm–Liouville problems. In practice, the compressive strategy is highly parallelizable, and may eventually lead to memory savings for certain inverse problems involving the wave equation. Numerical experiments illustrate these properties in one spatial dimension.National Science Foundation (U.S.