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

项目名称： 多元逼近的贪婪算法与量子算法

项目编号： No.10971251

项目类型： 面上项目

立项/批准年度： 2010

项目学科： 数理科学和化学

项目作者： 叶培新

作者单位： 南开大学

项目金额： 30万元

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

中文关键词： 贪婪逼近；量子逼近；Monte Carlo逼近；正则化学习；压缩感知

英文摘要：

英文关键词： Greedy approximation；Quantum approximation；Monte Carlo approximation；Regularzation learning；Compressed sensing