Applications of gauge duality in robust principal component analysis and semidefinite programming

DOI10.1007/S11425-016-0312-1zbMATH Open1380.65106arXiv1601.06893OpenAlexW2262822087MaRDI QIDQ341322FDOQ341322

Authors: Shiqian Ma, Junfeng Yang 

Publication date: 16 November 2016

Published in: Science China. Mathematics (Search for Journal in Brave)

Abstract: Gauge duality theory was originated by Freund [Math. Programming, 38(1):47-67, 1987] and was recently further investigated by Friedlander, Mac{^e}do and Pong [SIAM J. Optm., 24(4):1999-2022, 2014]. When solving some matrix optimization problems via gauge dual, one is usually able to avoid full matrix decompositions such as singular value and/or eigenvalue decompositions. In such an approach, a gauge dual problem is solved in the first stage, and then an optimal solution to the primal problem can be recovered from the dual optimal solution obtained in the first stage. Recently, this theory has been applied to a class of emph{semidefinite programming} (SDP) problems with promising numerical results [Friedlander and Mac{^e}do, SIAM J. Sci. Comp., to appear, 2016]. In this paper, we establish some theoretical results on applying the gauge duality theory to robust emph{principal component analysis} (PCA) and general SDP. For each problem, we present its gauge dual problem, characterize the optimality conditions for the primal-dual gauge pair, and validate a way to recover a primal optimal solution from a dual one. These results are extensions of [Friedlander and Mac{^e}do, SIAM J. Sci. Comp., to appear, 2016] from nuclear norm regularization to robust PCA and from a special class of SDP which requires the coefficient matrix in the linear objective to be positive definite to SDP problems without this restriction. Our results provide further understanding in the potential advantages and disadvantages of the gauge duality theory.

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

Recommendations

• Two proposals for robust PCA using semidefinite programming
• Dual gauge programs, with applications to quadratic programming and the minimum-norm problem
• Low-rank spectral optimization via gauge duality
• Exploiting sparsity in the matrix-dilation approach to robust semidefinite programming
• A Dual Approach to Semidefinite Least-Squares Problems
• Robust least square semidefinite programming with applications
• Strongly convex programming for exact matrix completion and robust principal component analysis
• Robust PCA and pairs of projections in a Hilbert space

zbMATH Keywords

singular value decompositionsemidefinite programmingrobust principal component analysisantipolar setgauge dualitygauge optimizationpolar function

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Semidefinite programming (90C22) Random operators and equations (aspects of stochastic analysis) (60H25)

Cites Work

• An Inverse Free Preconditioned Krylov Subspace Method for Symmetric Generalized Eigenvalue Problems
• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Robust principal component analysis?
• Title not available (Why is that?)
• Convex Analysis
• Rank-Sparsity Incoherence for Matrix Decomposition
• Proximal level bundle methods for convex nondifferentiable optimization, saddle-point problems and variational inequalities
• Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization
• Non-Euclidean restricted memory level method for large-scale convex optimization
• New variants of bundle methods
• Alternating direction augmented Lagrangian methods for semidefinite programming
• Title not available (Why is that?)
• Low-rank spectral optimization via gauge duality
• Dual gauge programs, with applications to quadratic programming and the minimum-norm problem
• Gauge optimization and duality

Cited In (5)

• Foundations of gauge and perspective duality
• Dual gauge programs, with applications to quadratic programming and the minimum-norm problem
• Duality of optimization problems with gauge functions
• Classification rules for two exponential populations with a common location using censored samples
• Gauge optimization and duality

Uses Software

• EIGIFP
• LMaFit
• ADMM_QAP
• PhaseLift

This page was built for publication: Applications of gauge duality in robust principal component analysis and semidefinite programming

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