Extreme point inequalities and geometry of the rank sparsity ball

DOI10.1007/S10107-014-0795-8MaRDI QIDQ494341zbMATHOpenAlexFDO

Authors D. Drusvyatskiy, Stephen A. Vavasis, Henry Wolkowicz

Publication date 31 August 2015

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

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

zbMATH Keywords

ranknuclear normsparsityconvex analysiscompressed sensingexposed face

Mathematics Subject Classification ID

Convex programming (90C25) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the $l_1$ norm of its entries --- a common penalty function encouraging joint low rank and high sparsity. As a byproduct of this effort, we develop a calculus (or algebra) of faces for general convex functions, yielding a simple and unified approach for deriving inequalities balancing the various features of the optimization problem at hand, at the extreme points of the solution set.

Recommendations

• The convex geometry of linear inverse problems
• The non-convex geometry of low-rank matrix optimization
• Convexifying the set of matrices of bounded rank: applications to the quasiconvexification and convexification of the rank function
• Deforming \(\|.\|_1\) into \(\|.\|_{\infty}\) via polyhedral norms: a pedestrian approach
• Explicit Solutions to Optimization Problems on the Intersections of the Unit Ball of the $l_1 $ and $l_\infty $ Norms with a Hyperplane

Cites work

• scientific article; zbMATH DE number 3177945 (Why is no real title available?)
• scientific article; zbMATH DE number 3664045 (Why is no real title available?)
• scientific article; zbMATH DE number 1534289 (Why is no real title available?)
• scientific article; zbMATH DE number 3323651 (Why is no real title available?)
• A proximal point algorithm for sequential feature extraction applications
• Compressed sensing
• Convex Analysis
• Decoding by Linear Programming
• Do semidefinite relaxations solve sparse PCA up to the information limit?
• Exact matrix completion via convex optimization
• Faces of the unit ball of a unitarily invariant norm
• Finding approximately rank-one submatrices with the nuclear norm and \(\ell_1\)-norm
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Introduction to Smooth Manifolds
• Nonsmooth analysis of singular values. I: Theory
• Nuclear norm minimization for the planted clique and biclique problems
• On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
• Orthogonal invariance and identifiability
• Phase retrieval via matrix completion
• Problems of distance geometry and convex properties of quadratic maps
• Rejoinder: Latent variable graphical model selection via convex optimization
• Robust principal component analysis?
• Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
• Stable signal recovery from incomplete and inaccurate measurements

Cited in

(4)

• Max-norm optimization for robust matrix recovery
• Lattice-based patterned fabric inspection by using total variation with sparsity and low-rank representations
• A note on alternating projections for ill-posed semidefinite feasibility problems
• On representer theorems and convex regularization

Describes a project that uses

Uses Software

• PhaseLift

This page was built for publication: Extreme point inequalities and geometry of the rank sparsity ball

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