多元函数的稀疏逼近与随机逼近

项目名称： 多元函数的稀疏逼近与随机逼近

项目编号： No.11271199

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 叶培新

作者单位： 南开大学

项目金额： 75万元

中文摘要： 我们研究多元函数的稀疏逼近与随机逼近。这两种逼近方法能够有效地克服高维逼近中的维数效应。关于稀疏逼近，我们研究稀疏函数的压缩学习、流形上的学习、关于M-相干字典的贪婪逼近、压缩感知的lq最小化算法。关于随机逼近，我们研究量子计算模型的易处理性、随机量子计算模型下多元函数逼近的复杂性、混合光滑性的Besov函数类的逼近问题的线性与自适应随机算法、随机框架下的加权Sobolev类上的积分问题的易处理性。我们的预期结果将为逼近论、基于信息的复杂性理论的研究提供多个新的增长点，同时也对机器学习、压缩感知、量子计算的研究起到推进作用。

中文关键词： m项逼近；贪婪算法；正则化学习；压缩感知；Shannon取样

英文摘要： We study several problems related to sparse approximation and randomized approximation of multi-variate functions. These two types of approximation method can vanquish the curse of dimensionality in high dimensional approximation. For sparse approximation, we study compressed learning for sparse functions, learning on manifolds, greedy approximation with M-coherent dictionary, lq minimization for compressed sensing. For randomized approximation, we study tractability in the quantum computation model, complexity of multi-variate approximation in the quantum setting with randon bites、randomized approximation for Besov class with mixed smoothness, and tractability of randomized integration on weighted sobolev space. Our expected results will provide several new directs for the the study of approximation theory,information-based complexity theory. These results will also be helpful for the development of machine learning, compressed sensing and quantum computation.

英文关键词： m term approximation；greedy algorithm；regularized learning；compressed sensing；Shannon sampling