线性等式不等式约束下的零范数最小化问题

A note on-norm minimization under linear equality and inequality constraints

本文主要研究了约束条件是线性等式和不等式的零范数最小化问题.通过增加一个非负变量,使得线性等式不等式约束条件转化为新的线性等式约束条件,从而使原问题转化为压缩感知领域中一个特殊的部分稀疏问题.针对该问题,提出了精确恢复条,即块零空间性质(block NSP)及块限制等距性质(block RIP).进一步地证明block RIP常数只由原始的线性等式决定.最后证明随机高斯矩阵是以高概率满足block RIP.

In this article, we consider the problem of -norm minimization under linear equality and inequality constraints. We transform the primal problem into a special partial sparse problem in compressed sensing, in which those linear equality and inequality constraints are transformed to the new linear equality constraints by adding to a non-negative vector. We present and derive the exact recovery conditions： block null space property and block restricted isometry property. Moreover, we demon- strate that the block restricted isometry property constant is determined by original linear equality. Eventually, we analysis that a random Gaussian matrix satisfies the block RIP with high probability.