1-bit compressive sensing: reformulation and RRSP-based sign recovery theory

DOI10.1007/S11425-016-5153-2zbMATH Open1349.90617arXiv1412.5514OpenAlexW2963319894MaRDI QIDQ341409FDOQ341409

Authors: Chunlei Xu, Yun-Bin Zhao 

Publication date: 16 November 2016

Published in: Science China. Mathematics (Search for Journal in Brave)

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 $el{l}_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.

Full work available at URL: https://arxiv.org/abs/1412.5514

Recommendations

• Stability of 1-bit compressed sensing in sparse data reconstruction
• One-bit compressive sensing of dictionary-sparse signals
• Noisy 1-bit compressive sensing: models and algorithms
• Bayesian signal reconstruction for 1-bit compressed sensing
• Statistical mechanics approach to 1-bit compressed sensing

zbMATH Keywords

\(\ell_0\)-minimization1-bit basis pursuit1-bit compressive sensinglinear programrestricted range space propertysparse signal recovery

Mathematics Subject Classification ID

Convex programming (90C25) Linear programming (90C05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Sampling theory in information and communication theory (94A20)

Cites Work

• Title not available (Why is that?)
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• 1-bit matrix completion
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Trust, But Verify: Fast and Accurate Signal Recovery From 1-Bit Compressive Measurements
• Decoding by Linear Programming
• Stable signal recovery from incomplete and inaccurate measurements
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• A mathematical introduction to compressive sensing
• On Sparse Representations in Arbitrary Redundant Bases
• Greed is Good: Algorithmic Results for Sparse Approximation
• Reweighted \(\ell_1\)-minimization for sparse solutions to underdetermined linear systems
• The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing
• On Polar Polytopes and the Recovery of Sparse Representations
• One-bit compressed sensing by linear programming
• Certifying the Restricted Isometry Property is Hard
• Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
• Title not available (Why is that?)
• One-bit compressed sensing with non-Gaussian measurements
• Theory of compressive sensing via \(\ell_1\)-minimization: a non-RIP analysis and extensions
• Regime Change: Bit-Depth Versus Measurement-Rate in Compressive Sensing
• Robust 1-bit Compressive Sensing Using Adaptive Outlier Pursuit
• RSP-Based Analysis for Sparsest and Least $\ell_1$-Norm Solutions to Underdetermined Linear Systems
• Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications
• A new computational method for the sparsest solutions to systems of linear equations
• Binary Compressed Imaging

Cited In (18)

• Nonuniqueness of solutions of a class of \(\ell_0\)-minimization problems
• Optimality analysis on partial \(l_1\)-minimization recovery
• One-bit compressed sensing by greedy algorithms
• Stability of 1-bit compressed sensing in sparse data reconstruction
• 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
• Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
• Weak stability of \(\ell_1\)-minimization methods in sparse data reconstruction

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)