A Direct Formulation for Sparse PCA Using Semidefinite Programming

By Alexandre d'Aspremont, Laurent El Ghaoui, Michael I. Jordan, Gert R. G. Lanckriet. SIAM Review, 2004

1,113 citations recorded by the source corpus.

We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming based relaxation for our problem.

Subfields: Computational Mechanics, Control and Systems Engineering, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/14e10498f4f12e18aaf4706969746b3cfb36132f

How researchers see this paper

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

In Computational Mechanics

In Control and Systems Engineering

In Numerical Analysis

Citations in the corpus

Generalized Low Rank Models (2014, background): “Many variants on this basic idea have been proposed, together with a wide variety of algorithms [33, 161, 128, 94, 155, 122, 152].”
MINIMAX SPARSE PRINCIPAL SUBSPACE ESTIMATION IN HIGH DIMENSIONS (2012, neutral): “BY VINCENT Q. VU1 AND JING LEI2”
Sparse canonical correlation analysis (2009, methodology): “While (4) is similar to Least Absolute Shrinkage and Selection Operator (LASSO) (Tibshirani 1994) (Basis Pursuit Denoising ( Chen et al. 1999 )), (4) also has similarity to nonnegative matrix factorization (Heiler and Schnor 2006), it is not a standard LASSO problem unless e is fixed.”
An Informative Feature Selection Method Based on Sparse PCA for VHR Scene Classification (2016, methodology): “As cited in [15] where they suppose that Σ is fixed, the maximum eigenvalue function λmax(.”
Random matrix theory in statistics: A review (2014, background): “…Zou et al. (2006) imposed l1-type sparsity constraints directly on the eigenvector estimates and proposed optimization procedures for obtaining them. d'Aspremont et al. (2007) suggested a semi-definite programming (SDP) problem as a relaxation to the l0-penalty for sparse population eigenvectors.”
The Indian Buffet Process: An Introduction and Review (2011, neutral): “In sparse latent feature models (e.g., sparse PCA; d’Aspremont et al., 2004; Jolliffe and Uddin, 2003; Zou et al., 2006) only a subset of features take on non-zero values for each object, and Z picks out these subsets.”
The spectral norm of random inner-product kernel matrices (2015, methodology): “Computationally-efficient procedures for estimating sparse principal components include diagonal thresholding [31, 32, 9], `1- and model-selection-penalization approaches [33, 62, 21, 49, 60, 12], iterative thresholding via the QR method [40], approximate message passing [22], and covariance thresho”
High-dimensional analysis of semidefinite relaxations for sparse principal components (2008, methodology): “Past work has focused on greedy or non-convex optimization procedures [10], [11], as well as various types of 1-regularization [14], [5].”
A feasible method for optimization with orthogonality constraints (2012, methodology): “A globally convergent monotone curvilinear search algorithm, whose step size is chosen according to the Armijo-Wolfe condition, is presented in subsection 3.1.”
Covariance regularization by thresholding (2009, neutral): “30 79 v1 [ m at h. ST ] 2 0 Ja n 20 09 The Annals of Statistics 2008, Vol. 36, No. 6, 2577–2604 DOI: 10.1214/08-AOS600 c© Institute of Mathematical Statistics, 2008”