Optimization Online


Extreme point inequalities and geometry of the rank sparsity ball

D. Drusvyatskiy(ddrusvya***at***uwaterloo.ca)
S.A. Vavasis(vavasis***at***math.uwaterloo.ca)
H. Wolkowicz(hwolkowicz***at***uwaterloo.ca)

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.

Keywords: Nuclear norm, compressed sensing, sparsity, rank, exposed face, convex analysis

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: 23 pages, 2 figures

Download: [PDF]

Entry Submitted: 01/19/2014
Entry Accepted: 01/19/2014
Entry Last Modified: 01/19/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society