Spectral Methods: Algorithms and Applications

谱方法：算法和应用

• 批准号: 0634904
• 负责人: Daniel Spielman
• 金额: --
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-10-01 至 2010-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0634904&HistoricalAwards=false
• 关键词: Spectral; Methods; Algorithms; Applications

Abstract--------Problems in many areas where the input data is a matrix have been tackled by Spectral Methods which use low-rank approximations to the input matrix. In the important application area of Clustering, only known proofs that the methods succeed have to make the unrealistic assumption that all entries of the matrix arestatistically independent. This research removes this important impediment to the wider use of the method by developing the theory and algorithms that work under limited independence, a much more realistic assumption. To illustrate, in one example - document-term matrices - this research assumes only that thedocuments are statistically independent, not the terms in each document.The research also generalize the methods developed for limited independence to deal with matrix-valued random variables which are of interest in several areas and to date have no substantial work on them. The PI and supported students will extend the applications of spectral-like methods to tensors - multi-dimensional arrays. It is expected that the research here will be one of the key bridges between theory and practice in thisarea, thus leading to a broad transfer of theoretical developments into practice in time.

摘要-输入数据是矩阵的许多领域中的问题已经通过对输入矩阵使用低阶近似的频谱方法来解决。在聚类的重要应用领域，只有已知的方法成功的证明必须假设矩阵的所有项都是统计独立的，这是不现实的。这项研究通过开发在有限独立性下工作的理论和算法，消除了该方法更广泛使用的这一重要障碍，这是一个更现实的假设。为了说明这一点，在一个例子--文档-术语矩阵--中，本研究只假设文档在统计上是独立的，而不是每个文档中的术语。研究还推广了为有限独立性而开发的方法，以处理几个领域中感兴趣的矩阵值随机变量，并且到目前为止还没有对它们进行实质性的研究。PI和被支持的学生将把类谱方法的应用扩展到张量-多维阵列。预计这方面的研究将成为这一领域理论与实践之间的重要桥梁之一，从而使理论发展及时广泛地转化为实践。