A Direct Formulation for Sparse PCA Using Semidefinite Programming
TITLE: A Direct Formulation for Sparse PCA Using Semidefinite Programming.
AUTHORS: Alexandre d'Aspremont, Laurent El Ghaoui, Michael I. Jordan, Gert R. G. Lanckriet
ABSTRACT: We examine the problem of approximating, in the Frobeniusnorm sense, a positive, semidefinite symmetric matrix by a rankone 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. We also discuss Nesterov's smooth minimization technique applied to the SDP arising in the direct sparse PCA method.
STATUS: SIAM Review, 49(3), pp. 434448, July 2007.
ArXiv PREPRINT: cs.CE/0406021
SOFTWARE: The DSPCA code is available here.
PAPER: Direct Formulation for Sparse PCA Using Semidefinite Programming in pdf
