几类贪婪型算法的逼近性能分析

We will make some deep investigations of the efficiency of the following greedy-type algorithms: greedy type algorithms with respect to dictionaries of Banach spaces with incoherence properties, reduced bases method for approximating a compact subset of a Banach space, Orthogonal Multi-Matching Pursuit in compressed sensing and the relaxed greedy algorithms for the regression problem with Gaussian noise. We establish the corresponding Lebesgue type inequalities to describe the approximation properties of these algorithms. Our expected results will provide several new directions for the future study of greedy approximation and will also be helpful for the developments of numerical analysis, compressed sensing and machine learning.

我们将深入研究几类重要的贪婪型算法的性能.它们是借助于给定Banach空间的字典以逼近该空间元素的贪婪算法，用于逼近给定Banach空间的紧子集的约化基方法，压缩感知中的正交多匹配追踪算法、用于带有Gauss噪声的回归学习的松弛贪婪算法. 我们将分别建立这几种算法所相应的Lebesgue型不等式以深入地刻画它们的逼近性质。我们的预期结果将为贪婪逼近的研究提供多个新的增长点，同时也对数值分析、压缩感知、机器学习的发展起到推进作用。

贪婪型算法是解决高维逼近问题的有效手段,它具有易于实施,计算复杂性小等优点,因此在信号处理与机器学习中有广泛应用。本项目我们研究了几类贪婪算法的性能及其在信号处理的应用,机器学习中的稀疏算法,多元函数逼近的稀疏随机算法的性能。贪婪算法的性能方面,我们首次对一般的双正交系证明了契比雪夫阈贪婪算法的收敛性。在该算法的误差估计方面，对可求和基与三角系这两种非拟贪婪基导出了相应的Lebesgue常数的下界。这是首次对非贪婪基得到的Lebesgue常数的估计。对借助于Hilbert空间H中满足某些条件的字典，我们研究了弱正交超级贪婪算法的性能，在字典的RIP条件以及更一般的相干条件下证明了该算法的几乎最优性。在稀疏感知方面, 证明了当测量矩阵满足限制性等距条件时，经过s次迭代，正交多匹配追踪算法能够恢复d维空间中的s稀疏信号。文中给出的限制性等距常数是迄今为止最好的。在学习理论方面, 在相当一般情形下得到了系数正则化算法与移动最小二乘学习算法的最优收敛阶。在函数逼近的随机算法方面,得到了经典的以及具有混合光滑性的Besov函数类的随机逼近算法的最优收敛阶,所得结果表明了某些情况下随机算法的收敛速度快于确定性算法。本项目的成果将对函数逼近、泛函分析、机器学习、信号处理等领域的研究起到引领、推动作用。