High-dimensional analysis of semidefinite relaxations for sparse principal components

By Arash Ali Amini, Martin J. Wainwright. 2008 IEEE International Symposium on Information Theory, 2008

327 citations recorded by the source corpus.

In problem of sparse principal components analysis (SPCA), the goal is to use n i.i.d. samples to estimate the leading eigenvector(s) of a p times p covariance matrix, which are known a priori to be sparse, say with at most k non-zero entries. This paper studies SPCA in the high-dimensional regime, where the model dimension p, sparsity index k, and sample size n all tend to infinity simultaneously. We first analyze a simple and computationally inexpensive diagonal cut-off method, and establish a threshold of the order thetasdiag = n/[k2 log(p-k)] separating success from failure. We then analyze a more complex semidefinite programming (SDP) relaxation due to dpsilaAspremont et al., and prove that it succeeds once the sample size is of the order thetassdp = n/[k log(p - k)]. Our results thus highlight an interesting tradeoff between statistical and computational efficiency in high-dimensional estimation problems.

Subfields: Artificial Intelligence, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/bab4ebd7c361f0704ae38661b121d244707f3040

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Asymptotics and Concentration Bounds for Bilinear Forms of Spectral Projectors of Sample Covariance (2014, unknown): “For instance, in [1], a spiked covariance model was considered, where Σ = s(2)1θ1 ⊗ θ1 + ( Ik 0 0 Γp−k ) , the first k entries of θ1 ∈ Sp−1 are equal to ± 1 k for some k ≥ 1 and Γp−k is symmetric positive semi-definite with ‖Γp−k‖∞ ≤ 1.”
Principal Differences Analysis: Interpretable Characterization of Differences between Distributions (2015, methodology): “Finally, we emphasize that PDA (and SPARDA) not only computationally resembles (sparse) PCA, but the latter is actually a special case of the former in the Gaussian, paired-sample-differences setting.”
Principal Component Analysis of High-Frequency Data (2016, background): “Anderson (1958) and Anderson (1963) developed the asymptotic theory of eigenvalues and eigenvectors under the assumption of multivariate normality. Even in this case, the asymptotic distribution becomes rather complicated when repeated eigenvalues are present. The literature has relaxed these assump”
On Consistency and Sparsity for Principal Components Analysis in High Dimensions (2009, unknown): “The study of consistency properties for these methods and comparison with those of this article is a natural topic for further research, with significant progress recently reported in Amini and Wainwright (2009).”
The spectral norm of random inner-product kernel matrices (2015, background): “In this setting, non-polynomial-time algorithms can detect the spike and recover the support even when v has sparsity near-linear in n [1, 5, 13], but it is conjectured that polynomial-time methods require the higher sparsity levels ‖v‖0 .”
MINIMAX SPARSE PRINCIPAL SUBSPACE ESTIMATION IN HIGH DIMENSIONS (2012, background): “Theoretical developments on sparsity and PCA include consistency [Johnstone and Lu (2009), Shen, Shen and Marron (2013)], variable selection properties [Amini and Wainwright (2009)], rates of convergence and minimaxity [Vu and Lei (2012a)], but have primarily been limited to results about estimation”
Estimation of high-dimensional low-rank matrices (2009, background): “(2008), Amini and Wainwright (2009), Cai, Zhang and Zhou (2010) and the references cited therein]. Most of attention was devoted to estimation of a large covariance matrix or its inverse. In these papers, sparsity is characterized by the number of nonzero entries of a matrix. Candès and Recht (2009)”
Truncated power method for sparse eigenvalue problems (2011, methodology): “The only exception is the analysis of the convex relaxation method (d’Aspremont et al., 2007) by Amini & Wainwright (2009) under the high dimensional spiked covariance model (Johnstone, 2001).”
Large Covariance Estimation by Thresholding Principal Orthogonal Complements (2011, unknown): “More literature on sparse PCA is found in Johnstone and Lu (2009), Amini and Wainwright (2009), Zhang and El Ghaoui (2011), Birnbaum et al. (2012), among others.”
ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions (2013, methodology): “On one hand, in terms of computationally efficient methods, under the spike covariance Gaussian model, Amini and Wainwright (2009) showed the consistency in parameter estimation and model selection for sparse PCA computed via the semidefinite program proposed by d’Aspremont et al. (2007). Ma (2013) ”
Fast global convergence rates of gradient methods for high-dimensional statistical recovery (2010, unknown): “, [3, 11, 28, 36, 37, 39]).”