Alternating maximization: unifying framework for 8 sparse PCA formulations and efficient parallel codes

DOI10.1007/S11081-020-09562-3zbMATH Open1484.62009arXiv1212.4137OpenAlexW3089317050MaRDI QIDQ2129204FDOQ2129204

Peter Richtárik, M. Takáč, Majid Jahani, Selin Damla Ahipaşaoğlu

Publication date: 22 April 2022

Published in: Optimization and Engineering (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/1212.4137

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

zbMATH Keywords

unsupervised learningsparse PCAbig data analyticsalternating maximizationgpower

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Factor analysis and principal components; correspondence analysis (62H25) Learning and adaptive systems in artificial intelligence (68T05) Parallel numerical computation (65Y05) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Cites Work

• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
• Certifiably optimal sparse principal component analysis
• Generalized power method for sparse principal component analysis
• Robust principal component analysis?
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• An augmented Lagrangian approach for sparse principal component analysis
• Sparse principal component analysis via regularized low rank matrix approximation
• Projected gradient approach to the numerical solution of the SCoTLASS
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Improve robustness of sparse PCA by \(L_{1}\)-norm maximization
• Sparse principal component analysis by choice of norm
• The sparse principal component analysis problem: optimality conditions and algorithms
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• Sparsistency and agnostic inference in sparse PCA
• Minimax sparse principal subspace estimation in high dimensions
• From simple structure to sparse components: a review
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
• NP-hardness and inapproximability of sparse PCA

Cited In (8)

• From simple structure to sparse components: a review
• Certifiably optimal sparse principal component analysis
• Modeling and optimization: theory and applications (MOPTA) 2019 -- selected works
• Three \(l_1\) based nonconvex methods in constructing sparse mean reverting portfolios
• Sparsifying the least-squares approach to PCA: comparison of lasso and cardinality constraint
• PCA Sparsified
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Alternating direction method of multipliers for a class of nonconvex bilinear optimization: convergence analysis and applications

Uses Software

• PMA
• Optimal-SPCA

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)