A direct formulation for sparse PCA using semidefinite programming

A d'Aspremont (aspremonprinceton.edu)
L. El Ghaoui (elghaouieecs.berkeley.edu)
M. I. Jordan (jordancs.berkeley.edu)
G. R. G. Lanckriet (gerteecs.berkeley.edu)

Abstract: 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. We also discuss Nesterov's smooth minimization technique applied to the SDP arising in the direct sparse PCA method.

Keywords: PCA, semidefinite programming, sparsity

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 2: Applications -- Science and Engineering (Statistics )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation: ArXiv PREPRINT: cs.CE/0406021

Download: [PDF]

Entry Submitted: 07/07/2004
Entry Accepted: 07/07/2004
Entry Last Modified: 07/07/2004

Modify/Update this entry