×

Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. (English) Zbl 1477.65197

The main concern of the authors is the numerical approximation of solutions to boundary value problems attached to PDEs, based on compressive sensing via the CORSING (COmpRessed SolvING) method. Actually they work on weak problems formulated in Hilbert spaces. The main idea of the compressed solving is to lighten the computational cost characterizing a Petrov-Galerkin discretization method, the so called curse of dimensionality, by reducing the dimension of the test space with respect to the trial space. In the present paper the authors provide a new analysis of the restricted isometry constants and null space property of matrices arising from random sampling in bounded Riesz systems. With this result they considerably improve the theoretical guarantees for the CORSING method.

MSC:

65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65K10 Numerical optimization and variational techniques
15B52 Random matrices (algebraic aspects)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adcock, B., Infinite-dimensional compressed sensing and function interpolation, Found. Comput. Math., 18, 3, 661-701 (2018) · Zbl 1396.41001
[2] Adcock, B.; Bao, A.; Brugiapaglia, S., Correcting for unknown errors in sparse high-dimensional function approximation, Numer. Math., 142, 3, 667-711 (2019) · Zbl 1415.65030
[3] Adcock, B.; Brugiapaglia, S.; Webster, C. G., Compressed sensing approaches for polynomial approximation of high-dimensional functions, (Compressed Sensing and Its Applications (2017), Springer), 93-124
[4] Adcock, B.; Hansen, A. C.; Poon, C.; Roman, B., Breaking the Coherence Barrier: A New Theory for Compressed Sensing, Forum Math. Sigma, vol. 5 (2017), Cambridge University Press · Zbl 1410.94030
[5] Alberti, G. S.; Santacesaria, M., Infinite dimensional compressed sensing from anisotropic measurements and applications to inverse problems in PDE, Appl. Comput. Harmon. Anal. (2019)
[6] Błasiok, J.; Lopatto, P.; Luh, K.; Marcinek, J.; Rao, S., An improved lower bound for sparse reconstruction from subsampled Hadamard matrices (2019), Preprint
[7] Boucheron, S.; Lugosi, G.; Massart, P., Concentration Inequalities (2013), Oxford University Press: Oxford University Press Oxford · Zbl 1279.60005
[8] Bouchot, J. L.; Rauhut, H.; Schwab, C., Multi-level compressive sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs (2017), Preprint
[9] Bourgain, J., An improved estimate in the restricted isometry problem, (Klartag, B.; Milman, E., Geometric Aspects of Functional Analysis. Geometric Aspects of Functional Analysis, Lect. Notes Math., vol. 2116 (2014), Springer International Publishing), 65-70 · Zbl 1323.46009
[10] Bourgain, J.; Dilworth, S.; Ford, K.; Konyagin, S.; Kutzarova, D., Explicit constructions of RIP matrices and related problems, Duke Math. J., 159, 1, 145-185 (2011) · Zbl 1236.94027
[11] Bousquet, Olivier, A Bennett concentration inequality and its application to suprema of empirical processes, C. R. Math., 334, 6, 495-500 (2002) · Zbl 1001.60021
[12] Brugiapaglia, S., COmpRessed SolvING: sparse approximation of PDEs based on compressed sensing (2016), MOX - Politecnico di Milano, PhD thesis
[13] Brugiapaglia, S., A compressive spectral collocation method for the diffusion equation under the restricted isometry property (2018), arXiv preprint
[14] Brugiapaglia, S.; Micheletti, S.; Nobile, F.; Perotto, S., Wavelet-Fourier CORSING techniques for multi-dimensional advection-diffusion-reaction equations, IMA J. Numer. Anal. (2020), in press
[15] Brugiapaglia, S.; Micheletti, S.; Perotto, S., Compressed solving: a numerical approximation technique for elliptic PDEs based on compressed sensing, Comput. Math. Appl., 70, 6, 1306-1335 (2015) · Zbl 1443.65313
[16] Brugiapaglia, S.; Nobile, F.; Micheletti, S.; Perotto, S., A theoretical study of COmpRessed SolvING for advection-diffusion-reaction problems, Math. Comput., 87, 309, 1-38 (2018) · Zbl 1376.65127
[17] Cai, T. T.; Zhang, A., Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inf. Theory, 60, 1, 122-132 (January 2014) · Zbl 1364.94114
[18] Candès, E. J.; Tao, T.; Romberg, J. K., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017
[19] Candes, E. J.; Tao, T., Decoding by linear programming, IEEE Trans. Inf. Theory, 51, 12, 4203-4215 (Dec 2005) · Zbl 1264.94121
[20] Candès, E. J.; Tao, T., Near optimal signal recovery from random projections: universal encoding strategies?, IEEE Trans. Inf. Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033
[21] Cheraghchi, M.; Guruswami, V.; Velingker, A., Restricted isometry of Fourier matrices and list decodability of random linear codes, SIAM J. Comput., 42, 5, 1888-1914 (2013) · Zbl 1321.94122
[22] Chkifa, A.; Dexter, N.; Tran, H.; Webster, C. G., Polynomial approximation via compressed sensing of high-dimensional functions on lower sets, Math. Comput., 87, 311, 1415-1450 (2018) · Zbl 1516.94010
[23] Christensen, O., An Introduction to Frames and Riesz Bases, Appl. Numer. Harmon. Anal. (2002), Birkhäuser: Birkhäuser Boston
[24] Cohen, A.; Dahmen, W.; DeVore, R., Orthogonal matching pursuit under the restricted isometry property, Constr. Approx., 45, 1, 113-127 (2017) · Zbl 1379.94014
[25] Dahmen, W., Multiscale and wavelet methods for operator equations, (Multiscale Problems and Methods in Numerical Simulations (2003), Springer), 31-96 · Zbl 1036.65095
[26] Dirksen, S.; Lecue, G.; Rauhut, H., On the gap between restricted isometry properties and sparse recovery conditions, IEEE Trans. Inf. Theory, 64, 8, 5478-5487 (2018) · Zbl 1401.94031
[27] Donoho, D. L., Compressed sensing, IEEE Trans. Inf. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[28] Doostan, A.; Owhadi, H., A non-adapted sparse approximation of PDEs with stochastic inputs, J. Comput. Phys., 230, 8, 3015-3034 (2011) · Zbl 1218.65008
[29] Foucart, S.; Rauhut, H., A mathematical introduction to compressive sensing, (Appl. Numer. Harmon. Anal. (2013), Birkhaüser) · Zbl 1315.94002
[30] Haviv, I.; Regev, O., The restricted isometry property for subsampled Fourier matrices, (Geometric Aspects of Functional Analysis (2017), Springer), 163-179 · Zbl 1379.46014
[31] Jokar, S.; Mehrmann, V.; Pfetsch, M. E.; Yserentant, H., Sparse approximate solution of partial differential equations, Appl. Numer. Math., 60, 4, 452-472 (2010) · Zbl 1220.65170
[32] Kabanava, M.; Rauhut, H., Analysis \(\ell^1\)-recovery with frames and Gaussian measurements, Acta Appl. Math., 140, 1, 173-195 (December 2015) · Zbl 1378.94008
[33] Kang, H.; Lai, M.-J.; Li, X., An economical representation of PDE solution by using compressive sensing approach, Comput. Aided Des., 115, 78-86 (2019)
[34] Krahmer, F.; Ward, R., New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 3, 1269-1281 (2011) · Zbl 1247.15019
[35] Krahmer, F.; Ward, R., Stable and robust sampling strategies for compressive imaging, IEEE Trans. Image Process., 23, 2, 612-622 (2014) · Zbl 1374.94181
[36] Ledoux, M.; Talagrand, M., Probability in Banach Spaces (1991), Springer-Verlag: Springer-Verlag Berlin · Zbl 0748.60004
[37] Mackey, A.; Schaeffer, H.; Osher, S., On the compressive spectral method, Multiscale Model. Simul., 12, 4, 1800-1827 (2014) · Zbl 1314.65152
[38] Mathelin, L.; Gallivan, K. A., A compressed sensing approach for partial differential equations with random input data, Commun. Comput. Phys., 12, 4, 919-954 (2012) · Zbl 1388.65018
[39] Oymak, S.; Recht, B.; Soltanolkotabi, M., Isometric sketching of any set via the restricted isometry property, Inf. Inference, 7, 4, 707-726 (2018) · Zbl 1473.60021
[40] Quarteroni, A.; Valli, A., Numerical Approximation of Partial Differential Equations, Springer Ser. Comput. Math., vol. 23 (2008), Springer-Verlag: Springer-Verlag Berlin · Zbl 1151.65339
[41] Rauhut, H., Random sampling of sparse trigonometric polynomials, Appl. Comput. Harmon. Anal., 22, 1, 16-42 (2007) · Zbl 1123.94004
[42] Rauhut, H.; Schwab, C., Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations, Math. Comput., 86, 304, 661-700 (2017) · Zbl 1358.65034
[43] Rauhut, H.; Ward, R., Sparse Legendre expansions via \(\ell_1\)-minimization, J. Approx. Theory, 164, 5, 517-533 (2012) · Zbl 1239.65018
[44] Rauhut, H.; Ward, R., Interpolation via weighted \(\ell^1\)-minimization, Appl. Comput. Harmon. Anal., 40, 2, 321-351 (2016) · Zbl 1333.41003
[45] Rudelson, M.; Vershynin, Roman, On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., 61, 1025-1045 (2008) · Zbl 1149.94010
[46] Rudelson, M.; Zhou, S., Reconstruction from anisotropic random measurements, (Conference on Learning Theory (2012)), 10.1-10.24
[47] Talagrand, M., Upper and Lower Bounds for Stochastic Processes: Modern Methods and Classical Problems, Vol. 60 (2014), Springer Science & Business Media · Zbl 1293.60001
[48] Tran, G.; Ward, R., Exact recovery of chaotic systems from highly corrupted data, Multiscale Model. Simul., 15, 3, 1108-1129 (2017)
[49] Urban, K., Wavelet Methods for Elliptic Partial Differential Equations (2009), Oxford University Press · Zbl 1158.65002
[50] Yan, L.; Guo, L.; Xiu, D., Stochastic collocation algorithms using \(\ell_1\)-minimization, Int. J. Uncertain. Quantificat., 2, 3 (2012) · Zbl 1291.65024
[51] Yang, X.; Karniadakis, G. E., Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations, J. Comput. Phys., 248, 87-108 (2013) · Zbl 1349.60113
[52] Zhang, T., Sparse recovery with orthogonal matching pursuit under RIP, IEEE Trans. Inf. Theory, 57, 9, 6215-6221 (2011) · Zbl 1365.94091
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.