Extreme point inequalities and geometry of the rank sparsity ball

• 成果类型: Article
• 署名作者: Drusvyatskiy, D.; Vavasis, S. A.; Wolkowicz, H.
• 署名单位: University of Washington; University of Washington Seattle; University of Waterloo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0795-8
• 发表日期: 2015
• 页码: 521-544
• 关键词: nuclear norm

摘要

We investigate geometric features of the unit ball corresponding to the sum of the nuclear norm of a matrix and the 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.