Information-theoretically Optimal Sparse PCA

Andrea Montanari, Yash Deshpande

Publication date: 10 February 2014

Abstract: Sparse Principal Component Analysis (PCA) is a dimensionality reduction technique wherein one seeks a low-rank representation of a data matrix with additional sparsity constraints on the obtained representation. We consider two probabilistic formulations of sparse PCA: a spiked Wigner and spiked Wishart (or spiked covariance) model. We analyze an Approximate Message Passing (AMP) algorithm to estimate the underlying signal and show, in the high dimensional limit, that the AMP estimates are information-theoretically optimal. As an immediate corollary, our results demonstrate that the posterior expectation of the underlying signal, which is often intractable to compute, can be obtained using a polynomial-time scheme. Our results also effectively provide a single-letter characterization of the sparse PCA problem.

Has companion code repository: https://github.com/krzakala/LowRAMP

This page was built for publication: Information-theoretically Optimal Sparse PCA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6248917)