Sparse Principal Component Analysis via the Sparsest Element in a Subspace

通过子空间中最稀疏元素的稀疏主成分分析

• 批准号: 1418971
• 负责人: Paul Hand
• 金额: $ 13.38万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2014-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1418971&HistoricalAwards=false
• 关键词: Sparse; Principal; Component; Analysis; via

Sparse principal component analysis (PCA) is a technique that allows biologists and other scientists to interpret experimental data in terms of very few variables. For example, it can help identify which among thousands of genes are important in distinguishing different types of cancer. In order for scientists and engineers to select the best algorithm for finding sparse principal components, it is important to have a theoretical understanding of the performance of many algorithms under a realistic data model. Most existing theoretical understanding focuses on the simple case where there is a single component that happens to be sparse. The proposed work will introduce a new model in which there are multiple components, of which one is sparse. For a special case of this more realistic model, the proposed work attempts to understand if there are any conditions under which sophisticated convex programs are provably better than very simple algorithms. Either outcome would be informative in helping researchers decide between the many algorithms for sparse PCA. In this project, sparse PCA will be studied from the perspective of finding the sparsest element in a subspace. This perspective is motivated by a multispike data model, which the PI calls a sparse-dense model. Under this model, the infinite data limit of sparse PCA becomes the sparsest element problem, which is nontrivial. The objective of this research is to understand the computational-statistical tradeoff in finding the sparsest element in a subspace under the sparse-dense model. The PI would like to determine if there is a scaling gap between the information theoretic limit and the best performance by a computationally efficient algorithm. Ultimately, we would like to understand when sophisticated convex methods are provably better than simple thresholding methods. This objective will be explored by semidefinite relaxations, polynomial optimization, and reductions to the planted clique problem.

稀疏主成分分析（PCA）是一种使生物学家和其他科学家可以用很少的变量来解释实验数据的技术。例如，它可以帮助确定成千上万基因在区分不同类型癌症的基因中很重要。为了使科学家和工程师选择找到稀疏主组件的最佳算法，重要的是要在现实的数据模型下对许多算法的性能有理论上的理解。大多数现有的理论理解都集中在一个简单的情况下，其中一个组件恰好是稀疏的。拟议的工作将引入一个新模型，其中有多个组件，其中一个组成部分很少。对于这种更现实的模型的特殊情况，拟议的工作试图了解是否有任何条件，在任何条件下，复杂的凸面程序比非常简单的算法要好得多。在帮助研究人员之间决定稀疏PCA的许多算法之间，这两种结果都是有益的。 在这个项目中，将从查找子空间中最稀少元素的角度研究稀疏PCA。该观点是由多功能数据模型的动机，PI称之为稀疏密集的模型。在此模型下，稀疏PCA的无限数据限制成为最稀少的元素问题，这是非平凡的。这项研究的目的是了解计算统计的权衡，以在稀疏密集模型下找到子空间中最稀少的要素。 PI希望确定信息理论限制与计算有效算法之间的最佳性能之间是否存在缩放差距。最终，我们想了解何时复杂的凸方法比简单的阈值方法更好。该目标将通过半决赛松弛，多项式优化以及对种植集团问题的减少来探索。