Sparse Principal Component Analysis via the Sparsest Element in a Subspace

稀疏主成分分析（PCA）是一种允许生物学家和其他科学家根据很少的变量来解释实验数据的技术。例如，它可以帮助识别在数千个基因中哪些对区分不同类型的癌症是重要的。为了让科学家和工程师选择寻找稀疏主成分的最佳算法，从理论上了解许多算法在实际数据模型下的性能是很重要的。大多数现有的理论理解都集中在一个简单的情况下，即存在一个碰巧是稀疏的单个组件。提出的工作将引入一个新的模型，其中有多个组件，其中一个是稀疏的。对于这种更现实的模型的一个特殊情况，提出的工作试图理解是否存在任何条件下，复杂的凸规划被证明比非常简单的算法更好。这两种结果都有助于研究人员在稀疏PCA的多种算法之间做出选择。本课题将从寻找子空间中最稀疏元素的角度来研究稀疏主成分分析。这种观点是由多尖峰数据模型驱动的，PI称之为稀疏密集模型。在该模型下，稀疏主成分分析的无限数据极限问题成为最稀疏元素问题，具有非平凡性。本研究的目的是了解在稀疏-密集模型下寻找子空间中最稀疏元素的计算-统计权衡。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.