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和支持的学生将扩展类谱方法的应用到张量-多维数组。预计这里的研究将成为该领域理论与实践之间的关键桥梁之一，从而导致理论发展及时广泛转移到实践中。