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设计的领域中一些最有效的技术的基础。 它们在组合优化中也起着重要的作用，在组合优化中，它们在算法中用于图形分配和约束满意度。 尽管光谱技术明显具有实用性以及致力于分析的巨大努力，但我们严格推论它们的能力仍然非常有限。 该项目介绍了一种以算法为中心的光谱分析理论的发展，该理论利用了当代数学的工具，并受到实验证据的启发，到目前为止，它已经避免了令人满意的理论解释。 该项目还从计算复杂性的角度解决了光谱方法的相对功能。这涉及对仅使用有关特征值和特征向量的信息进行的研究的研究，以及通过将光谱分析与经典组合方法结合到图形流的计算流量来实现的方法。