Optimization Online


Sparse PCA on fixed-rank matrices

Alberto Del Pia (delpia***at***wisc.edu)

Abstract: We consider two different versions of multi-component Sparse PCA: Sparse PCA with global support, and Sparse PCA with disjoint supports. In both problems we assume that the rank of the data matrix is a fixed value, and in the disjoint case we further assume that the number of principal components is fixed. We give the first algorithms that can solve these problems to global optimality in a number of operations that is polynomial in the number of input variables. The algorithms depend on methods form discrete geometry and combinatorial optimization.

Keywords: principal component analysis; sparsity; polynomial-time algorithm; global optimum; constant-rank quadratic function

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: submitted manuscript on May 23, 2019

Download: [PDF]

Entry Submitted: 07/25/2019
Entry Accepted: 07/25/2019
Entry Last Modified: 07/26/2019

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