On the stability and accuracy of least squares approximations

DOI10.1007/S10208-013-9142-3zbMATH Open1276.93086arXiv1111.4422OpenAlexW2026679679MaRDI QIDQ385457FDOQ385457

Authors: Albert Cohen, Mark A. Davenport, D. Leviatan 

Publication date: 2 December 2013

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We consider the problem of reconstructing an unknown function $f$ on a domain $X$ from samples of $f$ at $n$ randomly chosen points with respect to a given measure $h{o}_X$. Given a sequence of linear spaces $(V_m{)}_{m>0}$ with $mdim(V_m)=mleqn$, we study the least squares approximations from the spaces $V_m$. It is well known that such approximations can be inaccurate when $m$ is too close to $n$, even when the samples are noiseless. Our main result provides a criterion on $m$ that describes the needed amount of regularization to ensure that the least squares method is stable and that its accuracy, measured in $L^2(X,h{o}_X)$, is comparable to the best approximation error of $f$ by elements from $V_m$. We illustrate this criterion for various approximation schemes, such as trigonometric polynomials, with $h{o}_X$ being the uniform measure, and algebraic polynomials, with $h{o}_X$ being either the uniform or Chebyshev measure. For such examples we also prove similar stability results using deterministic samples that are equispaced with respect to these measures.

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

Recommendations

• scientific article; zbMATH DE number 727770
• Correction to: ``On the stability and accuracy of least squares approximations
• On the numerical stability and accuracy of the conventional recursive least squares algorithm.
• Stability of moving least squares approximation
• A note on an error estimate for least squares approximation
• scientific article; zbMATH DE number 4070775
• scientific article; zbMATH DE number 868182
• scientific article; zbMATH DE number 4151645
• The accuracy of the method of least squares

zbMATH Keywords

samplingleast squaresrandom matricespolynomial approximation

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Numerical smoothing, curve fitting (65D10) Trigonometric approximation (42A10) Least squares and related methods for stochastic control systems (93E24) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05)

Cites Work

• A distribution-free theory of nonparametric regression
• User-friendly tail bounds for sums of random matrices
• Minimum contrast estimators on sieves: Exponential bounds and rates of convergence
• Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE's
• Model selection for regression on a random design
• Adaptive quadrature -- Revisited
• Strong converse for identification via quantum channels

Cited In (only showing first 100 items - show all)

