Optimization Online


On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis

Laurent El Ghaoui (elghaoui***at***eecs.berkeley.edu)

Abstract: We examine the problem of approximating a positive, semidefinite matrix $\Sigma$ by a dyad $xx^T$, with a penalty on the cardinality of the vector $x$. This problem arises in sparse principal component analysis, where a decomposition of $\Sigma$ involving sparse factors is sought. We express this hard, combinatorial problem as a maximum eigenvalue problem, in which we seek to maximize, over a box, the largest eigenvalue of a symmetric matrix that is linear in the variables. This representation allows to use the techniques of robust optimization, to derive a bound based on semidefinite programming. The quality of the bound is investigated using a technique inspired by Nemirovski and Ben-Tal (2002).

Keywords: Sparse Principal Component Analysis, Semidefinite Programming, Quality of Relaxation, Unsupervised Machine Learning

Category 1: Robust Optimization

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

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

Citation: unpublished

Download: [PDF]

Entry Submitted: 03/10/2006
Entry Accepted: 03/10/2006
Entry Last Modified: 03/10/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society