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

AF：小：最小化和子空间跟踪的新算法和改进算法

• 批准号: 1115704
• 负责人: Jesse Barlow
• 金额: $ 35万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115704&HistoricalAwards=false
• 关键词: AF; Small; New; Improved; Algorithms

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.

Gram-Schmidt正交分解算法和Golub-Kahan-Lanczos(GKL)双对角化简算法产生了数值线性代数的两个基本分解。对这些算法的改进为本提案的主题“新的和改进的最小化和子空间跟踪算法”奠定了基础。这两种算法都是设计用来产生感兴趣的子空间的基的正交因式分解算法，并且对于这两种算法，稳定性分析是必要的，以考虑保持这些基的正交性的必要条件。基于新的Gram-Schmidt和GKL过程，提出了正则化最小二乘算法和跟踪矩阵主子空间的算法。利用PI和合作者在之前的NSF项目中开发的基于离散余弦和快速傅立叶变换的预条件，将正则化最小二乘算法扩展为基于牛顿的正则化总体最小二乘算法，该算法非常适合于图像去模糊问题。对块Gram-Schmidt和GKL双对角化算法的研究促进了科学界关于如何在现代计算环境中为数值线性代数中的两个基本算法开发高效软件的知识，数值线性代数是一个跨越计算科学和应用数学的核心领域。Gram-Schmidt算法在开发迭代方法以解决大量科学和工程学科中出现的大型线性方程组方面非常重要。GKL双对角线降维算法和子空间跟踪工作在统计学中降维的众多应用中是有用的，最著名的是网络搜索算法。双对角线缩减也是Netflix问题解决方案的关键组成部分，Netflix问题是根据客户已经评分的较小电影样本，在非常大的样本中识别客户喜欢观看的电影的问题。图像去模糊算法在高分辨率图像重建中占有重要地位。这些图像与高分辨率电视产生的图像类似，传输成本很高。总体最小二乘研究开发了一种算法，该算法将有助于从传输成本较低的低分辨率图像中恢复高分辨率图像。