Computational and Mathematical Methods in Medicine
Volume 2012 (2012), Article ID 646045, 8 pages
Research Article

Linear Program Relaxation of Sparse Nonnegative Recovery in Compressive Sensing Microarrays

Department of Applied Mathematics, Beijing Jiaotong University, Beijing 100044, China

Received 23 May 2012; Accepted 30 July 2012

Academic Editor: Huafeng Liu

Copyright © 2012 Linxia Qin et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Compressive sensing microarrays (CSM) are DNA-based sensors that operate using group testing and compressive sensing principles. Mathematically, one can cast the CSM as sparse nonnegative recovery (SNR) which is to find the sparsest solutions subjected to an underdetermined system of linear equations and nonnegative restriction. In this paper, we discuss the relaxation of the SNR. By defining nonnegative restricted isometry/orthogonality constants, we give a nonnegative restricted property condition which guarantees that the SNR and the relaxation share the common unique solution. Besides, we show that any solution to the SNR must be one of the extreme points of the underlying feasible set.