Full regularization path for sparse principal component analysis
Lists
Only you see this
Abstract
Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a particular linear combination of the input variables while constraining the number of nonzero coefficients in this combination. This is known as sparse principal component analysis and has a wide array of applications in machine learning and engineering. We formulate a new semidefinite relaxation to this problem and derive a greedy algorithm that computes a full set of good solutions for all numbers of non zero coefficients, with complexity O(n3), where n is the number of variables. We then use the same relaxation to derive sufficient conditions for global optimality of a solution, which can be tested in O(n3). We show on toy examples and biological data that our algorithm does provide globally optimal solutions in many cases.
BibTeX
@inproceedings{daspremont2007full,
author = {Alexandre d'Aspremont and Francis R. Bach and Laurent El Ghaoui},
title = {{Full regularization path for sparse principal component analysis}},
booktitle = {International Conference on Machine Learning},
year = {2007},
doi = {10.1145/1273496.1273519},
}Loading related content...