Optimization Online


Sparse principal component analysis and its l1-relaxation

Santanu S. Dey(santanu.dey***at***isye.gatech.edu)
Rahul Mazumder(rahulmaz***at***mit.edu)
Marco Molinaro(mmolinaro***at***inf.puc-rio.br)
Guanyi Wang(gwang93***at***gatech.edu)

Abstract: Principal component analysis (PCA) is one of the most widely used dimensionality reduction methods in scientific data analysis. In many applications, for additional interpretability, it is desirable for the factor loadings to be sparse, that is, we solve PCA with an additional cardinality (l0) constraint. The resulting optimization problem is called the sparse principal component analysis (SPCA). One popular approach to achieve sparsity is to replace the l0 constraint by an l1 constraint. In this paper, we prove that, independent of the data, the optimal objective function value of the problem with l0 constraint is within a constant factor of the the optimal objective function value of the problem with l1 constraint. To the best of our knowledge, this is the first formal relationship established between the l0 and the l1 constraint version of the problem.


Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Applications -- Science and Engineering (Data-Mining )


Download: [PDF]

Entry Submitted: 12/03/2017
Entry Accepted: 12/03/2017
Entry Last Modified: 12/03/2017

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 Optimization Society