Source-linked AI summary
Optimal weighted least-squares methods
Albert Cohen, Giovanni Migliorati
TL;DR
The paper addresses instability and excessive sampling requirements in least-squares reconstruction from random samples. It develops weighted least-squares theory and a method for sampling the optimal measure, showing stability and near-optimal accuracy with n of order m ln(m), while covering unbounded settings.
Problem
Least-squares reconstruction can be unstable when the sample count is too close to the approximation dimension, motivating better choices of sampling measure and weights.
Method
The paper analyzes weighted least squares with independently sampled points, an optimal space- and measure-dependent sampling measure and weight, and conditioning or truncation strategies.
Results
The analysis establishes stability and near-optimal accuracy with a sample requirement of order m ln(m), including truncated, nontruncated, and conditioned estimators.
Takeaways & Limitations
The proposed approach extends weighted least-squares analysis to unbounded functions and domains and provides a method for generating independent samples from the optimal measure.
Takeaways & Limitations
Although the estimates are independent of domain dimension, increasing dimension restricts the function classes having prescribed approximation-error decay because of the curse of dimensionality.
Abstract
from arXiv · showhide
We consider the problem of reconstructing an unknown bounded function $u$ defined on a domain $X\subset \mathbb{R}^d$ from noiseless or noisy samples of $u$ at $n$ points $(x^i)_{i=1,\dots,n}$. We measure the reconstruction error in a norm $L^2(X,dρ)$ for some given probability measure $dρ$. Given a linear space $V_m$ with ${\rm dim}(V_m)=m\leq n$, we study in general terms the weighted least-squares approximations from the spaces $V_m$ based on independent random samples. The contribution of the present paper is twofold. From the theoretical perspective, we establish results in expectation and in probability for weighted least squares in general approximation spaces $V_m$. These results show that for an optimal choice of sampling measure $dμ$ and weight $w$, which depends on the space $V_m$ and on the measure $dρ$, stability and optimal accuracy are achieved under the mild condition that $n$ scales linearly with $m$ up to an additional logarithmic factor. The present analysis covers also cases where the function $u$ and its approximants from $V_m$ are unbounded, which might occur for instance in the relevant case where $X=\mathbb{R}^d$ and $dρ$ is the Gaussian measure. From the numerical perspective, we propose a sampling method which allows one to generate independent and identically distributed samples from the optimal measure $dμ$. This method becomes of interest in the multivariate setting where $dμ$ is generally not of tensor product type. We illustrate this for particular examples of approximation spaces $V_m$ of polynomial type, where the domain $X$ is allowed to be unbounded and high or even infinite dimensional, motivated by certain applications to parametric and stochastic PDEs.
1 Introduction
The paper studies weighted least-squares reconstruction in finite-dimensional spaces from random samples, seeking stability and accuracy with sample sizes close to the approximation dimension. It develops conditioning strategies and identifies sampling choices that address instability, including settings with unbounded functions or domains.
- Weighted least squares reconstructs u in an m-dimensional space V_m from noiseless or noisy point samples, with error measured in L^2(X,dρ).
- The method uses random samples and weights so the Gram matrix G concentrates toward the identity, while truncation or conditioning limits effects of ill-conditioning.
- When n is too close to m, least-squares methods can become unstable and inaccurate, with polynomial interpolation providing a highly unstable example.
- The central design problem is choosing the sampling measure and weights so the L^2 error is comparable to the best approximation error e_m(u) with n as close to m as possible.
- For standard least squares, the required sample size can be much larger than m ln(m), including order m^2 ln(m) for Legendre polynomial spaces.
2 Main results
The paper develops weighted least-squares methods using a sampling measure and weight tailored to V_m and dρ. The optimal choice yields near-optimal estimates under n scaling as m ln(m), while extending applicability to unbounded settings and highlighting sampling and adaptivity challenges.
- Theorem 2 results: The weighted least-squares framework provides stability and approximation results for truncated, nontruncated, and conditioned estimators under the theorem’s sampling-size condition.Theorem 2 states a Gram-matrix tail bound and separate noiseless guarantees for these estimator variants.
- Unbounded domains: The conditioned estimator remains valid for polynomial approximation on unbounded domains such as X = R with Gaussian measure when target functions are not uniformly bounded.The nontruncated and truncated results requiring uniform boundedness do not apply in that setting.
- Scope and limitations: The results are independent of the domain dimension d, although increasing d restricts function classes with prescribed best-approximation decay because of the curse of dimensionality.Dimension independence concerns the stated weighted least-squares results, not the approximation rates available for arbitrary function classes.
- Scope and limitations: The optimal pair depends on V_m, creating a difficulty when V_m varies, as in adaptive methods; asymptotic replacements w* and dμ* are available only in certain cases.The paper states that sampling strategies without such asymptotic equivalences remain under investigation.
- Sampling implementation: Generating independent samples from dμ_m is intrinsically difficult in multivariate settings because the optimal measure is generally not a tensor-product measure.The paper discusses a sampling method for this setting and contrasts it with Markov Chain Monte Carlo approaches, whose samples are correlated and only asymptotically distributed as desired.
3 Proof of Theorem 2
The proof establishes concentration of the weighted Gram matrix around the identity and uses this event to control estimator errors. It combines a matrix Chernoff bound with norm-equivalence and orthogonality arguments for the different estimator guarantees.
- Gram-matrix concentration: The weighted Gram matrix is represented as an average of independent rank-one random matrices with expectation equal to the identity.This representation permits concentration analysis through a matrix Chernoff bound.
- Gram-matrix concentration: A matrix Chernoff bound yields the tail estimate for G under an almost-sure bound on the rank-one summands.The proof selects a deviation parameter to obtain the stated theorem bound.
- Estimator error bounds: On the event ∥G − I∥2 ≤ 1/2, the inverse Gram matrix is controlled, enabling the approximation estimate for the truncated estimator.The proof combines this event with the truncation operator and orthogonality of the residual to V_m.
- Estimator error bounds: The proof of the nontruncated estimate uses the resulting norm equivalence on V_m together with domination by the L∞ norm.This argument is carried out on the event where the Gram matrix remains sufficiently close to the identity.
- Estimator error bounds: The conditioned-estimator estimate follows the same decomposition as the truncated case, treating separately the event where G deviates substantially from I.The proof concludes by applying the same control strategy to the corresponding error terms.
4 The noisy case
The noisy-case analysis extends weighted least-squares estimates to additive deterministic and stochastic noise. Under the stated sampling condition, the resulting bounds remain robust, with additional assumptions needed for high-probability estimates.
- Noise models: Additive observation noise is modeled through deterministic perturbations h or stochastic fluctuations η, which need not be independent of the sample locations.The stochastic noise is centered and has uniformly bounded conditional variance in the stated model.
- General noise results: Theorem 3 states that weighted least-squares estimates remain robust under the additive-noise model when condition (14) holds.The theorem includes results for truncated estimators and assumes a uniform bound on u for item (i).
- Scope and assumptions: The general noisy-case conclusions do not include the probability estimate corresponding to item (iii) of Theorem 2 without an additional bounded-noise assumption.A bounded deterministic perturbation h and bounded random noise η are imposed to recover such an estimate.
- Bounded-noise case: Theorem 4 provides probability bounds for bounded noise when u is bounded and condition (14) is satisfied.The stated guarantee holds with probability larger than 1 − 2n^−r for any r > 0.
- Proof strategy: The noise contribution is represented by the weighted least-squares approximation of the noise vector and is bounded using the same Gram-matrix control as the noiseless analysis.The proof separates previously analyzed terms from the new approximation term P_mβ and works on the event ∥G−I∥_2 ≤ 1/2.
5 Random sampling from µm
The paper develops sequential conditional sampling for the optimal measure μ_m, whose multivariate density generally lacks product structure. The method generates independent samples by sampling successive univariate conditional densities, with rejection or inversion-transform methods as implementation options.
- Motivation and setting: The sampling problem arises because the optimal multivariate measure μ_m is generally not a tensor product, despite the underlying reference measure being a product density.The method assumes a Cartesian-product domain and product reference measure in the multivariate construction.
- Sequential conditional sampling: Sequential conditional sampling generates n independent and identically distributed realizations from μ_m by sampling coordinates one at a time.At each step, the next coordinate is sampled conditionally on the previously generated coordinates.
- Conditional densities: The conditional density of coordinate q is formed from the ratio of successive marginals, with a continuous extension where the denominator vanishes.The densities ϕ_q are defined as conditional densities and can be expressed as convex combinations of univariate basis-dependent densities.
- Algorithm: The algorithm samples the first coordinate from ϕ_1, then iterates through coordinates 2 to d using conditional densities evaluated at the previously sampled coordinates.Coordinates may be reordered, and the construction relies on evaluating the relevant univariate basis functions and densities.
- Univariate sampling: Rejection sampling and inversion-transform sampling provide two ways to sample each univariate conditional density.Inversion transform sampling requires suitable cumulative-distribution invertibility, while rejection sampling uses a proposal density Θ_q and acceptance factor M_q.
- Computational cost: For rejection sampling with bounded orthonormal systems, a crude computational estimate is 2ndm^2, while Jacobi-polynomial bounds retain linear dependence on n and d.The rejection-sampling cost is proportional to the coordinate-wise proposal factors, and the Jacobi case admits analogous bounds.
- Computational cost: With inversion-transform sampling and bisection, the overall cost is expressed through the number of iterations γ_q and per-iteration costs W_q across coordinates.The same cost structure is stated for locating inverse-CDF values to a prescribed tolerance.
6 Examples and numerical illustrations
The numerical examples compare weighted and standard least squares across uniform, Gaussian, and Chebyshev measures in univariate and multivariate polynomial spaces. Weighted least squares achieves stable Gramian matrices with substantially less dependence on the measure, dimension, and polynomial-space sequence.
- Experimental setup: The experiments compare both methods using empirical estimates of Pr{cond(G) ≤3}, with one hundred random-sampling repetitions.The tests use uniform, Gaussian, and Chebyshev measures; multivariate tests cover downward closed polynomial spaces.
- Univariate examples: In one dimension, weighted least squares reaches empirical probability one when n/ln(n) ≥4m for all three measures.The three measures show no perceivable performance differences in this test.
- Multivariate examples: In dimension d = 10, weighted least squares achieves empirical probability one when n/log(n) ≥2m, with similar behavior for all three measures.The observed transition agrees with the theoretical condition for stability.
- Multivariate examples: For d = 10, standard least squares needs n/ln(n) ≥3.5m for the uniform measure and many more evaluations for the Gaussian measure, while Chebyshev sampling is more favorable.The uniform threshold exceeds the weighted threshold, whereas Gaussian standard least squares exhibits a drastically larger sample requirement.
- Multivariate examples: Standard least-squares results are sensitive to the chosen sequence of polynomial spaces, unlike the weighted approach under condition (21).Different multivariate spaces can produce null empirical probabilities for standard least squares with uniform or Chebyshev measures.