Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
From MaRDI portal
Publication:2989301
DOI10.1109/TIT.2012.2234823zbMATH Open1364.94130arXiv1104.3160OpenAlexW2112038498MaRDI QIDQ2989301FDOQ2989301
Authors: Laurent Jacques, Jason N. Laska, Richard G. Baraniuk, Petros T. Boufounos 
Publication date: 8 June 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: The Compressive Sensing (CS) framework aims to ease the burden on analog-to-digital converters (ADCs) by reducing the sampling rate required to acquire and stably recover sparse signals. Practical ADCs not only sample but also quantize each measurement to a finite number of bits; moreover, there is an inverse relationship between the achievable sampling rate and the bit depth. In this paper, we investigate an alternative CS approach that shifts the emphasis from the sampling rate to the number of bits per measurement. In particular, we explore the extreme case of 1-bit CS measurements, which capture just their sign. Our results come in two flavors. First, we consider ideal reconstruction from noiseless 1-bit measurements and provide a lower bound on the best achievable reconstruction error. We also demonstrate that i.i.d. random Gaussian matrices describe measurement mappings achieving, with overwhelming probability, nearly optimal error decay. Next, we consider reconstruction robustness to measurement errors and noise and introduce the Binary -Stable Embedding (BSE) property, which characterizes the robustness measurement process to sign changes. We show the same class of matrices that provide almost optimal noiseless performance also enable such a robust mapping. On the practical side, we introduce the Binary Iterative Hard Thresholding (BIHT) algorithm for signal reconstruction from 1-bit measurements that offers state-of-the-art performance.
Full work available at URL: https://arxiv.org/abs/1104.3160
Cited In (56)
- Distributed Decoding From Heterogeneous 1-Bit Compressive Measurements
- Fast Metric Embedding into the Hamming Cube
- Just least squares: binary compressive sampling with low generative intrinsic dimension
- One-bit gridless DOA estimation with multiple measurements exploiting accelerated proximal gradient algorithm
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- Covariance estimation under one-bit quantization
- Fast binary embeddings with Gaussian circulant matrices: improved bounds
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- One-bit compressed sensing with non-Gaussian measurements
- Joint image compression-encryption scheme using entropy coding and compressive sensing
- One-bit sensing, discrepancy and Stolarsky's principle
- Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
- Weighted \(\ell_1\)-minimization for sparse recovery under arbitrary prior information
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- Error bounds for consistent reconstruction: random polytopes and coverage processes
- Dimension reduction by random hyperplane tessellations
- Sparse classification: a scalable discrete optimization perspective
- Sparse recovery from inaccurate saturated measurements
- Binary vectors for fast distance and similarity estimation
- Generalized notions of sparsity and restricted isometry property. II: Applications
- Quantization and compressive sensing
- Sigma delta quantization with harmonic frames and partial Fourier ensembles
- On recovery guarantees for one-bit compressed sensing on manifolds
- Iteratively consistent one-bit phase retrieval
- A unified approach to uniform signal recovery from nonlinear observations
- Quantization of compressive samples with stable and robust recovery
- Title not available (Why is that?)
- A theoretical perspective on hyperdimensional computing
- Information theory and recovery algorithms for data fusion in Earth observation
- Compressive sensing based sampling and reconstruction for wireless sensor array network
- On the atomic decomposition of coorbit spaces with non-integrable kernel
- Phase retrieval by binary questions: which complementary subspace is closer?
- On the number of faces and radii of cells induced by Gaussian spherical tessellations
- Noisy 1-bit compressive sensing: models and algorithms
- Quantized compressed sensing: a survey
- 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
- NBIHT: An Efficient Algorithm for 1-Bit Compressed Sensing With Optimal Error Decay Rate
- Memoryless scalar quantization for random frames
- Quadratic Convergence of Smoothing Newton's Method for 0/1 Loss Optimization
- An approach to one-bit compressed sensing based on probably approximately correct learning theory
- Representation and coding of signal geometry
- Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
- A survey on compressive sensing: classical results and recent advancements
- Democracy in action: quantization, saturation, and compressive sensing
- One-bit compressed sensing by linear programming
- Time for dithering: fast and quantized random embeddings via the restricted isometry property
- Sigma Delta Quantization for Images
- Sparse recovery from saturated measurements
- Estimation in high dimensions: a geometric perspective
- High-dimensional estimation with geometric constraints
- Simple classification using binary data
- Classification scheme for binary data with extensions
- Bipolar measurement matrix using chaotic sequence
- AdaBoost and robust one-bit compressed sensing
- Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
- Endpoint results for Fourier integral operators on noncompact symmetric spaces
This page was built for publication: Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989301)
