中文摘要：

近年来，随着信息技术的快速发展，人们对高频信号的处理需求愈来愈大。由于受Shannon-Nyquist采样定理的限制，对于高频信号的采样与重建过程十分具有挑战性。压缩传感是一种新兴的利用信号稀疏性与可压缩性的信息获取与处理技术。本项目旨在研究压缩传感中循环测量的理论与快速重建算法。由于从不完全测量中寻找最稀疏的信号是一个高度非线性的优化问题，纯随机采样给计算带来很大困难。本项目中，我们（1）通过理论分析与数值实验的方法对各种循环测量矩阵与稀疏变换之间的非相关性进行系统研究，并建立重建稀疏信号所需循环测量的下界；（2）设计能够充分利用循环结构以及快速Fourier变换的数值计算方法从不完全测量以及各种正则化模型中恢复目标信号；（3）利用问题的结构特性，在理论分析与计算实践相结合的基础上，编写高效的可供工程技术界应用的软件程序。

结论摘要：

本项目以压缩传感中循环结构测量为主题对其中的结构型优化问题深入展开理论与算法研究，取得了重要的研究成果，已在国际期刊上发表7篇学术论文，其中5篇发表在SIAM系列、Mathematics of Computation、Inverse Problems and Imaging等有重要国际学术影响的期刊上，另有1篇论文已被Journal of Optimization: Theory and Applications接受。 通过该项目研究，主要取得如下成果。第一，提出并研究了求解压缩传感问题中L1问题的交替方向算法，并受到广泛关注。在该研究的驱动下，此类算法越来越受到更广泛的关注，并已应用到诸多领域，包括图像与信号处理、矩阵补全、机器学习等。第二，研究了线性化的交替方向法，并应用于矩阵补全问题。第三，将研究成果推广到了更广泛的问题，包括图像重建，稀疏低秩矩阵分解等。第四，为克服交替方向法等一阶算法对参数的敏感性，提出并研究求解Group Lasso问题的临近点算法，子问题应用高阶算法求解，取得了良好的数值效果。另外，我们已将解压缩传中L1问题的交替方向法编写成了软件包，可以供工程界使用。该软件包自2011年至今已先后被下载累计3000余次，这充分说明了该算法应用的广泛性。求解Group Lasso问题的临近点算法软件包还在调试与改进中，目前尚未公开。 上述研究成果的主要意义在于，提出并研究了简单、易于实现和推广的一阶算法，在一些对解的精度要求不是太高，而对处理速度要求苛刻的领域中有着广泛的应用前景。另外，当解的精度要求较高时，我们提出的数值稳定、稳健的PPA算法既有理论上的收敛性保证，又有着更好的数值表现，在相关应用中可以发挥重要作用。