近年来,压缩感知和低秩矩阵恢复成为国内外应用数学和工程上极为热门和活跃的研究方向,它们的理论分析表明稀疏信号和低秩矩阵可以通过较少的线性测量恢复出来.压缩感知和低秩矩阵恢复理论已经在很多应用领域产生了重要的影响,如核磁共振成像,雷达,计算生物学,机器学习,量子物理以及在线推荐系统等.本文主要对压缩感知和低秩矩阵恢复问题中几个经典算法做了系统的理论分析.主要工作如下：首先,我们考虑压缩数据分离问题,即多成分数据在较少线性测量下的数据分离问题.本文研究的是多成分数据的不同成分分别在一般框架表示下稀疏的数据分离问题,所用的恢复算法是基于对偶框架的l1分解分析法.本文证明了当测量矩阵为Weibull(非Gaussian)随机矩阵并且框架之间满足相互相干性条件时,基于对偶框架的l1分解分析法能以极大概率恢复多成分数据的不同成分.其次,我们研究将投影梯度下降算法用于求解非凸Schatten-p(0<p<1)最小化问题.当线性测量映射满足矩阵限制同构性质时,我们证明了投影梯度下降算法是线性收敛的并且该算法是相对于噪声稳定的.最后,我们研究了迭代加权最小二乘算法用于求解带噪声低秩矩阵恢复问题的收敛性和稳定性,推广了已有文献中关于无噪声低秩矩阵恢复问题的迭代加权最小二乘算法的理论结果.我们不仅对于带噪声时该算法的收敛性进行了严格的证明,而且当线性测量映射满足矩阵限制同构性质时我们证明了该算法是相对于噪声稳定的.