On the Compressive Spectral Method

The authors of [Proc. Natl. Acad. Sci. USA, 110 (2013), pp. 6634--6639] proposed sparse Fourier domain approximation of solutions to multiscale PDE problems by soft thresholding. We show here that the method enjoys a number of desirable numerical and analytic properties, including convergence for linear PDEs and a modified equation resulting from the sparse approximation. We also extend the method to solve elliptic equations and introduce sparse approximation of differential operators in the Fourier domain. The effectiveness of the method is demonstrated on homogenization examples, where its complexity is dependent only on the sparsity of the problem and constant in many cases.