大规模结构矩阵的预处理方法与理论及其在压缩感知中的应用

This project is based on the background of large-scale compressive sensing. According to the structural characteristics and sparsity of the structured matrices derived from signal reconstruction, this project systematically studies the efficient preconditioning technique for large sparse saddle point problems, including: 1) construct HSS-based and SOR-like iterative algorithms and preconditioners for the saddle point problem who has dominant skew-Hermitian part; 2) construct the relaxation-type preconditioners for large sparse saddle point problems according to the structural characteristics and sparsity of the coefficient matrix, further accelerate the computation speed for the related subspace method; 3) in the case of failure of fixed preprocessing, the efficient solution of large sparse saddle point problem can be realized by flexible preconditioning. The implementation of this project not only enriches the numerical solution of large sparse saddle point problems, but also builds a "bridge" for the interior point algorithm and large-scale signal reconstruction, improves the speed of reconstruction of compressed sensing signals and achieves high efficiency of the statistical properties of compressed signals analysis, provides theoretical basis and technical support for more large-scale engineering calculation involving or relying on saddle point problem.

本项目以大规模压缩感知为背景，根据信号重构中衍生的结构矩阵的特点及稀疏性，系统研究大型稀疏鞍点问题的高效预处理方法和理论，主要包括：1）建立反Hermitian部分占优鞍点问题基于HS分裂的迭代方法及SOR类算法，并构造相应预处理子，解决反Hermitian部分占优鞍点问题的求解困难；2）针对大型稀疏鞍点问题的结构特点及稀疏性，构建松弛型预处理子，进一步加快子空间方法求解的计算速度；3）在固定预处理失效时，通过变化预处理手段来实现大规模稀疏鞍点问题的高效求解。本项目的实施不仅能丰富大型稀疏鞍点问题的数值解法研究，也能为内点算法和大规模信号重构搭建“桥梁”，提高压缩感知信号重构的速度，并实现压缩信号统计特性的高效分析，为更多涉及或依赖鞍点问题求解的大规模工程计算提供理论依据和技术支持。

本项目以大规模压缩感知为背景。根据信号重构中衍生的结构矩阵的特点及稀疏性，系统研究大型稀疏鞍点问题的高效预处理方法和理论，主要包括：1）建立反Hermitian部分占优鞍点问题的迭代方法及SOR类算法；2）针对大型稀疏鞍点问题的结构特点及稀疏性，构建松弛型预处理子，加快子空间方法的求解速度；3）通过变化预处理方法来实现和改善固定预处理失效时大型鞍点问题的求解的高效求解。通过三年研究，本项目取得的主要研究进展、重要结果和关键数据有：1）已完成求解反Hermitian部分占优鞍点问题的SOR方法的建立，同时还针对Hermitian部分对角占优鞍点问题，设计建立了一类非精确块状SSOR-like预处理子；2）基于前期已有的关于松弛型预处理子的成果，对求解非对称鞍点问题的RDPSS预处理子的正规矩阵进行了详细的分析，解决了正规矩阵的选择困难问题；3）本项目将矩阵计算和鞍点问题求解的数值方法成功运用到信号处理、压缩感知和图像处理等领域，在信号处理凸优化和图像去噪方面取得了突破性结果。针对大型稀疏鞍点问题的特定结构及性质构造高效预处理算法,提高子空间方法的求解速度并节省内存空间,对于大规模信号重构等热点工程计算问题具有重要的实际意义.从目前项目已取得的成果看来，项目在信号处理、凸优化以及图像去噪等方面都有很强的应用前景，因此本项目的研究具有很强的科学意义。