Debiasing Polynomial and Fourier Regression

2025/08/08 by Chris Camaño, Raphael A. Meyer, Camaño, Chris +3
Computer Science · Mathematics · #65F99 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Polynomial and algebraic computation #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2508.05920

openalex publication_date 2025/08/08 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

Abstract

We study the problem of approximating an unknown function f:ℝ→ℝ by a degree-d polynomial using as few function evaluations as possible, where error is measured with respect to a probability distribution μ. Existing randomized algorithms achieve near-optimal sample complexities to recover a (1+ε) -optimal polynomial but produce biased estimates of the best polynomial approximation, which is undesirable. We propose a simple debiasing method based on a connection between polynomial regression and random matrix theory. Our method involves evaluating f(λ₁),…,f(λ_d+1) where λ₁,…,λ_d+1 are the eigenvalues of a suitably designed random complex matrix tailored to the distribution μ. Our estimator is unbiased, has near-optimal sample complexity, and experimentally outperforms iid leverage score sampling. Additionally, our techniques enable us to debias existing methods for approximating a periodic function with a truncated Fourier series with near-optimal sample complexity.

Citations

• Optimal sampling for least-squares approximation
• Improved Active Learning via Dependent Leverage Score Sampling
• A note on the exact simulation of a random eigenvalue of a GUE matrix
• Near-Linear Sample Complexity for L_p Polynomial Regression
• Near Optimal Reconstruction of Spherical Harmonic Expansions
• Deep Learning in High Dimension: Neural Network Approximation of Analytic Functions in L²(ℝ^d,γ_d)
• Fast and stable approximation of analytic functions from equispaced samples via polynomial frames
• Semi-Infinite Linear Regression and Its Applications
• Sampling the eigenvalues of random orthogonal and unitary matrices
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Determinantal Point Processes in Randomized Numerical Linear Algebra
• Vandermonde with Arnoldi
• Unbiased estimators for random design regression
• A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms
• Relating Leverage Scores and Density using Regularized Christoffel Functions
• Active Regression via Linear-Sample Sparsification
• Robust polynomial regression up to the information theoretic limit
• Compressed sensing approaches for polynomial approximation of high-dimensional functions
• On spectral measures of random Jacobi matrices
• On discrete least square projection in unbounded domain with random evaluations and its application to parametric uncertainty quantification
• Matrix models for circular ensembles

Related

• Robust polynomial regression up to the information theoretic limit
• Near-Linear Sample Complexity for L_p Polynomial Regression
• Computation of Induced Orthogonal Polynomial Distributions
• Robust Linear Regression: Optimal Rates in Polynomial Time
• Outlier Robust Multivariate Polynomial Regression