求解欠定线性方程组在机器学习,信号处理,压缩感知,线性逆问题以及统计推断等领域有广泛的应用.作为稀疏优化的分支,压缩感知问题可通过求解极小化1-范数正则项问题处理.这样得到的问题因其正则项的非光滑性而颇具挑战.本论文提出两种求解压缩感知问题的算法,分别用修正的共轭梯度法和交替方向法求解大规模稀疏优化问题,给出一定条件下算法收敛性定理,并通过数值试验验证算法有效性.第一部分,给出稀疏优化和压缩感知的定义,列出应用稀疏优化求解压缩感知问题的算法的最新研究进展,给出本论文研究的理论基础并列出文中所用到的一些基本概念,符号,定义.第二部分,受Nesterov的光滑化技巧启发,提出一种利用三项结构的Polak-Ribi`ere-Polyak共轭梯度法求解稀疏信号恢复中的1-范数最小二乘问题的算法.每次迭代该算法只需求解三次矩阵-向量乘积运算.算法所应用的理论基础保证了算法的全局收敛性.其次,该算法通过连续性技巧加速,数值试验表明该连续性技巧明显提高了算法的执行效率.算法的执行效果优越于同样使用Nesterov的光滑化技巧和梯度法的NESTA算法.第三部分,分别基于原始模型和对偶模型,提出两种求解包含1-范数正则项和1-范数数据拟合项优化问题的交替方向法.该算法交替地极小化原始问题和对偶问题的增广Lagrangian函数.通过使用一维收缩算子或欧氏投影,所有子问题都存在显式解.算法每次迭代仅需求解两次矩阵-向量乘积运算,从而很容易实现.最后给出一定条件下算法的全局收敛性,并讨论了算法在非负信号复原问题以及赋权值的正则项极小化问题中的应用.数值试验说明该算法优于著名的YALL1算法.最后,给出本文的总结,并提出一些值得继续探讨的方向.