压缩感知理论是一种充分利用信号稀疏性或者可压缩性的全新的信号采样理论。该理论表明,通过采集少量的信号值就可实现稀疏或可压缩信号的精确重建。该理论成功克服了采样数据量巨大,传感元、采样时间以及数据存储空间等物理资源浪费严重的问题,具有良好的实际应用前景。重建算法作为压缩感知过程中一个不可或缺的环节,其关键问题是如何从仅有的低维数据中最大程度地恢复出原始的高维数据。本文在深入研究现有重建算法和相关最优化理论的基础上,围绕它们展开深入研究,主要完成工作如下。对压缩感知重建算法中的子空间追踪算法进行了改进。本文在深入研究了基于压缩感知的正交匹配追踪、子空间追踪等经典重建算法之后,分析了各算法的原子更新过程。重点分析子空间追踪算法中的回溯过程,即在迭代过程中不断选中原子的同时剔除部分以前选中的原子,这种方式能否保证每轮剔除原子后迭代余量会下降,这是一个值得质疑的问题。针对该问题,本文提出一种迭代余量稳定下降的原子更新方法,通过实验证明,在相同迭代条件下,改进后的子空间追踪算法在重建质量上优于原始的子空间追踪算法。对基于光滑l0范数(Smoothed l0 Norm,SL0)的重建算法进行了改进。光滑l0范数用光滑函数近似l0范数,并与凸优化思想相结合进行求解,具体迭代过程采用最速下降法和梯度投影原理,逐步逼近最优解。本文在深入研究SLO算法的基础上,针对其近似l0范数估计函数的选取,引入双曲正切函数来近似l0范数；针对收敛速度方面的不足,提出了一种基于近似l0范数最小和修正牛顿法的重建算法(NSL0算法),该算法基于性能更好的双曲正切函数来近似l0范数,采用简单而有效的修正牛顿法实现最优值求解,取得较好的效果。本文在深入研究压缩感知理论及其重建算法之后,将其应用到数字水印技术中。数字水印技术是通过在原始数据中嵌入秘密信息——水印,来证实该数据的所有权归属。本文利用压缩感知的优良特性,在压缩感知域中完成数字水印的嵌入。测量矩阵充当了密钥的作用,由于其构造方法较多,且矩阵大小灵活多样,因此在未知密钥的情况下很难提取出水印信息。实验结果表明该方法对大多数攻击具有鲁棒性。