Projects per year
Abstract
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. In this paper, 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 a k-sparse signal can be exactly recovered with 1-bit basis pursuit.
Original language | English |
---|---|
Pages (from-to) | 2049-2074 |
Number of pages | 25 |
Journal | Science China Mathematics |
Volume | 59 |
Issue number | 10 |
Early online date | 18 Jul 2016 |
DOIs | |
Publication status | Published - Oct 2016 |
Keywords
- 1-bit compressive sensing
- , restricted range space property
- 1-bit basis pursuit
- linear program
- `0-minimization
- sparse signal recovery
Fingerprint
Dive into the research topics of '1-bit compressive sensing: reformulation and RRSP-based sign recovery theory'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Foundation and Reweighted Algorithms for Sparsest Points of Convex Sets with Application to Data Processing
Zhao, Y.-B. (Principal Investigator)
Engineering & Physical Science Research Council
18/04/13 → 31/05/15
Project: Research Councils