压缩感知（Compressed Sensing，CS）是针对稀疏信号或可压缩信号的一种新理论，该理论打破了传统奈奎斯特（Nyquist）采样定律，是信号采集方式的一种大胆革新，有着非常广阔的应用前景。在压缩感知过程中，重建算法是关键的一部分，重建算法的优劣对采样过程的准确性验证及对信号的精确重建意义重大。本文侧重在压缩感知重建算法的研究,主要创新成果如下：(1)信号的稀疏重建已经广泛应用到信号处理和压缩传感中。为了实现这一工作，我们需要解决一个l1范数极小化问题。由于目标函数是非光滑的，所以问题的解决很复杂。我们在这篇文章中提出了带投影的修正Polak-Ribie`re-Polyak (PRP)共轭梯度算法来恢复压缩传感中的稀疏信号。算法的构造包括两个主要方面。首先，将l1范数的最小二乘问题转化为一组非线性单调方程组。然后，采用一个带投影的PRP共轭梯度算法来求解这一单调方程组。算法是容易实施的，因为在算法迭代的每一步，仅需要矩阵的向量乘积信息。由于共轭梯度的低存储需求，所以算法是有效的。在适当的条件下，我们确立了算法的全局收敛性。实验结果表明算法在恢复稀疏信号方面是实用的的有效的。(2)我们还研究了一个非单调的自适应谱梯度算法来求解由压缩传感问题中稀疏信号恢复问题转化为的l1最小化问题。在算法迭代的每一步，生成的搜索方向均具有下降性质，而且搜索方向容易通过极小化一个局部近似二次模型得到。此外，我们在提出搜索方向的同时还采用了一种非单调的线性搜索策略，在适当的条件下我们证明了算法的全局收敛性。实验结果表明算法是有效的，能够与流行的算法NBBL1和两步IST (TwIST)法相媲美。