• High-resolution signal recovery via generalized sampling and functional principal component analysis
• Nonparametric drift estimation for i.i.d. paths of stochastic differential equations
• Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
• Data assimilation for models with parametric uncertainty
• Polynomial approximation via compressed sensing of high-dimensional functions on lower sets
• Adaptive multi-fidelity polynomial chaos approach to Bayesian inference in inverse problems
• Multivariate approximation in downward closed polynomial spaces
• On polynomial chaos expansion via gradient-enhanced \(\ell_1\)-minimization
• All well-posed problems have uniformly stable and convergent discretizations
• Randomized numerical linear algebra: Foundations and algorithms
• Regression function estimation as a partly inverse problem
• On tensor product approximation of analytic functions
• Regression function estimation on non compact support in an heteroscesdastic model
• Analysis of discrete \(L^2\) projection on polynomial spaces with random evaluations
• A theoretical study of compressed solving for advection-diffusion-reaction problems
• Correction to: ``On the stability and accuracy of least squares approximations
• Compressive sensing Petrov-Galerkin approximation of high-dimensional parametric operator equations
• Upper estimates of Christoffel function on convex domains
• A sparse grid stochastic collocation method for elliptic interface problems with random input
• Distribution-free robust linear regression
• Drift estimation on non compact support for diffusion models
• Reducing sensors for transient heat transfer problems by means of variational data assimilation
• Infinite-dimensional \(\ell ^1\) minimization and function approximation from pointwise data
• Variational Monte Carlo -- bridging concepts of machine learning and high-dimensional partial differential equations
• Spectral likelihood expansions for Bayesian inference
• Sparse identification of nonlinear dynamical systems via reweighted \(\ell_1\)-regularized least squares
• Least squares approximations of measures via geometric condition numbers
• Nadaraya–Watson estimator for I.I.D. paths of diffusion processes
• Title not available (Why is that?)
• Sparse polynomial chaos expansions via compressed sensing and D-optimal design
• Stability of discrete empirical interpolation and gappy proper orthogonal decomposition with randomized and deterministic sampling points
• Geometric computation of Christoffel functions on planar convex domains
• Least-squares approach to problems with inexact values of the function and its argument
• Weighted discrete least-squares polynomial approximation using randomized quadratures
• Constructing least-squares polynomial approximations
• Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression
• Randomized weakly admissible meshes
• Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension
• Convergence estimates in probability and in expectation for discrete least squares with noisy evaluations at random points
• Optimal weighted least-squares methods
• Near-optimal sampling strategies for multivariate function approximation on general domains
• Gaussian functional regression for linear partial differential equations
• Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets
• Optimal Monte Carlo methods for \(L^2\)-approximation
• A mixed ℓ<sub>1</sub> regularization approach for sparse simultaneous approximation of parameterized PDEs
• Matrix concentration inequalities via the method of exchangeable pairs
• On a near optimal sampling strategy for least squares polynomial regression
• Interpolation via weighted \(\ell_{1}\) minimization
• A Christoffel function weighted least squares algorithm for collocation approximations
• Stable extrapolation of analytic functions
• Least squares polynomial chaos expansion: a review of sampling strategies
• An improved discrete least-squares/reduced-basis method for parameterized elliptic PDEs
• A parameterized-background data-weak approach to variational data assimilation: formulation, analysis, and application to acoustics
• Basis adaptive sample efficient polynomial chaos (BASE-PC)
• PBDW state estimation: noisy observations; configuration-adaptive background spaces; physical interpretations
• On a projection estimator of the regression function derivative
• On least squares discrete Fourier analysis of unequally spaced data
• Efficient Bayesian experimentation using an expected information gain lower bound
• Stability of \(L_ 1\)-approximations and robustness of least module estimates
• Adaptive approximation by optimal weighted least-squares methods
• Functional regression for state prediction using linear PDE models and observations
• Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic PDEs
• Nonadaptive quasi-optimal points selection for least squares linear regression
• An orthogonality property of the Legendre polynomials
• Function values are enough for \(L_2\)-approximation. II
• The expected norm of a sum of independent random matrices: an elementary approach
• Computation of induced orthogonal polynomial distributions
• APPROXIMATING SMOOTH, MULTIVARIATE FUNCTIONS ON IRREGULAR DOMAINS
• Effectively subsampled quadratures for least squares polynomial approximations
• Nonparametric estimation for independent and identically distributed stochastic differential equations with space-time dependent coefficients
• Sparse identification of nonlinear dynamical systems via non-convex penalty least squares
• Least squares orthogonal polynomial regression estimation for irregular design
• Towards stability results for global radial basis function based quadrature formulas
• Nonparametric adaptive estimation for interacting particle systems
• Risk of estimators for Sobol' sensitivity indices based on metamodels
• Variable transformations in combination with wavelets and ANOVA for high-dimensional approximation
• Learning interaction kernels in stochastic systems of interacting particles from multiple trajectories
• Optimal sampling and Christoffel functions on general domains
• Parametrization of Random Vectors in Polynomial Chaos Expansions via Optimal Transportation
• Automated importance sampling via optimal control for stochastic reaction networks: a Markovian projection-based approach
• On the reconstruction of functions from values at subsampled quadrature points
• Nonparametric estimation for i.i.d. paths of a martingale-driven model with application to non-autonomous financial models
• On the training and generalization of deep operator networks
• Randomized least-squares with minimal oversampling and interpolation in general spaces
• Nonparametric estimation for i.i.d. paths of fractional SDE
• Boosted optimal weighted least-squares
• Optimal learning
• Weighted approximate Fekete points: sampling for least-squares polynomial approximation
• Correcting data corruption errors for multivariate function approximation
• Fast hyperbolic wavelet regression meets ANOVA
• Towards optimal sampling for learning sparse approximation in high dimensions
• Nonparametric drift estimation from diffusions with correlated Brownian motions
• Nonparametric plug-in classifier for multiclass classification of S.D.E. paths
• Random sampling and unisolvent interpolation by almost everywhere analytic functions
• Data-driven polynomial chaos expansions: a weighted least-square approximation
• Least squares approximations in linear statistical inverse learning problems
• ``Regression anytime with brute-force SVD truncation
• SeAr PC: sensitivity enhanced arbitrary polynomial chaos
• Structure-Preserving Method for Reconstructing Unknown Hamiltonian Systems From Trajectory Data
• Error guarantees for least squares approximation with noisy samples in domain adaptation

This page was built for publication: On the stability and accuracy of least squares approximations

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