1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
From MaRDI portal
(Redirected from Publication:341409)
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 -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 -sparse signal can be exactly recovered with 1-bit basis pursuit.
Recommendations
Cites work
- scientific article; zbMATH DE number 3121284 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- 1-bit matrix completion
- A mathematical introduction to compressive sensing
- A new computational method for the sparsest solutions to systems of linear equations
- Binary Compressed Imaging
- Certifying the Restricted Isometry Property is Hard
- Compressed sensing
- Compressed sensing and best \(k\)-term approximation
- Decoding by Linear Programming
- Enhancing sparsity by reweighted \(\ell _{1}\) minimization
- Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Greed is Good: Algorithmic Results for Sparse Approximation
- On Polar Polytopes and the Recovery of Sparse Representations
- On Sparse Representations in Arbitrary Redundant Bases
- One-bit compressed sensing by linear programming
- One-bit compressed sensing with non-Gaussian measurements
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems
- Regime Change: Bit-Depth Versus Measurement-Rate in Compressive Sensing
- Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
- Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
- Robust 1-bit Compressive Sensing Using Adaptive Outlier Pursuit
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Stable signal recovery from incomplete and inaccurate measurements
- The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
- Theory of compressive sensing via _1-minimization: a non-RIP analysis and extensions
- Trust, But Verify: Fast and Accurate Signal Recovery From 1-Bit Compressive Measurements
Cited in
(18)- Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
- Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction
- Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
- Optimality analysis on partial l₁-minimization recovery
- Stability of 1-bit compressed sensing in sparse data reconstruction
- One-bit compressed sensing by greedy algorithms
- Statistical mechanics approach to 1-bit compressed sensing
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- Stability analysis of a class of sparse optimization problems
- Bayesian signal reconstruction for 1-bit compressed sensing
- One-bit compressive sensing of dictionary-sparse signals
- Required Number of Iterations for Sparse Signal Recovery via Orthogonal Least Squares
- New low-rank optimization model and algorithms for spectral compressed sensing
- Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained \(\ell_1\) minimization
- On fast decoding of high-dimensional signals from one-bit measurements
- Noisy 1-bit compressive sensing: models and algorithms
- Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
- Sparse recovery from saturated measurements
This page was built for publication: 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q341409)
