基于函数在有限采样点处的函数值对其进行近似，是数学中的经典问题，如今在机器学习等领域也扮演着重要角色。该问题主要涉及三个核心要素：采样点的选择、近似函数空间的选取以及近似方法的设计。一种广为采用的策略是：随机选取采样点，采用多项式空间作为近似函数空间，并以最小二乘法作为近似手段。针对这种随机采样下的多项式最小二乘方法，Cohen、Davenport 与 Leviatan 于 2013 年证明：在均匀随机采样的设定下，若采样点数量达到多项式次数的平方量级，则该方法具有稳定性。此后，研究者们一直致力于降低所需采样点的数量，期望将其降至与多项式次数呈线性关系。然而，我们证明了该方法稳定性的必要条件：为保证其稳定性，采样点数量至少需达到多项式次数的平方量级。这一结果揭示了在众多场景中，为确保函数近似或学习的有效性，采样点数量存在一个不可逾越的下界：即与多项式次数的平方成正比。

Publication:

Constructive Approximation

https://link.springer.com/article/10.1007/s00365-026-09735-w

Author:

Xinyue Zhang 

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, No. 55, Zhongguancun East Road, Beijing 100190, China

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

zhangxinyue@amss.ac.cn

Zhiqiang Xu 

State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, No. 55, Zhongguancun East Road, Beijing 100190, China

School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

xuzq@lsec.cc.ac.cn