Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Direct Formulation for Sparse PCA Using Semidefinite Programming

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

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1330
June 2004

http://www.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1330.pdf

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. The method has complexity O( n^4 square root of log( n) / epsilon), where n is the size of the underlying covariance matrix, and epsilon is the desired absolute accuracy on the optimal value of the problem.


BibTeX citation:

@techreport{d'Aspremont:CSD-04-1330,
    Author = {d'Aspremont, Alexandre and El Ghaoui, Laurent and Jordan, Michael I. and Lanckriet, Gert R. G.},
    Title = {A Direct Formulation for Sparse PCA Using Semidefinite Programming},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2004/5534.html},
    Number = {UCB/CSD-04-1330},
    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. The method has complexity <i>O</i>(<i>n</i>^4 square root of log(<i>n</i>) / epsilon), where <i>n</i> is the size of the underlying covariance matrix, and epsilon is the desired absolute accuracy on the optimal value of the problem.}
}

EndNote citation:

%0 Report
%A d'Aspremont, Alexandre
%A El Ghaoui, Laurent
%A Jordan, Michael I.
%A Lanckriet, Gert R. G.
%T A Direct Formulation for Sparse PCA Using Semidefinite Programming
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1330
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2004/5534.html
%F d'Aspremont:CSD-04-1330