Sparse PCA: convex relaxations, algorithms and applications

DOI10.1007/978-1-4614-0769-0_31zbMATH Open1334.90120arXiv1011.3781OpenAlexW1599867596MaRDI QIDQ2802550FDOQ2802550

Authors: Youwei Zhang, Alexandre d'Aspremont, Laurent El Ghaoui 

Publication date: 26 April 2016

Published in: International Series in Operations Research & Management Science (Search for Journal in Brave)

Abstract: Given a sample covariance matrix, we examine the problem of maximizing the variance explained by a 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. Unfortunately, this problem is also combinatorially hard and we discuss convex relaxation techniques that efficiently produce good approximate solutions. We then describe several algorithms solving these relaxations as well as greedy algorithms that iteratively improve the solution quality. Finally, we illustrate sparse PCA in several applications, ranging from senate voting and finance to news data.

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

Recommendations

• Optimal solutions for sparse principal component analysis
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Generalized power method for sparse principal component analysis
• Clustering and feature selection using sparse principal component analysis
• An exact approach to sparse principal component analysis

zbMATH Keywords

sparse principal component analysisconvex relaxation techniques

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Applications of mathematical programming (90C90) Semidefinite programming (90C22)

Cites Work

• Matrix Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• Generalized power method for sparse principal component analysis
• Optimal solutions for sparse principal component analysis
• Title not available (Why is that?)
• Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Decoding by Linear Programming
• The varimax criterion for analytic rotation in factor analysis
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Sparse Approximate Solutions to Linear Systems
• Numerical methods for large eigenvalue problems
• Testing the nullspace property using semidefinite programming
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Smoothing technique and its applications in semidefinite optimization
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Low-rank approximations with sparse factors. I: Basic algorithms and error analysis

Cited In (30)

• Optimal solutions for sparse principal component analysis
• Truncated power method for sparse eigenvalue problems
• Understanding large text corpora via sparse machine learning
• [HDDA] sparse subspace constrained partial least squares
• Using \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCA
• Majorization-Minimization on the Stiefel Manifold With Application to Robust Sparse PCA
• An \(\ell_1\)-penalized adaptive normalized quasi-Newton algorithm for sparsity-aware generalized eigen-subspace tracking
• Title not available (Why is that?)
• Generalized power method for sparse principal component analysis
• Sparse PCA: optimal rates and adaptive estimation
• The sparse principal component analysis problem: optimality conditions and algorithms
• Sparse learning via Boolean relaxations
• A sparse decomposition of low rank symmetric positive semidefinite matrices
• Sparse Variable PCA Using Geodesic Steepest Descent
• A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
• Clustering and feature selection using sparse principal component analysis
• Recovering PCA and sparse PCA via hybrid-\((\ell_1,\ell_2)\) sparse sampling of data elements
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Projection algorithms for nonconvex minimization with application to sparse principal component analysis
• Principal component analysis with weighted sparsity constraint
• A guide for sparse PCA: model comparison and applications
• Convex approximations to sparse PCA via Lagrangian duality
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Rate-optimal posterior contraction for sparse PCA
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Title not available (Why is that?)
• Bayesian variable selection for globally sparse probabilistic PCA
• Solving sparse principal component analysis with global support
• Sparse PCA on fixed-rank matrices
• Sparsistency and agnostic inference in sparse PCA

This page was built for publication: Sparse PCA: convex relaxations, algorithms and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802550)