Sparse Principal Component Analysis via the Sparsest Element in a Subspace

稀疏主成分分析（PCA）是一种允许生物学家和其他科学家用很少的变量来解释实验数据的技术。例如，它可以帮助确定在数千个基因中，哪些基因对区分不同类型的癌症很重要。为了让科学家和工程师选择最好的算法来寻找稀疏主成分，重要的是要在理论上理解许多算法在现实数据模型下的性能。大多数现有的理论理解集中在简单的情况下，有一个单一的组件，碰巧是稀疏的。拟议的工作将引入一个新的模型，其中有多个组件，其中一个是稀疏的。对于这种更现实的模型的一个特殊情况下，所提出的工作试图了解是否有任何条件下，复杂的凸规划可证明优于非常简单的算法。任何一种结果都将有助于研究人员在稀疏PCA的许多算法之间做出决定。 在这个项目中，稀疏PCA将从寻找子空间中的稀疏元素的角度进行研究。这种观点是由多峰数据模型激发的，PI称之为稀疏-密集模型。在该模型下，稀疏PCA的无限数据极限成为稀疏元问题，这是非平凡的。本研究的目的是了解在稀疏-稠密模型下，在子空间中寻找稀疏元素的计算-统计权衡。PI希望确定信息理论极限与计算高效算法的最佳性能之间是否存在缩放差距。最后，我们想了解复杂的凸方法何时被证明比简单的阈值方法更好。这一目标将探讨半定松弛，多项式优化，并减少种植集团问题。

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.