Polynomial approximation via compressed sensing of high-dimensional functions on lower sets

Chkifa, Abdellah; Dexter, Nick; Tran, Hoang; Webster, Clayton

doi:10.1090/mcom/3272

Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
HTML articles powered by AMS MathViewer

by Abdellah Chkifa, Nick Dexter, Hoang Tran and Clayton G. Webster PDF

Math. Comp. 87 (2018), 1415-1450 Request permission

Abstract:

This work proposes and analyzes a compressed sensing approach to polynomial approximation of complex-valued functions in high dimensions. In this context, the target function is often smooth and characterized by a rapidly decaying orthonormal expansion, whose most important terms are captured by a lower (or downward closed) set. Motivated by this fact, we present an innovative weighted $\ell _1$-minimization procedure with a precise choice of weights for imposing the downward closed preference. Theoretical results reveal that our computational approaches possess a provably reduced sample complexity compared to existing compressed sensing techniques presented in the literature. In addition, the recovery of the corresponding best approximation using these methods is established through an improved bound for the restricted isometry property. Our analysis represents an extension of the approach for Hadamard matrices by J. Bourgain [An improved estimate in the restricted isometry problem, Lecture Notes in Math., vol. 216, Springer, 2014, pp. 65–70] to the general bounded orthonormal systems, quantifies the dependence of sample complexity on the successful recovery probability, and provides an estimate on the number of measurements with explicit constants. Numerical examples are provided to support the theoretical results and demonstrate the computational efficiency of the novel weighted $\ell _1$-minimization strategy.

References

