A direct formulation for sparse PCA using semidefinite programming

d'Aspremont, Alexandre; Ghaoui, Laurent El; Jordan, Michael I.; Lanckriet, Gert R. G.

A direct formulation for sparse PCA using semidefinite programming

Authors

d'Aspremont, Alexandre

Ghaoui, Laurent El

Jordan, Michael I.

Lanckriet, Gert R. G.

Description

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.
Final version, to appear in SIAM review