Stable and efficient computation of the CS decomposition

CS分解的稳定且高效的计算

• 批准号: 0914559
• 负责人: Brian Sutton
• 金额: $ 10.8万
• 依托单位: Randolph-Macon College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914559&HistoricalAwards=false
• 关键词: Stable; efficient; computation; CS; decomposition

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The CS decomposition is a matrix decomposition related to the eigenvalue and singular value decompositions. It applies to any unitary matrix partitioned into a 2-by-2 block structure, and the effect is to simultaneously diagonalize all four blocks. By orthogonality, the entries of the resulting diagonal blocks must be the cosines and sines of some angles, leading Stewart to coin the term CS (cosine-sine) decomposition for his 1977 discovery. The decomposition can reveal the canonical angles between linear subspaces, studied as early as 1875 by Jordan, and the canonical correlations between two sets of observed variables, introduced by Hotelling in 1936. The current proposal focuses on computational aspects of this matrix decomposition. The first goal is the stable computation of the full form of the decomposition, as originally formulated by Stewart. As described above, this may be called a 2-by-2 CSD. Prior methods compute a reduced form, the 2-by-1 CSD, which in a sense is half of the full 2-by-2 form. Attempts at extending existing methods for the 2-by-1 CSD to the full 2-by-2 CSD have not been successful. A proof of stability for a recent algorithm described by the investigator, designed from the ground up to compute the full 2-by-2 CSD, is sought. Another goal of the project is to analyze the stability and efficiency of the algorithm when specialized to the 2-by-1 CSD and the GSVD, comparing with existing methods. A third goal is the investigation of an alternative algorithm based on a divide-and-conquer scheme, in addition to the QR iteration-approach of the investigator's first algorithm. Finally, possible applications enabled by the stable computation of the 2-by-2 CSD will be explored.A matrix decomposition is a mathematical tool for breaking a matrix, a rectangular array of numbers, into a product of simpler matrices. These simpler matrices often reveal important structure. The eigenvalue matrix decomposition can distinguish between stability and instability in engineering applications and can reveal the prominence of web pages when performing Internet searches. The singular value matrix decomposition can infer the roles of genes from indirect observations and provides a key component in facial recognition. The subject of this project is another matrix decomposition, the CS (cosine-sine) decomposition. This decomposition can be used to compare and contrast underlying factors present in two data sets. An example is provided by Hotelling, who proposes the analysis of heritable traits by comparing and contrasting mother rat and daughter rat. The computation of the CS decomposition has proved more difficult than that of the eigenvalue and singular value decompositions. This project seeks to improve the accuracy and speed of computation. In addition, this project will consider a more general form of the CS decomposition than earlier studies, opening the possibility of new applications.

该奖项由2009年《美国复苏和再投资法案》(公法111-5)资助。CS分解是与特征值和奇异值分解相关的矩阵分解。它适用于任何分割成2乘2块结构的酉矩阵，其效果是同时对角化所有四个块。根据正交性，得到的对角线块的条目必须是某些角度的余弦和正弦，这导致斯图尔特在1977年的发现中创造了术语CS(余弦-正弦)分解。这种分解可以揭示早在1875年由Jordan研究的线性子空间之间的正则角，以及由Hotling在1936年引入的两组观测变量之间的正则相关性。目前的建议侧重于这种矩阵分解的计算方面。第一个目标是稳定地计算分解的完整形式，就像斯图尔特最初提出的那样。如上所述，这可以被称为2x2CSD。现有方法计算简化形式2×1 CSD，其在某种意义上是完整的2×2形式的一半。试图将2x1 CSD的现有方法扩展到完整的2x2 CSD，但没有成功。研究人员最近描述的一种算法的稳定性被寻求证明，该算法是从头开始设计的，用于计算完整的2乘2 CSD。该项目的另一个目标是分析算法在专门针对2×1 CSD和GSVD时的稳定性和效率，并与现有方法进行比较。第三个目标是研究基于分而治之方案的替代算法，除了调查者第一个算法的QR迭代方法。最后，我们将探讨2×2 CSD的稳定计算可能带来的应用。矩阵分解是一种数学工具，用于将矩阵(一个矩形数字阵列)分解为更简单的矩阵的乘积。这些更简单的矩阵通常揭示出重要的结构。特征值矩阵分解可以区分工程应用中的稳定性和不稳定性，并可以在进行互联网搜索时揭示网页的突出程度。奇异值矩阵分解可以从间接观测中推断基因的作用，是人脸识别中的关键组成部分。这个项目的主题是另一种矩阵分解，CS(余弦-正弦)分解。这种分解可用于比较和对比两个数据集中存在的潜在因素。霍特林提供了一个例子，他提出了通过比较母鼠和子鼠来分析可遗传特征的方法。已证明CS分解的计算比特征值和奇异值分解的计算更困难。该项目旨在提高计算的精度和速度。此外，本项目将考虑CS分解的一种比以前研究更一般的形式，从而打开了新应用的可能性。