AF: Small: New and Improved Algorithms for Minimization and Subspace Tracking

Gram—Schmidt正交因子分解算法和Golub—Kahan—Lanczos （GKL）双对角约简算法产生了数值线性代数的两个基本因子分解。这些算法的增强为“新的和改进的最小化和子空间跟踪算法”提供了基础，这是本提案的主题。这些都是正交分解算法，旨在为感兴趣的子空间产生基，对于这两种算法，稳定性分析是必要的，以考虑保持这些基正交的必要条件。这些算法也适应于基于矩阵-矩阵操作，从而使它们可以使用3级BLAS和稀疏BLAS例程来实现，这是使它们在现代架构上高效所必需的。在新的Gram—Schmidt和GKL过程的基础上，提出了正则化最小二乘和矩阵主子空间的跟踪算法。使用由PI和合作者在之前的NSF项目中开发的离散余弦和基于快速傅立叶变换的预调节器，将正则化最小二乘算法扩展为基于牛顿的正则化总最小二乘算法，该算法非常适合于图像去模糊问题。对块Gram- Schmidt和GKL双对角化算法的研究推进了科学界如何在现代计算环境中为数值线性代数中的两种基本算法开发高效软件的知识，这是一个跨越计算科学和应用数学的核心领域。Gram- Schmidt算法在开发求解大型线性方程组的迭代方法中非常重要，这些迭代方法出现在一长串科学和工程学科中。GKL双对角约简算法和子空间跟踪工作在统计学中的许多降维应用中很有用，最著名的是web搜索算法。双对角线缩减也是解决Netflix问题的关键组成部分——这个问题是根据客户已经评价过的更小的电影样本，在一个非常大的样本中确定客户会喜欢看哪些电影。图像去模糊算法在高分辨率图像重建中具有重要意义。这些图像与高分辨率电视产生的图像类似，传输成本很高。总最小二乘研究开发了一种算法，可用于从传输成本较低的低分辨率图像中恢复高分辨率图像。

The Gram--Schmidt orthogonal factorization algorithm and the Golub--Kahan--Lanczos (GKL) bidiagonal reduction algorithm produce two fundamental factorizations for numerical linear algebra. Enhancements to these algorithm provide the foundation for the ``New and Improved Algorithms for Minimization and Subspace Tracking'' that are the subject of this proposal. These are both orthogonal factorization algorithms designed to produce bases for subspaces of interest and, for both algorithms, stability analyses are necessary to consider what is necessary to keep these bases orthogonal. The algorithms are also adapted to be based upon matrix--matrix operations, thereby making them implementable using the level-3 BLAS and sparse BLAS routine necessary to make them efficient on modern architectures.Based upon the new Gram--Schmidt and GKL procedures, regularized least squares and algorithms for tracking the leading principal subspace of a matrix are developed. Using discrete cosine and fast Fourier transformbased preconditioners developed by the PI and collaborators in a previous NSF project, a regularized least squares algorithm is extended into a Newton--based regularized total least squares algorithm that is well suited to image deblurring problems. The research on the block Gram--Schmidt and GKL bidiagonalization algorithms advance the scientific community's knowledge of how to develop efficient software in modern computing environments for two fundamental algorithms in numerical linear algebra, a core field that straddles computational science and applied mathematics. The Gram--Schmidt algorithms are important in the development of iterative methods for the solution of large systems of linear equations arising in a long list of scientific and engineering disciplines. The GKL bidiagonal reduction algorithm and subspace tracking work is useful in the numerous applications of dimension reduction within statistics, most notably web search algorithms. Bidiagonal reduction is also a key component in the solution of the Netflix problem--the problem of identifying which films a customer would enjoy watching among a very large sample based upon a smaller sample of films which he/she has already rated. The image deblurring algorithms are important in the reconstruction of high-resolution images. These images, similar to those produced by high-resolution television, are expensive to transmit. The total least squares research develops an algorithm that would be useful in recovering a high-resolution image from cheaper-to-transmit lower resolution images.