多元逼近的贪婪算法与量子算法

我们分别研究多元函数m项逼近问题的贪婪算法与最优恢复问题的量子算法。在m项逼近方面，我们将构造出关于张量型Harr小波的单个函数以及关于字典的某些稀疏函数类的m项逼近的贪婪算法，并分析其收敛阶。作为贪婪算法的应用，我们研究函数学习与压缩感知的确定性算法的构造。在最优恢复方面，我们首先研究具有混合光滑性函数类上的最优恢复的量子算法的最优收敛阶与复杂性。在量子算法的基础上我们还将确定这些类上的最优恢复的限制性Monte Carlo方法的最优收敛阶与复杂性。我们预期成果将为逼近论的发展提供多个新的增长点，同时也对数值分析、泛函分析、计算复杂性、信号处理、机器学习以及量子计算等学科的发展起到推进作用。

本项目我们在 m 项逼近问题的贪婪算法、压缩感知、机器学习 、量子逼近、Monte Carlo逼近、Shannon取样等问题的研究中取得一系列成果。在m 项逼近方面，我们构造出关于张量型Harr 小波以及关于字典的某些稀疏函数类的m项逼近的贪婪算法，并分析其收敛阶。作为贪婪算法的应用，我们研究压缩感知的个例最优性以及稳定性。在随机逼近方面，我们确定了具有混合光滑性函数类的最优恢复的量子算法的最优收敛阶。在此基础上我们确定这些类上的最优恢复的Monte Carlo 方法的最优收敛阶。在机器学习方面，我们研究了系数正则化学习算法的学习速度，得到了一个与维数无关的收敛阶。在Shannon取样理论方面，我们给出了非帯限光滑函数借助Shannon取样级数逼近的误差阶估计。此外我们还在解析函数类逼近、正线性算子逼近的研究中取得了一些成果。这些成果将为逼近论的发展提供多个新的增长点，同时也对数值分析、泛函分析、计算复杂性、信号处理、机器学习以及量子计算等学科的发展起到推进作用。