Alternating direction method of multipliers for sparse principal component analysis

DOI10.1007/S40305-013-0016-9zbMATH Open1336.62160arXiv1111.6703OpenAlexW2090214813MaRDI QIDQ457552FDOQ457552

Authors: Shiqian Ma 

Publication date: 29 September 2014

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Abstract: We consider a convex relaxation of sparse principal component analysis proposed by d'Aspremont et al. in (d'Aspremont et al. SIAM Rev 49:434-448, 2007). This convex relaxation is a nonsmooth semidefinite programming problem in which the $el{l}_1$ norm of the desired matrix is imposed in either the objective function or the constraint to improve the sparsity of the resulting matrix. The sparse principal component is obtained by a rank-one decomposition of the resulting sparse matrix. We propose an alternating direction method based on a variable-splitting technique and an augmented Lagrangian framework for solving this nonsmooth semidefinite programming problem. In contrast to the first-order method proposed in (d'Aspremont et al. SIAM Rev 49:434-448, 2007) that solves approximately the dual problem of the original semidefinite programming problem, our method deals with the primal problem directly and solves it exactly, which guarantees that the resulting matrix is a sparse matrix. Global convergence result is established for the proposed method. Numerical results on both synthetic problems and the real applications from classification of text data and senate voting data are reported to demonstrate the efficacy of our method.

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

Recommendations

• scientific article; zbMATH DE number 6142618
• An alternating direction method with increasing penalty for stable principal component pursuit
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• An augmented Lagrangian approach for sparse principal component analysis
• Convex approximations to sparse PCA via Lagrangian duality

zbMATH Keywords

semidefinite programmingsparse PCAalternating direction methodaugmented Lagrangian methoddeflationprojection onto the simplex

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Numerical mathematical programming methods (65K05) Convex programming (90C25) Semidefinite programming (90C22)

Cites Work

• A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
• Probing the Pareto frontier for basis pursuit solutions
• Title not available (Why is that?)
• Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Splitting Algorithms for the Sum of Two Nonlinear Operators
• On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
• Smooth minimization of non-smooth functions
• Generalized power method for sparse principal component analysis
• Title not available (Why is that?)
• Fast alternating linearization methods for minimizing the sum of two convex functions
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Regularization methods for semidefinite programming
• An augmented Lagrangian approach for sparse principal component analysis
• The Split Bregman Method for L1-Regularized Problems
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• Signal Recovery by Proximal Forward-Backward Splitting
• Alternating direction method for covariance selection models
• Alternating Direction Algorithms for $\ell_1$-Problems in Compressive Sensing
• A new inexact alternating directions method for monotone variational inequalities
• Semidefinite optimization
• Title not available (Why is that?)
• Alternating direction augmented Lagrangian methods for semidefinite programming
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Fast multiple-splitting algorithms for convex optimization
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• An algorithm for a singly constrained class of quadratic programs subject upper and lower bounds
• Title not available (Why is that?)
• An O(n) algorithm for quadratic knapsack problems
• Title not available (Why is that?)
• Projection and deflation method for partial pole assignment in linear state feedback

Cited In (20)

• Title not available (Why is that?)
• [HDDA] sparse subspace constrained partial least squares
• Alternating direction method of multipliers for real and complex polynomial optimization models
• Accelerated Alternating Projections for Robust Principal Component Analysis
• An implementable splitting algorithm for the \(\ell_1\)-norm regularized split feasibility problem
• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Acceleration of the alternating least squares algorithm for principal components analysis
• Title not available (Why is that?)
• Alternating proximal gradient method for convex minimization
• Alternating direction method of multipliers for separable convex optimization of real functions in complex variables
• A coordinate descent MM algorithm for fast computation of sparse logistic PCA
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Title not available (Why is that?)
• Using ℓ1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA
• A homotopy alternating direction method of multipliers for linearly constrained separable convex optimization
• Convex approximations to sparse PCA via Lagrangian duality
• ADMM Algorithmic Regularization Paths for Sparse Statistical Machine Learning
• Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
• Solving sparse principal component analysis with global support
• An extragradient-based alternating direction method for convex minimization

Uses Software

• SPGL1
• RecPF

This page was built for publication: Alternating direction method of multipliers for sparse principal component analysis

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