矩阵分解的随机算法、随机扰动分析及其应用

This project will investigate the stochastic algorithms and stochastic perturbation analysis of matrix factorizations and their applications. Firstly, for large matrix with low rank, we will design the stochastic algorithms of some classic matrix factorizations, hyperbolic matrix factorizations, and matrix factorizations of matrix pencil using the random projection methods with some structured random matrices, the random sampling methods with the importance sampling distribution, and the regular algorithms for matrix factorizations of small matrix, and discuss their error analysis using the theory of regular error analysis, the theory of (stochastic) perturbation analysis for matrix factorizations, and the theory of probability-statistics. Then, with the matrix equation approach, the matrix-vector equation approach, the technique of Lyapunov majorant function, the fixed point theorems, and the technique of splitting operators, and combining some results of probability-statistics (such as the Markov inequality, the Chebyshev inequality, and the Slutsky theorem) and the properties of random matrix, we will study all types of condition numbers and perturbation bounds in the average and probabilistic senses of matrix factorizations under the stochastic perturbation, and consider the statistics estimates and algorithms of the obtained condition numbers and perturbation bounds using the probabilistic spectral norm estimator and the small-sample statistical condition estimation. Finally, the stochastic algorithms and stochastic perturbation analysis of the (constrained) indefinite least squares problem will be discussed based on the above results.

本项目拟研究矩阵分解的随机算法、随机扰动分析及其应用。首先，针对大型低秩矩阵，利用与各种结构随机矩阵相结合的随机投影方法、与重要抽样分布相结合的随机抽样方法、小型矩阵分解的传统算法等，设计部分经典矩阵分解、双曲矩阵分解、矩阵对的矩阵分解的随机算法，并利用传统的误差分析、矩阵分解的(随机)扰动分析与概率统计理论等探讨算法的误差分析；其次，利用矩阵方程方法、矩阵向量方程方法、Lyapunov 受控函数技术、不定点定理、算子分拆技术等，并结合概率统计的相关结论(如Markov 不等式、Chebyshev不等式、Slutsky 定理等)与随机矩阵的相关性质等，研究各种矩阵分解在随机扰动下基于平均意义与概率意义的各类型的条件数与扰动界，并利用概率谱范数估计、小样本统计条件估计等探讨条件数与扰动界的统计估计与算法；最后，结合上述结果探讨(约束)不定最小二乘问题的随机算法与随机扰动分析。

大数据时代，矩阵分解的很多经典确定性算法因计算与存储成本而难以胜任。本项目基于随机投影、随机抽样等随机思想，并结合一些概率分布的参数估计、贝叶斯后验估计等统计估计方法，设计了矩阵LU分解、Cholesky分解、奇异值分解等矩阵分解的随机算法，并探讨了算法在概率与期望意义下的误差分析及应用等，所得算法可用于大数据时代的一些数值代数问题，如线性系统、最小二乘问题、特征值问题等的求解，所得误差分析为算法的有效性提供了理论保证；基于随机矩阵，如Gaussian随机矩阵、次Gaussian随机矩阵等的相关性质，并结合矩阵分解、分块矩阵、非负矩阵、矩阵向量方程、Lyapunov受控函数、不定点定理等的相关结论，给出了矩阵QR类分解、Cholesky类分解、LU类分解、矩阵分解更新问题、特征值问题、矩阵方程等的扰动分析，所得扰动界、扰动区间、条件数、条件数的随机估计等可用于评估问题的敏感性、现有算法的有效性等，进而可据此设计更高效的算法，服务于大数据时代一些问题的求解；利用随机迭代方法、概率谱范数估计、小样本统计条件估计、矩阵微分等，并结合贪婪策略、矩阵Kronecker乘积、向量算子、矩阵范数的相关知识，获得了最小二乘问题、不定最小二乘问题、总体最小二乘问题、约束最小二乘问题等的随机算法、条件数、条件数的随机估计等，所得算法具有较低的计算成本，所得统一型条件数统一了文献中的范数型、分量型、混合型条件数。针对上述成果共发表或录用学术论文32篇，其中SCI检索论文29篇。此外，培养毕业博士留学研究生2名，培养毕业学术硕士研究生3名，培养在读博士研究生3名，培养在读硕士研究生9名(含专业硕士研究生4名)。