Sparse Principal Component Analysis via the Sparsest Element in a Subspace

稀疏主成分分析(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.