Extreme point inequalities and geometry of the rank sparsity ball

DOI10.1007/S10107-014-0795-8zbMATH Open1327.90200arXiv1401.4774OpenAlexW1991937133MaRDI QIDQ494341FDOQ494341

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)

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.

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

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

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)

Cites Work

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

Cited In (4)

• On Representer Theorems and Convex Regularization
• 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

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)