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

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-04-1330

, 2004

http://www2.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 <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.

---

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},
    Year= {2004},
    Month= {Jun},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5534.html
%F d'Aspremont:CSD-04-1330