Approximation bounds for sparse principal component analysis

DOI10.1007/S10107-014-0751-7zbMATH Open1303.90079arXiv1205.0121OpenAlexW2153671921MaRDI QIDQ484129FDOQ484129

Authors: Yong-Cai Geng, Sumit K. Garg 

Publication date: 18 December 2014

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Abstract: We produce approximation bounds on a semidefinite programming relaxation for sparse principal component analysis. These bounds control approximation ratios for tractable statistics in hypothesis testing problems where data points are sampled from Gaussian models with a single sparse leading component.

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

Recommendations

• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Optimal detection of sparse principal components in high dimension
• Statistical and computational trade-offs in estimation of sparse principal components

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Combinatorial optimization (90C27) Semidefinite programming (90C22)

Cites Work

• The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
• Smooth minimization of non-smooth functions
• Generalized power method for sparse principal component analysis
• Title not available (Why is that?)
• A Direct Formulation for Sparse PCA Using Semidefinite Programming
• Optimal detection of sparse principal components in high dimension
• Title not available (Why is that?)
• Non-Euclidean restricted memory level method for large-scale convex optimization
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Mean field models for spin glasses. Volume I: Basic examples.
• Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
• Information, Physics, and Computation
• On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty
• Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Low-rank optimization on the cone of positive semidefinite matrices
• Smoothed analysis of algorithms

Cited In (15)

• Sparse principal component analysis via fractional function regularity
• Title not available (Why is that?)
• Distance geometry and data science
• Bounds on the quality of the PCA bounding boxes
• Several approximation algorithms for sparse best rank-1 approximation to higher-order tensors
• Alternating direction method of multipliers for penalized zero-variance discriminant analysis
• Using ℓ1-Relaxation and Integer Programming to Obtain Dual Bounds for Sparse PCA
• The Sparse Principal Component of a Constant-Rank Matrix
• Sparse Principal Component Analysis via Axis-Aligned Random Projections
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Title not available (Why is that?)
• Practical approximation algorithms for \(\ell_1\)-regularized sparse rank-1 approximation to higher-order tensors
• Solving sparse principal component analysis with global support
• Sparse PCA on fixed-rank matrices
• Sparsistency and agnostic inference in sparse PCA

Uses Software

• Outward rotations

This page was built for publication: Approximation bounds for sparse principal component analysis

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