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

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-相干字典的贪婪逼近、压缩感知的lq最小化算法。关于随机逼近，我们研究量子计算模型的易处理性、随机量子计算模型下多元函数逼近的复杂性、混合光滑性的Besov函数类的逼近问题的线性与自适应随机算法、随机框架下的加权Sobolev类上的积分问题的易处理性。我们的预期结果将为逼近论、基于信息的复杂性理论的研究提供多个新的增长点，同时也对机器学习、压缩感知、量子计算的研究起到推进作用。

多元函数逼近是函数逼近的前沿热点问题。而稀疏逼近与随机逼近是多元逼近的重要手段。这两种逼近方法能够有效地克服高维逼近中的维数效应。本项目我们研究多元函数的稀疏逼近与随机逼近的若干问题。 关于稀疏逼近，我们研究m项逼近的贪婪算法、压缩感知的超级贪婪算法、Shannon取样展开逼近。关于随机逼近，我们研究基于随机样本的正则化学习算法的误差、混合光滑性的Besov函数类的Monte Carlo积分问题的误差估计。我们得到了以上问题的误差的最优收敛阶。这些结果将为逼近论、基于信息的复杂性理论的研究提供多个新的增长点，同时也对机器学习、压缩感知的研究起到推进作用。