B. Adcock, Infinite-dimensional compressed sensing and function interpolation, preprint (2015).
B. Adcock, Infinite-dimensional $\ell _1$ minimization and function approximation from pointwise data, preprint (2015).
Joakim Beck, Fabio Nobile, Lorenzo Tamellini, and Raúl Tempone, Convergence of quasi-optimal stochastic Galerkin methods for a class of PDES with random coefficients, Comput. Math. Appl. 67 (2014), no. 4, 732–751. MR 3163876, DOI 10.1016/j.camwa.2013.03.004
Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 265–274. MR 2559726, DOI 10.1016/j.acha.2009.04.002
Jean Bourgain, An improved estimate in the restricted isometry problem, Geometric aspects of functional analysis, Lecture Notes in Math., vol. 2116, Springer, Cham, 2014, pp. 65–70. MR 3364679, DOI 10.1007/978-3-319-09477-9_{5}
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
Mahdi Cheraghchi, Venkatesan Guruswami, and Ameya Velingker, Restricted isometry of Fourier matrices and list decodability of random linear codes, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2012, pp. 432–442. MR 3186765
Alexey Chernov and Dinh Dũng, New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness, J. Complexity 32 (2016), no. 1, 92–121. MR 3424640, DOI 10.1016/j.jco.2015.09.001
A. Chkifa, A. Cohen, R. DeVore, and C. Schwab, Sparse adaptive taylor approximation algorithms for parametric and stochastic elliptic pdes, Modél. Math. Anal. Numér. 47 (2013), no. 1, 253–280.
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
Abdellah Chkifa, Albert Cohen, and Christoph Schwab, High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs, Found. Comput. Math. 14 (2014), no. 4, 601–633. MR 3230010, DOI 10.1007/s10208-013-9154-z
Abdellah Chkifa, Albert Cohen, and Christoph Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs, J. Math. Pures Appl. (9) 103 (2015), no. 2, 400–428 (English, with English and French summaries). MR 3298364, DOI 10.1016/j.matpur.2014.04.009
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
Albert Cohen and Ronald DeVore, Approximation of high-dimensional parametric PDEs, Acta Numer. 24 (2015), 1–159. MR 3349307, DOI 10.1017/S0962492915000033
Albert Cohen, Ronald Devore, and Christoph Schwab, Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s, Anal. Appl. (Singap.) 9 (2011), no. 1, 11–47. MR 2763359, DOI 10.1142/S0219530511001728
A. Cohen, G. Migliorati, and F. Nobile, Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension, Constructive Approximation (2016), to appear.
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
Simon Foucart, Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants, Approximation theory XIII: San Antonio 2010, Springer Proc. Math., vol. 13, Springer, New York, 2012, pp. 65–77. MR 3026204, DOI 10.1007/978-1-4614-0772-0_{5}
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
Michael P. Friedlander, Hassan Mansour, Rayan Saab, and Özgür Yilmaz, Recovering compressively sampled signals using partial support information, IEEE Trans. Inform. Theory 58 (2012), no. 2, 1122–1134. MR 2918013, DOI 10.1109/TIT.2011.2167214
Roger G. Ghanem and Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag, New York, 1991. MR 1083354, DOI 10.1007/978-1-4612-3094-6
Max D. Gunzburger, Clayton G. Webster, and Guannan Zhang, Stochastic finite element methods for partial differential equations with random input data, Acta Numer. 23 (2014), 521–650. MR 3202242, DOI 10.1017/S0962492914000075
Jerrad Hampton and Alireza Doostan, Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies, J. Comput. Phys. 280 (2015), 363–386. MR 3273141, DOI 10.1016/j.jcp.2014.09.019
I. Haviv and O. Regev, The restricted isometry property of subsampled fourier matrices, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (2016), 288–297.
Viet Ha Hoang and Christoph Schwab, Regularity and generalized polynomial chaos approximation of parametric and random second-order hyperbolic partial differential equations, Anal. Appl. (Singap.) 10 (2012), no. 3, 295–326. MR 2948896, DOI 10.1142/S0219530512500145
Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30. MR 144363
J. Jo, Iterative hard thresholding for weighted sparse approximation, arXiv:1312.3582 (2013).
Thomas Kühn, Winfried Sickel, and Tino Ullrich, Approximation of mixed order Sobolev functions on the $d$-torus: asymptotics, preasymptotics, and $d$-dependence, Constr. Approx. 42 (2015), no. 3, 353–398. MR 3416161, DOI 10.1007/s00365-015-9299-x
L. Mathelin and K. A. Gallivan, A compressed sensing approach for partial differential equations with random input data, Commun. Comput. Phys. 12 (2012), no. 4, 919–954. MR 2913445, DOI 10.4208/cicp.151110.090911a
Akil Narayan and Tao Zhou, Stochastic collocation on unstructured multivariate meshes, Commun. Comput. Phys. 18 (2015), no. 1, 1–36. MR 3371550, DOI 10.4208/cicp.020215.070515a
F. Nobile, R. Tempone, and C. G. Webster, An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal. 46 (2008), no. 5, 2411–2442. MR 2421041, DOI 10.1137/070680540
F. Nobile, R. Tempone, and C. G. Webster, A sparse grid stochastic collocation method for partial differential equations with random input data, SIAM J. Numer. Anal. 46 (2008), no. 5, 2309–2345. MR 2421037, DOI 10.1137/060663660
Ji Peng, Jerrad Hampton, and Alireza Doostan, On polynomial chaos expansion via gradient-enhanced $\ell _1$-minimization, J. Comput. Phys. 310 (2016), 440–458. MR 3457977, DOI 10.1016/j.jcp.2015.12.049
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
Rodrigo B. Platte, Lloyd N. Trefethen, and Arno B. J. Kuijlaars, Impossibility of fast stable approximation of analytic functions from equispaced samples, SIAM Rev. 53 (2011), no. 2, 308–318. MR 2806639, DOI 10.1137/090774707
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, Reinhold Schneider, and Željka Stojanac, Low rank tensor recovery via iterative hard thresholding, Linear Algebra Appl. 523 (2017), 220–262. MR 3624675, DOI 10.1016/j.laa.2017.02.028
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
Mark Rudelson and Roman Vershynin, On sparse reconstruction from Fourier and Gaussian measurements, Comm. Pure Appl. Math. 61 (2008), no. 8, 1025–1045. MR 2417886, DOI 10.1002/cpa.20227
H. Tran, C. G. Webster, and G. Zhang, Analysis of quasi-optimal polynomial approximations for parameterized pdes with deterministic and stochastic coefficients, Numerische Mathematik (2016), to appear.
E. van den Berg and M. P. Friedlander, SPGL1: A solver for large-scale sparse reconstruction, June 2007, http://www.cs.ubc.ca/labs/scl/spgl1.
Ewout van den Berg and Michael P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput. 31 (2008/09), no. 2, 890–912. MR 2466141, DOI 10.1137/080714488
Dongbin Xiu and George Em Karniadakis, Modeling uncertainty in steady state diffusion problems via generalized polynomial chaos, Comput. Methods Appl. Mech. Engrg. 191 (2002), no. 43, 4927–4948. MR 1932024, DOI 10.1016/S0045-7825(02)00421-8
Liang Yan, Ling Guo, and Dongbin Xiu, Stochastic collocation algorithms using $\ell _1$-minimization, Int. J. Uncertain. Quantif. 2 (2012), no. 3, 279–293. MR 3044795, DOI 10.1615/Int.J.UncertaintyQuantification.2012003925
X. Yang and G. E. Karniadakis, Reweighted $\ell _1$-minimization method for stochastic elliptic differential equations, Journal of Computational Physics 248 (2013), 87–108.
X. Yu and S. Baek, Sufficient conditions on stable recovery of sparse signals with partial support information, IEEE Signal Processing Letters 20 (2013), no. 5, 539–542.