  


On the Quality of a Semidefinite Programming Bound for Sparse Principal Component Analysis
Laurent El Ghaoui (elghaouieecs.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 BenTal (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 (Semidefinite Programming ) Citation: unpublished Download: [PDF] Entry Submitted: 03/10/2006 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  