Subsampling Algorithms for Semidefinite Programming

DOI10.1214/10-SSY018zbMath1291.90169arXiv0803.1990MaRDI QIDQ5168846

Alexandre d'Aspremont

Publication date: 21 July 2014

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

zbMATH Keywords

stochastic optimizationsemidefinite programmingsubsampling

Mathematics Subject Classification ID

Semidefinite programming (90C22) Stochastic programming (90C15)

Related Items

Sublinear time algorithms for approximate semidefinite programming

Uses Software

• LAPACK
• GradSamp

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual subgradient methods for convex problems
• The convergence behavior of Ritz values in the presence of close eigenvalues
• On the distribution of the largest eigenvalue in principal components analysis
• Tracy-Widom limit for the largest eigenvalue of a large class of complex sample covariance matrices
• Exact matrix completion via convex optimization
• Matrix Algorithms
• The Fastest Mixing Markov Process on a Graph and a Connection to a Maximum Variance Unfolding Problem
• Fast computation of low-rank matrix approximations
• Sampling from large matrices
• The design and implementation of the MRRR algorithm
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• First-Order Methods for Sparse Covariance Selection
• Robust Stochastic Approximation Approach to Stochastic Programming
• Spectral Algorithms
• LAPACK Users' Guide
• On Estimating the Largest Eigenvalue with the Lanczos Algorithm
• Acceleration of Stochastic Approximation by Averaging
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• ARPACK Users' Guide
• Orthogonal Eigenvectors and Relative Gaps
• Patterns in eigenvalues: the 70th Josiah Willard Gibbs lecture
• A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Approximating Subdifferentials by Random Sampling of Gradients
• A Direct Formulation for Sparse PCA Using Semidefinite Programming