A direct formulation for sparse PCA using semidefinite programming
Alexandre d’Aspremont, Laurent El Ghaoui, Michael I. Jordan et al. · arXiv (Cornell University) · 2004
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.
Cited by 116 works. doi:10.48550/arxiv.cs/0406021 Open-access PDF
Authors
References
- Convex Optimization
- Regression Shrinkage and Selection Via the Lasso
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Semidefinite Programming
- Introductory Lectures on Convex Optimization
- Two Case Studies in the Application of Principal Component Analysis
- Nineteen Dubious Ways to Compute the Exponential of a Matrix
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- A rank minimization heuristic with application to minimum order system approximation