Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

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.
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?)


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.