稀疏表示是线性表示中最具有代表性的方法,在信号处理,图像处理,机器学习,计算机视觉等领域都有广泛应用.站在不同的角度,这些方法可以被分为不同的类型.比如,根据稀疏限制中所使用的范数,这些方法可以被分成5类:1)l0范数最小化;2)lp范数最小化(0<p<1);3)l1范数最小化;4)l2,1范数最小化;5)l2范数最小化.根据算法的可行性,这些方法又可被分为:1)贪婪策略逼近;2)限制优化;3)基于邻近算法的优化策略;4)基于同伦算法的稀疏表示.l0范数下的稀疏表示方法能够获得稀疏解,但直接求解相应优化问题的过程是一个NP难问题,贪婪逼近策略的提出正是为了解决这个难题.与其它正则化算法相比,贪婪算法计算简便,易于实施,在计算上有着巨大的优势.贪婪算法通过在每次迭代过程中搜索局部最优解来逼近整体最优解,计算上的便利所付出的代价是算法的估计子与估计目标之间关系的不确定.但即使贪婪算法不能适用于所有问题,对许多特殊问题它仍能产生整体最优解,此时如何证明算法的有效性将是一项有意义的工作.基于贪婪算法的设计思想,本文对两类学习问题提出了不同的贪婪型算法,并分析了它们的统计表现.(1)贪婪算法在固定设计高斯回归问题中的分析对于固定设计高斯回归情形,本文提出了惩罚经验松弛贪婪算法,并且通过建立oracle不等式分析了算法的有效性.算法的主要步骤为:首先通过经验松弛贪婪算法输出估计子序列,然后通过惩罚算法的迭代次数以及字典的容量,寻找最优的估计子.P.Massart针对lasso算法建立了oracle型不等式,同时得到了一类相当广泛的模型选择引理.本文将该模型选择引理稍作推广,分别在字典有限,字典无限可数,字典无限不可数三种情形加以应用,得到了表现算法学习性能的oracle型不等式.结果显示误差界受到逼近误差,惩罚项,噪音水平的影响.特别的,当目标函数属于字典的凸包时,算法的收敛速率为O((?)).(2)贪婪算法在稀疏限制优化问题中的分析考虑了目标函数为一般损失函数(非平方损失)的稀疏限制优化问题,提出了稀疏共轭梯度法,共轭梯度追踪法及其变形算法,并分析了算法的有效性.Yuan和Lu(2009)对传统的PRP公式进行了改进,提出了新的共轭方向,在此基础上解决了无限制优化问题下,共轭梯度法的全局收敛性,获得了算法的收敛速度,且实验效果良好.受此启发,本文针对一类广泛的稀疏限制优化问题,建立了三种基于共轭梯度方向学习的贪婪型算法,理论分析显示当目标函数满足限制强凸条件与限制光滑条件时,算法均具有线性收敛速率.(3)贪婪算法在复值稀疏信号重构问题中的分析考虑了复值稀疏信号的恢复问题.由于建立在复变量上的平方损失函数在原点以外是处处不可导的,故基于梯度方向学习的算法无法直接应用在该问题上.D.H.Brandwood(1983)提出了类似于梯度算子的偏复向量梯度算子,并且发现目标函数的偏复向量梯度方向对应着函数变化最大的方向.故通过对偏复梯度方向的学习,本文提出了稀疏复梯度算法,复梯度追踪算法及其变形算法.经过分析发现当观测矩阵满足D-RIP条件时,平方损失函数具有与限制强凸条件与限制强光滑条件非常类似的性质,基于这些性质,我们得到了算法的线性学习速率.