Semi-algebraic approximation using Christoffel-Darboux kernel

DOI10.1007/S00365-021-09535-4MaRDI QIDQ2067503zbMATH OpenOpenAlexFDO

Authors Swann Marx, Edouard Pauwels, Tillmann Weisser, Didier Henrion, Jean B. Lasserre

Publication date 18 January 2022

Published in Constructive Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.01833

zbMATH Keywords

momentsconvex optimizationapproximation theoryorthogonal polynomialspositive polynomials

Mathematics Subject Classification ID

Convex programming (90C25) Approximation by other special function classes (41A30) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05) Linear operators in reproducing-kernel Hilbert spaces (including de Branges, de Branges-Rovnyak, and other structured spaces) (47B32)

Abstract: We provide a new method to approximate a (possibly discontinuous) function using Christoffel-Darboux kernels. Our knowledge about the unknown multivariate function is in terms of finitely many moments of the Young measure supported on the graph of the function. Such an input is available when approximating weak (or measure-valued) solution of optimal control problems, entropy solutions to non-linear hyperbolic PDEs, or using numerical integration from finitely many evaluations of the function. While most of the existing methods construct a piecewise polynomial approximation, we construct a semi-algebraic approximation whose estimation and evaluation can be performed efficiently. An appealing feature of this method is that it deals with non-smoothness implicitly so that a single scheme can be used to treat smooth or non-smooth functions without any prior knowledge. On the theoretical side, we prove pointwise convergence almost everywhere as well as convergence in the Lebesgue one norm under broad assumptions. Using more restrictive assumptions, we obtain explicit convergence rates. We illustrate our approach on various examples from control and approximation. In particular we observe empirically that our method does not suffer from the the Gibbs phenomenon when approximating discontinuous functions.

Recommendations

• Kernel-based adaptive approximation of functions with discontinuities
• Christoffel functions and finite moment problems
• A Christoffel function weighted least squares algorithm for collocation approximations
• On approximate approximations using Gaussian kernels
• The empirical Christoffel function with applications in data analysis

Cites work

• scientific article; zbMATH DE number 1064079 (Why is no real title available?)
• scientific article; zbMATH DE number 1786124 (Why is no real title available?)
• scientific article; zbMATH DE number 1448982 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• scientific article; zbMATH DE number 3037624 (Why is no real title available?)
• A moment approach for entropy solutions to nonlinear hyperbolic PDEs
• Accurate and Efficient Reconstruction of Discontinuous Functions from Truncated Series Expansions
• Algebraic Fourier reconstruction of piecewise smooth functions
• Bergman polynomials on an archipelago: estimates, zeros and shape reconstruction
• Bernstein's inequality in \(L^p\) for \(0<p<1\) and \((C,1)\) bounds for orthogonal polynomials
• Christoffel functions and universality in the bulk for multivariate orthogonal polynomials
• Complete algebraic reconstruction of piecewise-smooth functions from Fourier data
• Computing Moments of the Exit Time Distribution for Markov Processes by Linear Programming
• Convex Duality and Nonlinear Optimal Control
• Data analysis from empirical moments and the Christoffel function
• Discussion of dynamic programming and linear programming approaches to stochastic control and optimal stopping in continuous time
• Géza Freud, orthogonal polynomials and Christoffel functions. A case study
• Learning sets with separating kernels
• Measure-valued solutions to conservation laws
• Minimizer Extraction in Polynomial Optimization Is Robust
• Moments, positive polynomials and their applications
• Nonlinear Optimal Control via Occupation Measures and LMI-Relaxations
• On the Gibbs Phenomenon and Its Resolution
• On the complexity of Putinar's Positivstellensatz
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Orthogonal polynomials of several variables
• Oscillation properties of scalar conservation laws
• PRICING A CLASS OF EXOTIC OPTIONS VIA MOMENTS AND SDP RELAXATIONS
• Piecewise-smooth chebfuns
• Real analysis
• Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
• The empirical Christoffel function with applications in data analysis
• The linear programming approach to deterministic optimal control problems
• The moment-SOS hierarchy

Cited in

(12)

• Global minimization of polynomial integral functionals
• Construction of Multivariate Polynomial Approximation Kernels via Semidefinite Programming
• A moment approach for entropy solutions of parameter-dependent hyperbolic conservation laws
• Moment-SoS methods for optimal transport problems
• The moment-SOS hierarchy: applications and related topics
• Sum-of-Squares Hierarchies for Polynomial Optimization and the Christoffel--Darboux Kernel
• Symmetry reduction and recovery of trajectories of optimal control problems via measure relaxations
• Graph recovery from incomplete moment information
• On the Christoffel function and classification in data analysis
• Approximation and interpolation of singular measures by trigonometric polynomials
• Rate of convergence for geometric inference based on the empirical Christoffel function
• Noncommutative Christoffel-Darboux kernels

Describes a project that uses

Uses Software

• Chebfun

This page was built for publication: Semi-algebraic approximation using Christoffel-Darboux kernel

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067503)