Authors: D Drusvyatskiy S A Vavasis H Wolkowicz
Publish Date: 2014/08/07
Volume: 152, Issue: 1-2, Pages: 521-544
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 setRecall that the minimal face of a convex set Q at barx is the unique face of Q containing barx in its relative interior A similar characterization holds for minimal exposed faces any set of the form partial delta Qv for some vector vin mathrmriN Qbarx is the minimal exposed face of Q at barx To be selfcontained we provide an elementary proof We begin with the following lemmaMinimal exposed faces of convex cones Consider a closed convex cone Ksubset mathbfE and a point barx in K Then for any vector vin mathrmriN Kbarx the set F=partial delta Kv is a minimal exposed face of K at barxThe theorem above can easily be extended to convex sets by homogenizing see Corollary 54 It will be particularly useful for us to understand the exposed faces of the gauge function The proof of the following proposition is standard we provide details for the sake of completenessIf F is an exposed face of gamma Q with exposing vector vne 0 then Fcap mathrmbdQ is an exposed face of Q with exposing vector v Moreover F then has the representation F=mathrmclmathrmconeFcap mathrmbdQ
Keywords: