Optimization Online


Linear Program Relaxation of Sparse Nonnegative Recovery

Linxia Qin(lxqin.echo***at***163.com)
Naihua Xiu(nhxiu***at***bjtu.edu.cn)
Lingchen Kong(konglchen***at***126.com)
Yu Li(liyubjut***at***gmail.com)

Abstract: In this paper, we study linear program / $l_1$ relaxation of sparse nonnegative recovery (SNR) which is to find the sparsest solutions subjected to an underdetermined system of linear equations and nonnegative restriction. Firstly, we investigate the solution property of the SNR and show that any solution to the SNR must be one of the extreme points of the underlying feasible set. Secondly, we verify that the solution set of $l_1$ relaxation proposed is nonempty, bounded and could be stated as convex hull of some extreme points of the feasible set. Thirdly, by defining nonnegative restricted isometry constants, we give a nonnegative restricted isometry property which guarantees that the SNR and the $l_1$ relaxation share the common unique solution.

Keywords: sparse nonnegative recovery, extreme point, linear program, nonnegative RIP

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Applications -- OR and Management Sciences

Citation: Beijing Jiaotong University, No.3 Shang Yuan Cun, Hai Dian District Beijing, China. January 2012

Download: [PDF]

Entry Submitted: 02/18/2012
Entry Accepted: 02/18/2012
Entry Last Modified: 02/18/2012

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