1-Bit compressive sensing: Reformulation and RRSP-based sign recovery theory
1-Bit compressive sensing: Reformulation and RRSP-based sign recovery theory
复制标题
DOI：
10.1007/s11425-016-5153-2
复制
发表时间：
2014-12
期刊：
影响因子：
--
通讯作者：
Yun-Bin Zhao;Chunlei Xu
中科院分区：
文献类型：
--
作者：
Yun-Bin Zhao;Chunlei Xu
最近，在稀疏信号恢复领域中已经研究了1比特压缩感知（1比特CS）。由于在1比特CS中稀疏信号的幅度信息是不可用的，因此通常可以用解码方法精确地恢复信号的支持或符号。我们首先表明，一个必要的假设（在文献中被忽视），应作出一些现有的理论和1位CS的讨论。在没有这样的假设的情况下，通过一些现有解码算法找到的解决方案可能与1比特测量不一致。这促使我们追求一个新的方向，发展统一和非统一的恢复理论1位CS与新的解码方法，总是产生一个解决方案与1位测量一致。我们专注于一个极端的情况下，1位CS，其中的测量捕获的传感矩阵和信号的产品的符号。我们表明，1位CS模型可以等价地重新表述为一个具有线性约束的最小化问题。这种重新制定自然会导致一个新的线性程序为基础的解码方法，称为1位基追求，这是显着不同的现有配方。结果表明，1位基追踪的解的唯一性条件产生了转置传感矩阵的所谓的限制范围空间性质（RRSP）。这个概念提供了一个基础，通过1位测量稀疏信号的符号恢复条件。我们证明了，如果一个稀疏信号的符号可以从1位测量与1位基追踪准确恢复，那么传感矩阵必须承认一定的RRSP，如果传感矩阵承认一个稍微增强的RRSP，那么ak-稀疏信号的符号可以准确恢复与1位基追踪。
Recently, the 1-bit compressive sensing (1-bit CS) has been studied in the field of sparse signal recovery. Since the amplitude information of sparse signals in 1-bit CS is not available, it is often the support or the sign of a signal that can be exactly recovered with a decoding method. We first show that a necessary assumption (that has been overlooked in the literature) should be made for some existing theories and discussions for 1-bit CS. Without such an assumption, the found solution by some existing decoding algorithms might be inconsistent with 1-bit measurements. This motivates us to pursue a new direction to develop uniform and nonuniform recovery theories for 1-bit CS with a new decoding method which always generates a solution consistent with 1-bit measurements. We focus on an extreme case of 1-bit CS, in which the measurements capture only the sign of the product of a sensing matrix and a signal. We show that the 1-bit CS model can be reformulated equivalently as anℓ0-minimization problem with linear constraints. This reformulation naturally leads to a new linear-program-based decoding method, referred to as the 1-bit basis pursuit, which is remarkably different from existing formulations. It turns out that the uniqueness condition for the solution of the 1-bit basis pursuit yields the so-called restricted range space property (RRSP) of the transposed sensing matrix. This concept provides a basis to develop sign recovery conditions for sparse signals through 1-bit measurements. We prove that if the sign of a sparse signal can be exactly recovered from 1-bit measurements with 1-bit basis pursuit, then the sensing matrix must admit a certain RRSP, and that if the sensing matrix admits a slightly enhanced RRSP, then the sign of ak-sparse signal can be exactly recovered with 1-bit basis pursuit.