矩阵分解问题的优化算法与理论

Eigenvalue and Singular value decomposition and matrix low rank decomposition are the fundamental tools for many emerging sophisticated optimization problems such as semi-definite programming, matrix rank minimization problems, and some other applied mathematical problems like principal component analysis problems in statistical learning and nonlinear eigenvalue problems in scientific computing. Therefore, the algorithms for matrix decompositions typically determine the effectiveness and efficiency of the above-mentioned mathematical models in solving application problems arising from image processing, medical imaging, statistic learning, artificial intelligence, material science and electronic commerce. In the era of big data, the rapidly increasing magnitude of data brings a huge challenge to the existent matrix decomposition solvers. To meet the new requirements and to be qualified for solving problems with big data, we do need revolutional algorithms. Hence, this project mainly focuses on the optimization algorithms and theory for matrix decompositions. To address the special characteristics of the scientific engineering problems with big data, we aim to design effective subspace approaches and distributed optimization algorithms to solve the arisen matrix decomposition problems. The new algorithms will have great improvement in the efficiency, storage and scalability. We will also study the theoretic properties of the new approaches such as convergence, complexity and stability.

矩阵特征值、奇异值分解与矩阵低秩分解是求解许多复杂优化问题--如半定规划问题、矩阵的秩极小化问题，和其它应用数学问题--如统计学习中的主成分分析问题、科学计算中的非线性特征值问题的基础工具。因而矩阵分解算法的性能往往决定了上述数学模型应用在图像处理、医学成像、统计学习、人工智能、材料科学、电子商务等科学工程领域的效果与效率。随着大数据时代的到来，数据规模不断扩大，已有的矩阵分解算法面临着巨大的挑战。要使得矩阵分解能够继续胜任来源于大数据背景下的实际应用问题，我们迫切需要革命性的新算法。 基于此本项目主要研究矩阵分解问题的优化算法及其理论性质。针对大数据背景下实际科学工程应用问题的特点，我们拟设计高效的子空间法、分布式优化算法等方法来求解应用于这些问题中的矩阵分解模型，以期所设计的新算法在效率、存储、可扩展性等方面都较已有算法有大幅改进。我们还将分析新算法的收敛性、复杂性、稳定性等理

线性和非线性特征值问题、矩阵低秩分解问题在材料计算、统计、反问题等科学领域；图像处理、数据分析等工程领域有着重要的应用。这些问题往往都可以转换为非凸优化模型。我们的研究在如下几个方面展开：我们对这些问题都设计了高效的算法，并分析了理论性质；对于线性特征值问题，解决了正交约束可扩展性差的瓶颈难点，设计了可并行的优化算法，并通过数值实验验证了其可扩展性；对于非线性特征值问题，我们分析了它的解同对应的能量极小问题最优解的关系；对于矩阵低秩分解问题，我们分析了在一定条件下，其全局最优性等价于二阶稳定性，因此我们可以通过局部优化算法找到其全局极小。本项目的研究应用在矩阵完整化、鲁棒主成分分析、材料计算等领域中都取得了令人满意的数值结果。