2024/07/14 by Zhiqiang Xu, Xinyue Zhang, Xu, Zhiqiang +1
Computer Science · Mathematics · #FOS: Mathematics #Fuzzy Systems and Optimization #Neural Networks and Applications #Numerical Analysis (math.NA) #Target Tracking and Data Fusion in Sensor Networks
paper · pdf · doi:10.48550/arxiv.2407.10221
openalex publication_date 2024/07/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper investigates the stability of the least squares approximation Pmn within the univariate polynomial space of degree m, denoted by \mathbb Pm. The approximation Pmn entails identifying a polynomial in \mathbb Pm that approximates a function f over a domain X based on samples of f taken at n randomly selected points, according to a specified probability measure ρX. The primary goal is to determine the sampling rate necessary to ensure the stability of Pmn. Assuming the sampling points are i.i.d. with respect to a Jacobi weight function, we present the sampling rate that guarantee the stability of Pmn. Specifically, for uniform random sampling, we demonstrate that a sampling rate of n \asymp m2 is required to maintain stability. By combining these findings with those of Cohen-Davenport-Leviatan, we conclude that, for uniform random sampling, the optimal sampling rate for guaranteeing the stability of Pmn is n \asymp m2, up to a log n factor. Motivated by this result, we extend the impossibility theorem, previously applicable to equally spaced samples, to the case of random samples, illustrating the balance between accuracy and stability in recovering analytic functions.