Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Authors: Abdellah Chkifa, Nick Dexter, Hoang Tran and Clayton G. Webster
Journal: Math. Comp. 87 (2018), 1415-1450
MSC (2010): Primary 35R60, 52C17, 94A08, 94A12, 15B52; Secondary 60H25, 62M40, 68W20, 03D32, 11M50
DOI: https://doi.org/10.1090/mcom/3272
Published electronically: September 19, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] B. Adcock, Infinite-dimensional compressed sensing and function interpolation, preprint (2015).
  • [2] B. Adcock, Infinite-dimensional $ \ell _1$ minimization and function approximation from pointwise data, preprint (2015).
  • [3] 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, https://doi.org/10.1016/j.camwa.2013.03.004
  • [4] Thomas Blumensath and Mike E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27 (2009), no. 3, 265-274. MR 2559726, https://doi.org/10.1016/j.acha.2009.04.002
  • [5] 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, https://doi.org/10.1007/978-3-319-09477-9_5
  • [6] 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, https://doi.org/10.1109/TIT.2005.862083
  • [7] 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
  • [8] 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, https://doi.org/10.1016/j.jco.2015.09.001
  • [9] 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.
  • [10] 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, https://doi.org/10.1051/m2an/2014050
  • [11] 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, https://doi.org/10.1007/s10208-013-9154-z
  • [12] 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. MR 3298364, https://doi.org/10.1016/j.matpur.2014.04.009
  • [13] 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, https://doi.org/10.1007/s10208-013-9142-3
  • [14] Albert Cohen and Ronald DeVore, Approximation of high-dimensional parametric PDEs, Acta Numer. 24 (2015), 1-159. MR 3349307, https://doi.org/10.1017/S0962492915000033
  • [15] 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, https://doi.org/10.1142/S0219530511001728
  • [16] 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.
  • [17] David L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. MR 2241189, https://doi.org/10.1109/TIT.2006.871582
  • [18] 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, https://doi.org/10.1016/j.jcp.2011.01.002
  • [19] 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, https://doi.org/10.1007/978-1-4614-0772-0_5
  • [20] Simon Foucart and Holger Rauhut, A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, New York, 2013. MR 3100033
  • [21] 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, https://doi.org/10.1109/TIT.2011.2167214
  • [22] Roger G. Ghanem and Pol D. Spanos, Stochastic Finite Elements: A Spectral Approach, Springer-Verlag, New York, 1991. MR 1083354
  • [23] 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, https://doi.org/10.1017/S0962492914000075
  • [24] 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, https://doi.org/10.1016/j.jcp.2014.09.019
  • [25] 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.
  • [26] 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, https://doi.org/10.1142/S0219530512500145
  • [27] Wassily Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13-30. MR 0144363
  • [28] J. Jo, Iterative hard thresholding for weighted sparse approximation, arXiv:1312.3582 (2013).
  • [29] 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, https://doi.org/10.1007/s00365-015-9299-x
  • [30] 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, https://doi.org/10.4208/cicp.151110.090911a
  • [31] Akil Narayan and Tao Zhou, Stochastic collocation on unstructured multivariate meshes, Commun. Comput. Phys. 18 (2015), no. 1, 1-36. MR 3371550, https://doi.org/10.4208/cicp.020215.070515a
  • [32] 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, https://doi.org/10.1137/070680540
  • [33] 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, https://doi.org/10.1137/060663660
  • [34] 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, https://doi.org/10.1016/j.jcp.2015.12.049
  • [35] 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, https://doi.org/10.1016/j.jcp.2014.02.024
  • [36] 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, https://doi.org/10.1137/090774707
  • [37] 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, https://doi.org/10.1515/9783110226157.1
  • [38] Holger Rauhut, Reinhold Schneider, and Željka Stojanac, Low rank tensor recovery via iterative hard thresholding, Linear Algebra Appl. 523 (2017), 220-262. MR 3624675, https://doi.org/10.1016/j.laa.2017.02.028
  • [39] 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, https://doi.org/10.1090/mcom/3113
  • [40] Holger Rauhut and Rachel Ward, Sparse Legendre expansions via $ \ell_1$-minimization, J. Approx. Theory 164 (2012), no. 5, 517-533. MR 2903116, https://doi.org/10.1016/j.jat.2012.01.008
  • [41] Holger Rauhut and Rachel Ward, Interpolation via weighted $ \ell_1$ minimization, Appl. Comput. Harmon. Anal. 40 (2016), no. 2, 321-351. MR 3440176, https://doi.org/10.1016/j.acha.2015.02.003
  • [42] 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, https://doi.org/10.1002/cpa.20227
  • [43] 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.
  • [44] 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.
  • [45] 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, https://doi.org/10.1137/080714488
  • [46] 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, https://doi.org/10.1016/S0045-7825(02)00421-8
  • [47] 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, https://doi.org/10.1615/ Int.J.UncertaintyQuantification.2012003925
  • [48] X. Yang and G. E. Karniadakis, Reweighted $ \ell _1$-minimization method for stochastic elliptic differential equations, Journal of Computational Physics 248 (2013), 87-108.
  • [49] 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 35R60, 52C17, 94A08, 94A12, 15B52, 60H25, 62M40, 68W20, 03D32, 11M50

Retrieve articles in all journals with MSC (2010): 35R60, 52C17, 94A08, 94A12, 15B52, 60H25, 62M40, 68W20, 03D32, 11M50


Additional Information

Abdellah Chkifa
Affiliation: Department of Computational and Applied Mathematics, Oak Ridge National Laboratory, 1 Bethel Valley Road, P.O. Box 2008, Oak Ridge, Tennessee 37831-6164
Email: chkifam@ornl.gov

Nick Dexter
Affiliation: Department of Mathematics, University of Tennessee, Knoxville, Tennessee 37996
Email: ndexter@utk.edu

Hoang Tran
Affiliation: Department of Computational and Applied Mathematics, Oak Ridge National Laboratory, 1 Bethel Valley Road, P.O. Box 2008, Oak Ridge, Tennessee 37831-6164
Email: tranha@ornl.gov

Clayton G. Webster
Affiliation: Department of Mathematics, University of Tennessee, Knoxville, Tennessee 37996 – and – Department of Computational and Applied Mathematics, Oak Ridge National Laboratory, 1 Bethel Valley Road, P.O. Box 2008, Oak Ridge, Tennessee 37831-6164
Email: webstercg@math.utk.edu

DOI: https://doi.org/10.1090/mcom/3272
Keywords: Compressed sensing, high-dimensional methods, polynomial approximation, convex optimization, downward closed (lower) sets
Received by editor(s): February 17, 2016
Received by editor(s) in revised form: November 8, 2016
Published electronically: September 19, 2017
Additional Notes: This material is based upon work supported in part by: the U.S. Defense Advanced Research Projects Agency, Defense Sciences Office under contract and award numbers HR0011619523 and 1868-A017-15; the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Applied Mathematics program under contract number ERKJ259; and the Laboratory Directed Research and Development program at the Oak Ridge National Laboratory, which is operated by UT-Battelle, LLC., for the U.S. Department of Energy under Contract DE-AC05-00OR22725.

American Mathematical Society