{"ID":2884491,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.05920","arxiv_id":"2508.05920","title":"Debiasing Polynomial and Fourier Regression","abstract":"We study the problem of approximating an unknown function $f:\\mathbb{R}\\to\\mathbb{R}$ 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+\\varepsilon) $-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(λ_1),\\ldots,f(λ_{d+1})$ where $λ_1,\\ldots,λ_{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.","short_abstract":"We study the problem of approximating an unknown function $f:\\mathbb{R}\\to\\mathbb{R}$ 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 $ (...","url_abs":"https://arxiv.org/abs/2508.05920","url_pdf":"https://arxiv.org/pdf/2508.05920v1","authors":"[\"Chris Camaño\",\"Raphael A. Meyer\",\"Kevin Shu\"]","published":"2025-08-08T00:43:33Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.NA\"]","methods":"[]","has_code":false}