Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
On Efficient Algorithms for Computing Near-Best Polynomial Approximations to High-Dimensional, Hilbert-Valued Functions from Limited Samples
 
Ben Adcock Simon Fraser University, Burnaby, BC, Canada
Simone Brugiapaglia Concordia University, Montreal, QC, Canada
Nick Dexter Simon Fraser University, Burnaby, BC, Canada
Sebastian Moraga Simon Fraser University, Burnaby, BC, Canada
A publication of European Mathematical Society
Softcover ISBN:  978-3-98547-070-9
Product Code:  EMSMEM/13
List Price: $75.00
AMS Member Price: $60.00
Not yet published - Preorder Now!
Expected availability date: August 13, 2024
Please note AMS points can not be used for this product
Click above image for expanded view
On Efficient Algorithms for Computing Near-Best Polynomial Approximations to High-Dimensional, Hilbert-Valued Functions from Limited Samples
Ben Adcock Simon Fraser University, Burnaby, BC, Canada
Simone Brugiapaglia Concordia University, Montreal, QC, Canada
Nick Dexter Simon Fraser University, Burnaby, BC, Canada
Sebastian Moraga Simon Fraser University, Burnaby, BC, Canada
A publication of European Mathematical Society
Softcover ISBN:  978-3-98547-070-9
Product Code:  EMSMEM/13
List Price: $75.00
AMS Member Price: $60.00
Not yet published - Preorder Now!
Expected availability date: August 13, 2024
Please note AMS points can not be used for this product
  • Book Details
     
     
    Memoirs of the European Mathematical Society
    Volume: 132024; 112 pp
    MSC: Primary 65; Secondary 41

    Sparse polynomial approximation is an important tool for approximating high-dimensional functions from limited samples — a task commonly arising in computational science and engineering. Yet, it lacks a complete theory. There is a well-developed theory of best \(s\)-term polynomial approximation, which asserts exponential or algebraic rates of convergence for holomorphic functions.

    There are also increasingly mature methods such as (weighted) \(\ell^1\)-minimization for practically computing such approximations. However, whether these methods achieve the rates of the best \(s\)-term approximation is not fully understood. Moreover, these methods are not algorithms per se, since they involve exact minimizers of nonlinear optimization problems.

    This paper closes these gaps by affirmatively answering the following question: Are there robust, efficient algorithms for computing sparse polynomial approximations to finite- or infinite-dimensional, holomorphic and Hilbert-valued functions from limited samples that achieve the same rates as the best \(s\)-term approximation?

    The authors do so by introducing algorithms with exponential or algebraic convergence rates that are also robust to sampling, algorithmic and physical discretization errors. Their results involve several developments of existing techniques, including a new restarted primal-dual iteration for solving weighted \(\ell^1\)-minimization problems in Hilbert spaces. Their theory is supplemented by numerical experiments demonstrating the efficacy of these algorithms.

    A publication of the European Mathematical Society (EMS). Distributed within the Americas by the American Mathematical Society.

  • Additional Material
     
     
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Accessibility – to request an alternate format of an AMS title
Volume: 132024; 112 pp
MSC: Primary 65; Secondary 41

Sparse polynomial approximation is an important tool for approximating high-dimensional functions from limited samples — a task commonly arising in computational science and engineering. Yet, it lacks a complete theory. There is a well-developed theory of best \(s\)-term polynomial approximation, which asserts exponential or algebraic rates of convergence for holomorphic functions.

There are also increasingly mature methods such as (weighted) \(\ell^1\)-minimization for practically computing such approximations. However, whether these methods achieve the rates of the best \(s\)-term approximation is not fully understood. Moreover, these methods are not algorithms per se, since they involve exact minimizers of nonlinear optimization problems.

This paper closes these gaps by affirmatively answering the following question: Are there robust, efficient algorithms for computing sparse polynomial approximations to finite- or infinite-dimensional, holomorphic and Hilbert-valued functions from limited samples that achieve the same rates as the best \(s\)-term approximation?

The authors do so by introducing algorithms with exponential or algebraic convergence rates that are also robust to sampling, algorithmic and physical discretization errors. Their results involve several developments of existing techniques, including a new restarted primal-dual iteration for solving weighted \(\ell^1\)-minimization problems in Hilbert spaces. Their theory is supplemented by numerical experiments demonstrating the efficacy of these algorithms.

A publication of the European Mathematical Society (EMS). Distributed within the Americas by the American Mathematical Society.

Review Copy – for publishers of book reviews
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.