大规模结构总体最小二乘问题的快速算法研究

In the age of "big data", the quick and efficient processing of large-scale high-dimensional data is becoming more and more significant. Total least squares (TLS) is an important method in the area such as signal processing and image deblurring. Fast and accurate computation for TLS is the basis for high-performance computing in big data processing. On the one hand, the coefficient matrix of TLS in practical applications is often structured (such as Toeplitz-like) and large-scale, hence solving TLS by traditional methods will be very costly. Based on this background, this project will design fast approximate numerical methods for large-scale structured TLS to guarantee the accuracy by combining randomized algorithms for matrix approximations, hierarchically semiseparable matrix representation and nonconvex optimization, et al. On the other hand, in many practical applications high-dimensional data is acquired incrementally. Hence corresponding incremental numerical methods for solving multidimensional TLS problem will be developed. We will also develop a software and perform extensive numerical simulations.

大数据时代对快速高效地处理大规模高维数据有着越来越高的要求。总体最小二乘作为信号处理、图像去噪等领域的一种重要手段，其准确、快速的计算是高效大数据处理的基础。一方面，实际问题对应的总体最小二乘问题的系数矩阵一般具有特殊结构（Toeplitz、类Toeplitz等），用经典的方法来求解此问题面临规模巨大和问题非凸的困难。基于此研究需要，本课题将结合低秩矩阵分解的随机算法、分层矩阵半分离表示、非凸优化等方法，在保证计算精度的前提下，对Toeplitz等结构的大规模总体最小二乘问题给出近似的快速求解算法。另一方面，在很多实际应用中高维数据的样本是逐个获取的，对此开发针对大规模多右端项总体最小二乘问题的渐近数值解法。最后研制相应的计算软件并进行精细化的数值模拟。

总体最小二乘作为信号处理、图像去噪等领域的一种重要手段，其准确、快速的计算是高效大数据处理的基础。主要研究内容：（一）在低秩逼近的概率方法和最小二乘问题的随机算法的框架下，设计单右端项总体最小二乘问题的随机算法；（二）由于张量可以在高维的空间中保留数据的结构信息，设计基于t-张量积的增量张量正则化最小二乘算法，使算法以增量方式计算右端项含多个侧向切片的张量正则化最小二乘问题的解；（三）建立正交张量的CS分解和张量的广义奇异值分解；（四）研究t-张量积运算下的张量不等式；（五）建立基于t-张量积的广义逆和方程组的扰动分析结果。. 本项目的研究成果有以下几个方面：. 1）我们对中等规模总体最小二乘问题提出了Nystrom方法。对于大规模不适定情形，以已知或者估计的秩作为正则化参数, 我们介绍了随机的截断总体最小二乘算法（RTTLS）。我们分析了算法RTTLS的精确性，并进行数值实验以检验随机算法的效率。这些随机算法以很高的概率在保持计算精度的情况下大大减少计算时间。. 2）我们通过求解一个右端项只含有一个侧向切片的张量正则化最小二乘问题来更新问题的解，而不是重新求解该问题。该算法非常适合于大数据集和实时操作。. 3）我们分析了张量CS分解和广义奇异值分解的结构并提出了相应的算法。张量的广义奇异值分解可应用于推导张量Tikhonov正则化问题解的显式表达式。. 4）我们证明了包含张量幂的不等式与矩阵情形是相似的，同时研究了张量范数不等式。将著名的算术-几何平均不等式、Holder不等式和Minkowski不等式推广到张量。进一步地，我们也得到了一些张量特征值不等式。. 5）我们建立了张量逆、张量Moore-Penrose逆和基于t-张量积的张量系统的扰动分析。在结构扰动的情况下，我们将Sherman-Morrison-Woodbury（SMW）公式推广到t-张量积的情形。SMW公式可用于张量多线性方程组的敏感性分析。