On the Solution Uniqueness Characterization in the L1 Norm and Polyhedral Gauge Recovery

详细信息    查看全文

• 作者：Jean Charles Gilbert
• 关键词：Basis pursuit ; Convex polyhedral function ; Gauge recovery ; L1 minimization ; Minkowski function ; Optimality conditions ; Sharp minimum ; Solution existence and uniqueness
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：172
• 期：1
• 页码：70-101
• 全文大小：
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operation Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878
• 卷排序：172

文摘

This paper first proposes another proof of the necessary and sufficient conditions of solution uniqueness in 1-norm minimization given recently by H. Zhang, W. Yin, and L. Cheng. The analysis avoids the need of the surjectivity assumption made by these authors and should be mainly appealing by its short length (it can therefore be proposed to students exercising in convex optimization). In the second part of the paper, the previous existence and uniqueness characterization is extended to the recovery problem where the L1 norm is substituted by a polyhedral gauge. In addition to present interest for a number of practical problems, this extension clarifies the geometrical aspect of the previous uniqueness characterization. Numerical techniques are proposed to compute a solution to the polyhedral gauge recovery problem in polynomial time and to check its possible uniqueness by a simple linear algebra test.