Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
From MaRDI portal
Publication:2129204
Computational methods for problems pertaining to statistics (62-08) Factor analysis and principal components; correspondence analysis (62H25) Parallel numerical computation (65Y05) Learning and adaptive systems in artificial intelligence (68T05) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)
Abstract: Given a multivariate data set, sparse principal component analysis (SPCA) aims to extract several linear combinations of the variables that together explain the variance in the data as much as possible, while controlling the number of nonzero loadings in these combinations. In this paper we consider 8 different optimization formulations for computing a single sparse loading vector; these are obtained by combining the following factors: we employ two norms for measuring variance (L2, L1) and two sparsity-inducing norms (L0, L1), which are used in two different ways (constraint, penalty). Three of our formulations, notably the one with L0 constraint and L1 variance, have not been considered in the literature. We give a unifying reformulation which we propose to solve via a natural alternating maximization (AM) method. We show the the AM method is nontrivially equivalent to GPower (Journ'{e}e et al; JMLR 11:517--553, 2010) for all our formulations. Besides this, we provide 24 efficient parallel SPCA implementations: 3 codes (multi-core, GPU and cluster) for each of the 8 problems. Parallelism in the methods is aimed at i) speeding up computations (our GPU code can be 100 times faster than an efficient serial code written in C++), ii) obtaining solutions explaining more variance and iii) dealing with big data problems (our cluster code is able to solve a 357 GB problem in about a minute).
Recommendations
- Generalized power method for sparse principal component analysis
- An exact approach to sparse principal component analysis
- Projection sparse principal component analysis: an efficient least squares method
- An augmented Lagrangian approach for sparse principal component analysis
- Sparse principal component analysis by choice of norm
Cites work
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
- An augmented Lagrangian approach for sparse principal component analysis
- Certifiably optimal sparse principal component analysis
- Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint
- Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
- From simple structure to sparse components: a review
- Generalized power method for sparse principal component analysis
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- scientific article; zbMATH DE number 6438182 (Why is no real title available?)
- Improve robustness of sparse PCA by \(L_{1}\)-norm maximization
- Improved bounds on restricted isometry constants for Gaussian matrices
- Minimax sparse principal subspace estimation in high dimensions
- NP-hardness and inapproximability of sparse PCA
- Optimal solutions for sparse principal component analysis
- Projected gradient approach to the numerical solution of the SCoTLASS
- Robust principal component analysis?
- Sparse principal component analysis by choice of norm
- Sparse principal component analysis via regularized low rank matrix approximation
- Sparsistency and agnostic inference in sparse PCA
- The sparse principal component analysis problem: optimality conditions and algorithms
Cited in
(9)- Three \(l_1\) based nonconvex methods in constructing sparse mean reverting portfolios
- Modeling and optimization: theory and applications (MOPTA) 2019 -- selected works
- From simple structure to sparse components: a review
- Certifiably optimal sparse principal component analysis
- Parallel regressions for variable selection using GPU
- Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint
- PCA Sparsified
- Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications
- Alternating direction method of multipliers for penalized zero-variance discriminant analysis
This page was built for publication: Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2129204)
