A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems

Brugiapaglia, Simone; Nobile, Fabio; Micheletti, Stefano; Perotto, Simona

doi:10.1090/mcom/3209

A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems
HTML articles powered by AMS MathViewer

by Simone Brugiapaglia, Fabio Nobile, Stefano Micheletti and Simona Perotto PDF

Math. Comp. 87 (2018), 1-38 Request permission

Abstract:

We present a theoretical analysis of the CORSING (COmpRessed SolvING) method for the numerical approximation of partial differential equations based on compressed sensing. In particular, we show that the best $s$-term approximation of the weak solution of a PDE with respect to a system of $N$ trial functions, can be recovered via a Petrov-Galerkin approach using $m \ll N$ test functions. This recovery is guaranteed if the local $a$-coherence associated with the bilinear form and the selected trial and test bases fulfills suitable decay properties. The fundamental tool of this analysis is the restricted inf-sup property, i.e., a combination of the classical inf-sup condition and the well-known restricted isometry property of compressed sensing.

References

B. Adcock, Infinite-dimensional compressed sensing and function interpolation, arXiv preprint arXiv:1509.06073 (2015).
B. Adcock, Infinite-dimensional $\ell ^1$ minimization and function approximation from pointwise data, arXiv preprint arXiv:1503.02352 (2015).
B. Adcock and A.C. Hansen, Generalized Sampling and Infinite-Dimensional Compressed Sensing, Found. Comput. Math. (2015), 1–61 (English).
B. Adcock, A.C. Hansen, C. Poon, and B. Roman, Breaking the coherence barrier: A new theory for compressed sensing, arXiv preprint arXiv:1302.0561 (2013).
Rudolf Ahlswede and Andreas Winter, Strong converse for identification via quantum channels, IEEE Trans. Inform. Theory 48 (2002), no. 3, 569–579. MR 1889969, DOI 10.1109/18.985947
A. K. Aziz (ed.), The mathematical foundations of the finite element method with applications to partial differential equations, Academic Press, New York-London, 1972. MR 0347104
J.-L. Bouchot, B. Bykowski, H. Rauhut, and C. Schwab, Compressed sensing Petrov-Galerkin approximations for parametric PDEs, Sampling Theory and Applications (SampTA), 2015 International Conference on, IEEE, 2015, pp. 528–532.
Jean-Luc Bouchot, Simon Foucart, and Pawel Hitczenko, Hard thresholding pursuit algorithms: number of iterations, Appl. Comput. Harmon. Anal. 41 (2016), no. 2, 412–435. MR 3534445, DOI 10.1016/j.acha.2016.03.002
Franco Brezzi and Michel Fortin, Mixed and hybrid finite element methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. MR 1115205, DOI 10.1007/978-1-4612-3172-1
S. Brugiapaglia, COmpRessed SolvING: Sparse Approximation of PDEs Based on Compressed Sensing, Ph.D. thesis, MOX - Politecnico di Milano, 2016.
S. Brugiapaglia, S. Micheletti, and S. Perotto, Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing, Comput. Math. Appl. 70 (2015), no. 6, 1306–1335. MR 3391114, DOI 10.1016/j.camwa.2015.07.015
Emmanuel J. Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489–509. MR 2236170, DOI 10.1109/TIT.2005.862083
Scott Shaobing Chen, David L. Donoho, and Michael A. Saunders, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput. 20 (1998), no. 1, 33–61. MR 1639094, DOI 10.1137/S1064827596304010
Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 57518, DOI 10.1214/aoms/1177729330
Abdellah Chkifa, Albert Cohen, Giovanni Migliorati, Fabio Nobile, and Raul Tempone, Discrete least squares polynomial approximation with random evaluations—application to parametric and stochastic elliptic PDEs, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 3, 815–837. MR 3342229, DOI 10.1051/m2an/2014050
Ole Christensen, An introduction to frames and Riesz bases, 2nd ed., Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, [Cham], 2016. MR 3495345, DOI 10.1007/978-3-319-25613-9
A. Cohen, W. Dahmen, and R. DeVore, Orthogonal matching pursuit under the restricted isometry property, Constr. Approx. (2015), 1–15.
Albert Cohen, Mark A. Davenport, and Dany Leviatan, On the stability and accuracy of least squares approximations, Found. Comput. Math. 13 (2013), no. 5, 819–834. MR 3105946, DOI 10.1007/s10208-013-9142-3
Wolfgang Dahmen, Wavelet and multiscale methods for operator equations, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 55–228. MR 1489256, DOI 10.1017/S0962492900002713
Wolfgang Dahmen, Chunyan Huang, Christoph Schwab, and Gerrit Welper, Adaptive Petrov-Galerkin methods for first order transport equations, SIAM J. Numer. Anal. 50 (2012), no. 5, 2420–2445. MR 3022225, DOI 10.1137/110823158
Marta D’Elia and Max Gunzburger, The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator, Comput. Math. Appl. 66 (2013), no. 7, 1245–1260. MR 3096457, DOI 10.1016/j.camwa.2013.07.022
Ronald A. DeVore, Nonlinear approximation, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 51–150. MR 1689432, DOI 10.1017/S0962492900002816
David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289–1306. MR 2241189, DOI 10.1109/TIT.2006.871582
Alireza Doostan and Houman Owhadi, A non-adapted sparse approximation of PDEs with stochastic inputs, J. Comput. Phys. 230 (2011), no. 8, 3015–3034. MR 2774328, DOI 10.1016/j.jcp.2011.01.002
Alexandre Ern and Jean-Luc Guermond, Theory and practice of finite elements, Applied Mathematical Sciences, vol. 159, Springer-Verlag, New York, 2004. MR 2050138, DOI 10.1007/978-1-4757-4355-5
Simon Foucart, Hard thresholding pursuit: an algorithm for compressive sensing, SIAM J. Numer. Anal. 49 (2011), no. 6, 2543–2563. MR 2873246, DOI 10.1137/100806278
Simon Foucart and Holger Rauhut, A mathematical introduction to compressive sensing, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013. MR 3100033, DOI 10.1007/978-0-8176-4948-7
Felix Krahmer and Rachel Ward, Stable and robust sampling strategies for compressive imaging, IEEE Trans. Image Process. 23 (2014), no. 2, 612–622. MR 3159526, DOI 10.1109/TIP.2013.2288004
S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process. 41 (1993), no. 12, 3397–3415.
B. K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24 (1995), no. 2, 227–234. MR 1320206, DOI 10.1137/S0097539792240406
D. Needell and J. A. Tropp, CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26 (2009), no. 3, 301–321. MR 2502366, DOI 10.1016/j.acha.2008.07.002
Jindřich Nečas, Sur une méthode pour résoudre les équations aux dérivées partielles du type elliptique, voisine de la variationnelle, Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3) 16 (1962), 305–326 (French). MR 163054
Ricardo H. Nochetto, Kunibert G. Siebert, and Andreas Veeser, Theory of adaptive finite element methods: an introduction, Multiscale, nonlinear and adaptive approximation, Springer, Berlin, 2009, pp. 409–542. MR 2648380, DOI 10.1007/978-3-642-03413-8_{1}2
Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, 1993, pp. 40–44.
Ji Peng, Jerrad Hampton, and Alireza Doostan, A weighted $\ell _1$-minimization approach for sparse polynomial chaos expansions, J. Comput. Phys. 267 (2014), 92–111. MR 3183283, DOI 10.1016/j.jcp.2014.02.024
Igor Podlubny, Aleksei Chechkin, Tomas Skovranek, YangQuan Chen, and Blas M. Vinagre Jara, Matrix approach to discrete fractional calculus. II. Partial fractional differential equations, J. Comput. Phys. 228 (2009), no. 8, 3137–3153. MR 2509311, DOI 10.1016/j.jcp.2009.01.014
Alfio Quarteroni and Alberto Valli, Numerical approximation of partial differential equations, Springer Series in Computational Mathematics, vol. 23, Springer-Verlag, Berlin, 1994. MR 1299729
Holger Rauhut, Compressive sensing and structured random matrices, Theoretical foundations and numerical methods for sparse recovery, Radon Ser. Comput. Appl. Math., vol. 9, Walter de Gruyter, Berlin, 2010, pp. 1–92. MR 2731597, DOI 10.1515/9783110226157.1
Holger Rauhut and Christoph Schwab, Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations, Math. Comp. 86 (2017), no. 304, 661–700. MR 3584544, DOI 10.1090/mcom/3113
Holger Rauhut and Rachel Ward, Sparse Legendre expansions via $\ell _1$-minimization, J. Approx. Theory 164 (2012), no. 5, 517–533. MR 2903116, DOI 10.1016/j.jat.2012.01.008
Holger Rauhut and Rachel Ward, Interpolation via weighted $\ell _1$ minimization, Appl. Comput. Harmon. Anal. 40 (2016), no. 2, 321–351. MR 3440176, DOI 10.1016/j.acha.2015.02.003
B. Roman, A. Bastounis, B. Adcock, and A.C. Hansen, On fundamentals of models and sampling in compressed sensing, Preprint (2015).
R. Rubinstein, Omp-Box v10, http://www.cs.technion.ac.il/\textasciitilde ronrubin/software.html, 2009.
R. Rubinstein, M. Zibulevsky, and M. Elad, Efficient implementation of the k-SVD algorithm using batch orthogonal matching pursuit, Tech. Report CS-2008-08, Technion, Computer Science Department, 2008.
Khachik Sargsyan, Cosmin Safta, Habib N. Najm, Bert J. Debusschere, Daniel Ricciuto, and Peter Thornton, Dimensionality reduction for complex models via Bayesian compressive sensing, Int. J. Uncertain. Quantif. 4 (2014), no. 1, 63–93. MR 3249677, DOI 10.1615/Int.J.UncertaintyQuantification.2013006821
V. N. Temlyakov, Nonlinear methods of approximation, Found. Comput. Math. 3 (2003), no. 1, 33–107. MR 1951502, DOI 10.1007/s102080010029
Joel A. Tropp, Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inform. Theory 50 (2004), no. 10, 2231–2242. MR 2097044, DOI 10.1109/TIT.2004.834793
Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389–434. MR 2946459, DOI 10.1007/s10208-011-9099-z
U. Trottenberg, C. W. Oosterlee, and A. Schüller, Multigrid, Academic Press, Inc., San Diego, CA, 2001. With contributions by A. Brandt, P. Oswald and K. Stüben. MR 1807961
X. Yang and G.E. Karniadakis, Reweighted $\ell _1$-minimization method for stochastic elliptic differential equations, J. Comput. Phys. 248 (2013), 87–108.
Harry Yserentant, On the multilevel splitting of finite element spaces, Numer. Math. 49 (1986), no. 4, 379–412. MR 853662, DOI 10.1007/BF01389538
Tong Zhang, Sparse recovery with orthogonal matching pursuit under RIP, IEEE Trans. Inform. Theory 57 (2011), no. 9, 6215–6221. MR 2857968, DOI 10.1109/TIT.2011.2162263