AF: Small: Spectral analysis, spectral algorithms, and beyond

AF：小型：光谱分析、光谱算法等

• 批准号: 0915251
• 负责人: James Lee
• 金额: $ 50万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2013-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915251&HistoricalAwards=false
• 关键词: AF; Small; Spectral; analysis; spectral

TITLE: Spectral analysis, spectral algorithms, and beyond Spectral algorithms and spectral analysis form the basis for some of the most efficient and effective techniques in areas ranging from machine learning to scientific computing, from graphics to data mining, and from collaborative filtering to VLSI design. They also play a prominent role in combinatorial optimization, where they are used in algorithms for graph partitioning and constraint satisfaction. Despite the apparent utility of spectral techniques and the intense effort devoted to their analysis, our ability to reason about them rigorously is still very limited. This project addresses the development of an algorithmically-centered theory of spectral analysis which draws upon tools from contemporary mathematics, and is inspired by experimental evidence which has, so far, eluded a satisfactory theoretical explanation. The project also addresses the relative power of spectral methods from the viewpoint of computational complexity.This involves the both the study of what cannot be done using only information about eigenvalues and eigenvectors, as well as what can be achieved by combining spectral analysis with classical combinatorial approaches, like computation of graph flows.

标题：光谱分析，光谱算法及其他 谱算法和谱分析形成了从机器学习到科学计算、从图形到数据挖掘、从协同过滤到VLSI设计等领域中一些最高效和最有效的技术的基础。 它们在组合优化中也扮演着重要的角色，它们被用于图划分和约束满足的算法中。 尽管光谱技术的明显效用和致力于他们的分析，我们的能力，严格的原因，他们仍然是非常有限的。 该项目致力于发展以算法为中心的光谱分析理论，该理论借鉴了当代数学的工具，并受到迄今为止尚未得到令人满意的理论解释的实验证据的启发。 该项目还从计算复杂性的角度讨论了谱方法的相对能力，包括研究仅使用特征值和特征向量的信息无法完成的工作，以及将谱分析与经典组合方法（如图流计算）相结合可以实现的工作。