Source-linked AI summary
On the stability and accuracy of least squares approximations
Albert Cohen, Mark A. Davenport, Dany Leviatan
TL;DR
The paper addresses instability in least squares reconstruction when the approximation dimension approaches the number of samples. It develops a criterion based on the space and sampling measure, proving stability and approximation-error bounds for noiseless and noisy data, with examples showing measure-dependent rates and dimension choices.
Problem
Least squares approximations can be inaccurate and unstable when m is too close to n, even for noiseless samples, so the needed regularization must be characterized.
Method
The paper analyzes concentration of the empirical Gram matrix around the identity through K(m), deriving a dimension criterion and applying it to random and structured approximation settings.
Results
The criterion ensures stable least squares and errors comparable to best approximation, with rates depending on the measure; for differentiable functions, Chebyshev sampling improves the exponent from r to 2r.
Takeaways & Limitations
Choosing m below the stability threshold provides a principled regularization rule, while the threshold and achievable rates depend on V_m and ρ_X.
Takeaways & Limitations
The admissible dimension can be severely constrained because K(m) depends on the sampling measure and may become arbitrarily large for certain measures.
Abstract
from arXiv · showhide
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 $ρ_X$. Given a sequence of linear spaces $(V_m)_{m>0}$ with ${\rm dim}(V_m)=m\leq n$, 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,ρ_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 $ρ_X$ being the uniform measure, and algebraic polynomials, with $ρ_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.
1 Introduction and main results
The paper studies least squares reconstruction from random samples and identifies how small the approximation space must be relative to the sample size for stability and accuracy. Its criterion controls norm comparability and yields approximation guarantees in noiseless and noisy settings, with rates depending on the measure and approximation scheme.
- Motivation: Least squares can be unstable even with noiseless data when the space dimension m is too close to the sample count n.For polynomial spaces with m=n, least squares becomes interpolation and can exhibit the Runge phenomenon on uniformly spaced samples.
- Stability of the least squares problem: The analysis measures stability through comparability of the true L2 norm and empirical norm on V_m, equivalently through the spectral proximity of G to I.The matrix criterion is formulated using concentration of the random matrix G around its expectation I.
- Stability of the least squares problem: K(m) must be smaller than n by a logarithmic factor to make the norms comparable with high probability and ensure that G is well conditioned.The quantity K(m) depends only on V_m and ρ_X, so the admissible m depends strongly on the approximation space and sampling measure.
- Accuracy of least squares approximation: Under this condition, the noiseless least squares projection is stable and its expected error is controlled relative to the best approximation error in V_m.Theorem 2 applies when condition (1.4) holds and includes ε(n) = 4κ log(n) → 0.
- Accuracy of least squares approximation: The same dimension condition gives an error bound for noisy regression, while the choice of m additionally depends on the decay of the approximation error e_m and the noise variance.Model selection or validation can be used when these quantities, or the maximal admissible m, are unknown.
- Examples and rates: For r-times differentiable functions, uniform polynomial sampling yields noiseless mean-squared error proportional to n^-r up to logarithmic factors, while Chebyshev sampling improves r to 2r.The corresponding noisy rate under the uniform setting is proportional to σ^(2r/(r+1)) n^(-r/(r+1)).
2 Proofs
The proofs establish stability by controlling the empirical Gram matrix with random-matrix concentration, then bound approximation and noise contributions under the stability condition.
- Stability proof: Random-matrix Chernoff bounds control deviations of the empirical Gram matrix from the identity.The proof applies a Chernoff bound to independent positive self-adjoint random matrices and uses matching minimum and maximum expected eigenvalues.
- Stability proof: Rank-one matrix norm identities reduce the matrix concentration estimate to products of Euclidean norms.For a rank-one matrix ab^T, the spectral norm equals the product of the Euclidean norms of a and b.
- Stability proof: The Gram-matrix deviation event is split into stable and complementary draw sets before estimating the least squares solution.The proof defines the product draw measure, the stable set Ω+, and its complement Ω−, then invokes the probabilistic estimate.
- Approximation and noise bounds: The noiseless error proof decomposes f into its projection onto Vm and the orthogonal residual, then bounds the residual's empirical correlations with the basis.The residual g = f − Pm f is orthogonal to Vm, while the Gram inverse is bounded on Ω+.
- Approximation and noise bounds: The noisy-data proof separates approximation and noise effects, using a corresponding least squares solution for the noise data and a decorrelation property.The argument allows η and x to be dependent but assumes a decorrelation relation sufficient for the noise estimates.
- Approximation and noise bounds: The resulting estimates conclude the theorem after separately controlling the approximation and noise terms under the same stability framework.The proof introduces coefficient systems for the approximation and noise components and combines their bounds.
3 Examples and numerical illustrations
The examples connect the stability criterion to trigonometric, algebraic, and piecewise constant approximation schemes, including deterministic sampling constructions. Numerical experiments show that the usable polynomial degree depends strongly on the sampling measure: roughly √n for uniform sampling and nearly linear in n for Chebyshev sampling.
- Approximation schemes: The paper computes K(m) for several approximation schemes to estimate ranges of m satisfying the stability condition, and gives corresponding deterministic sampling results.The examples include trigonometric polynomials, algebraic polynomials, and piecewise constant functions.
- Piecewise constant functions: For piecewise constant functions, K(m) is determined by the smallest partition-cell measure, and evenly distributing ρX minimizes K(m).Under the strong density assumption, uniform partitions yield K(m) ∼ m; choosing one deterministic point per cell ensures stability up to m = n.
- Trigonometric polynomials: For trigonometric polynomials with the uniform measure, stability can be ensured up to m ∼ n log n for random sampling and up to m = n for deterministic uniform sampling.The deterministic result uses equispaced points and applies when m ≤ n.
- Algebraic polynomials and uniform measure: For algebraic polynomials with the uniform measure, the stability range is lower, of order n log n, while deterministic interval sampling provides a separate stability guarantee.The deterministic bound is obtained by partitioning the interval into equal subintervals and selecting one point from each.
- Algebraic polynomials and Chebyshev measure: For algebraic polynomials with the Chebyshev measure, stability can be achieved for m ∼ n log n under random sampling and up to m = n 2π + 1 with deterministic sampling.The Chebyshev measure permits higher stable polynomial degrees than the uniform measure in the stated comparison.
- Numerical illustration: In numerical experiments, least squares becomes inaccurate as m approaches n, while Chebyshev sampling delays instability and produces m(n) that is nearly linear in n rather than √n.The experiments use the smooth Runge function f1 and the nonsmooth function f2, with noise-free samples.