多层次结构化矩阵低秩逼近与稀疏表示方法建模与算法研究

The theories of low-rank decomposition, structured decomposition and sparse representation of a matrix have been widely used in a great deal of scientific and engineering fields. In recent years, the relevant theories have been deeply studied and made great progress. The project mainly focuses on: (1) the existence of solutions and algorithms for the low-rank approximation model with multi-level and multi-structural constraints and the low-rank approximation model with banded structure constraints, the algorithms for the multi-objective structured low-rank approximation model under different metrics and stability of the solutions under noise perturbations, (2) giving the best approximation solution of rank k to the structured low rank sparse representation problem by using the matrix polynomial of rank 1, reconstructing the low-rank part and sparse part of a observation matrix with defect data, studying the existence of solutions and algorithms for the structured low- rank approximation model with sparse noise, (3) construction of preconditioned algorithms for solving the linear complementary problem with its coefficient matrix belonging to a special class of matrix and studying the stability of the preconditioned algorithms with sparse noise, construction of the new complementary function and structure of complementary standards and studying the structure solutions and sparse solutions under the above standards. The research results of the project will provide efficient algorithms and theoretical basis for solving the problem of multi-level structured low-rank approximation of a matrix, the model of structured low-rank sparse representation and structured sparse solution of linear and nonlinear complementary problem.

矩阵的低秩分解、结构化分解以及稀疏表示理论在众多科学工程领域中都有广泛的应用。近年来，相关理论得到深入研究并取得重大进展。本项目主要研究：（1）多层次、多结构低秩逼近模型和带带状约束条件的低秩稀疏表示模型解的存在性和算法；不同度量标准下多目标结构化低秩逼近模型求解算法及其在噪声扰动下解的稳定性；（2）用秩1矩阵多项式给出结构化低秩稀疏表示问题秩为k的最佳逼近解；重构具有缺损数据的观测矩阵的低秩和稀疏部分；研究带有稀疏噪声结构化低秩逼近模型解的存在性和求解算法。（3）构建求解系数矩阵为特殊类矩阵线性互补问题的预处理算法，并研究稀疏噪声干扰下预处理算法的稳定性；构建互补问题新的互补度函数和结构互补标准，并研究此标准下互补问题的结构解和稀疏解。项目的研究成果将为求解多层次结构化矩阵的稀疏低秩逼近问题、结构化低秩稀疏表示模型和线性与非线性互补问题的结构化低秩、稀疏解提供有效算法和理论基础。

矩阵低秩逼近方法是解决高维数据降维的有效技术，是从大规模、高维复杂数据中提取特征的一种有效方法，该问题的研究对海量数据处理、复杂信息加工、稀疏特征提取具有重要意义。项目主要聚焦以下内容的研究：. （1）多层次结构化矩阵低秩逼近、结构化低秩稀疏表示方法：提出了快速梯度下降算法、交替更新迭代算法、交替极小化更新算法以及加速增广拉格朗日算法，设计了多分块可分离凸优化模型，提出了参数临近点算法、修正增广拉格朗日方法、大步长广义对称交替方向迭代法和广义对称ADMM法、外推二次正则投影BB算法等，从理论上分析了算法的收敛性，数值实验印证了所构建算法的有效性。. （2）结构化线性互补问题数值解法和预条件方法：主要研究了M-矩阵线性互补问题的预处理迭代算法，以及五类特殊矩阵线性互补问题数值解的存在性和误差界估计问题，理论上证明了所构造算法的收敛性和所给出误差界的有效性，特别是，通过构建一类新的H-矩阵，即S-QN 矩阵，为相关线性互补问题的误差界研究提供了一种新的思路。. （3）大规模稀疏代数系统的数值解法：针对一些具有实际背景的Stokes问题、线性化不可压缩Navier-Stokes方程、加权Toeplitz最小二乘问题中产生的鞍点问题，提出了多种数值解法和多类型含多参数的预条件子，理论上证明了算法的收敛性和预处理矩阵的最佳选择策略。对奇异M-矩阵的代数Riccati方程、参数化代数Riccati方程以及非对称代数Riccati方程，研究了解的存在性和所设计算法的收敛性。基于Givens矩阵，研究了几类具有特殊带状结构的H-矩阵的逆特征值问题，给出了实现算法。. 项目研究期间共完成科研论文31篇，其中已正式发表SCI期刊论文26篇，已在线SCI论文4篇；培养博生研究生10人，其中4位已获得博士学位；培养硕士研究生8人，其中3位同学已获得硕士学位。