压缩感知，是近几年在信号处理领域出现的新颖的采样理论，该理论显示，通过采集相对较少的感兴趣的信号值就可实现稀疏的或可压缩信号的精确重建，这样就使得信息获取、存储、处理和传输的成本大大降低。压缩感知理论的前提条件是信号是稀疏的或者可压缩的，核心问题是如何从相对较少的低维数据中最大概率地恢复出原始的高维数据，由此可见，重建算法是压缩感知理论中一个非常重要的部分。本文在深入研究压缩感知理论的同时，着重研究了重建算法，从匹配追踪和最优化理论两个方面进行分析，并改进了一种凸优化重建算法，最后，在阐述了数字水印技术后，把压缩感知理论运用到数字水印中。本文主要完成工作如下：介绍了压缩感知重建算法的凸优化算法，并改进内点算法来完成压缩感知的稀疏重建，在重建过程中，引用连续性不断减小一个控制参数，来加快算法的收敛，减少运行时间。这里完全转化为严格意义上的数学模型求解欠定线性方程组，首先采用对数障碍法转化目标函数，使目标函数是凸的可微的，然后采用牛顿迭代逐渐对目标函数递减，当误差精度达到我们能接受的范围时结束。该算法在保证质量的同时，在时间复杂度方面取得较好的效果。将压缩感知运用到数字水印技术中。经过深入研究压缩感知和数字水印后，我们将压缩感知运用到数字水印中，其运用主要表现在两个方面：对水印的预处理和基于压缩感知域的水印嵌入提取方法。由于压缩感知理论所具有的特性，不管是对水印的预处理还是在压缩感知域中嵌入水印，测量矩阵都充当了密钥的作用，并且测量矩阵的选择多种多样，因此在不知道密钥的情况下很难提取或破坏水印信息。最后本文实验结果表明该方法具有可行性，而且对大多数攻击具有鲁棒性。