One-bit compressed sensing by linear programming
From MaRDI portal
Abstract: We give the first computationally tractable and almost optimal solution to the problem of one-bit compressed sensing, showing how to accurately recover an s-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linear measurements of x. The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors x. Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.
Recommendations
Cites work
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- scientific article; zbMATH DE number 3385043 (Why is no real title available?)
- Democracy in action: quantization, saturation, and compressive sensing
- Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
- Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
- Simultaneous analysis of Lasso and Dantzig selector
- Stability and instance optimality for Gaussian measurements in compressed sensing
- Stable signal recovery from incomplete and inaccurate measurements
- The Dantzig selector: statistical estimation when \(p\) is much larger than \(n\). (With discussions and rejoinder).
- Threshold Group Testing
- Trust, But Verify: Fast and Accurate Signal Recovery From 1-Bit Compressive Measurements
Cited in
(79)- Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
- Outlier robust and sparse estimation of linear regression coefficients
- Endpoint results for Fourier integral operators on noncompact symmetric spaces
- Quantization-aware phase retrieval
- Covariance estimation under one-bit quantization
- Stability of 1-bit compressed sensing in sparse data reconstruction
- One-bit compressed sensing by greedy algorithms
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- A reliable iteration algorithm for one-bit compressive sensing on the unit sphere
- Compressive phase retrieval: Optimal sample complexity with deep generative priors
- UNIFORM-IN-SUBMODEL BOUNDS FOR LINEAR REGRESSION IN A MODEL-FREE FRAMEWORK
- One-bit compressed sensing with non-Gaussian measurements
- Statistical mechanics approach to 1-bit compressed sensing
- Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
- One-bit sensing, discrepancy and Stolarsky's principle
- Error bounds for consistent reconstruction: random polytopes and coverage processes
- On the asymptotic variance of the debiased Lasso
- The stochastic geometry of unconstrained one-bit data compression
- Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- Advances in Neural Networks – ISNN 2005
- Robust one-bit compressed sensing with partial circulant matrices
- Dimension reduction by random hyperplane tessellations
- Sparse classification: a scalable discrete optimization perspective
- Sparse recovery from inaccurate saturated measurements
- Just least squares: binary compressive sampling with low generative intrinsic dimension
- scientific article; zbMATH DE number 7306893 (Why is no real title available?)
- Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
- Quantization and compressive sensing
- Sigma delta quantization with harmonic frames and partial Fourier ensembles
- Fast and RIP-optimal transforms
- Hypothesis testing for high-dimensional sparse binary regression
- On recovery guarantees for one-bit compressed sensing on manifolds
- One-bit compressive sensing of dictionary-sparse signals
- Estimation of block sparsity in compressive sensing
- Attribute-efficient learning of halfspaces with malicious noise: near-optimal label complexity and noise tolerance
- Iteratively consistent one-bit phase retrieval
- _1-penalized multinomial regression: estimation, inference, and prediction, with an application to risk factor identification for different dementia subtypes
- Quantized compressed sensing for random circulant matrices
- A unified framework for linear dimensionality reduction in L1
- A unified approach to uniform signal recovery from nonlinear observations
- Quantization of compressive samples with stable and robust recovery
- Performance bounds of the intensity-based estimators for noisy phase retrieval
- Dynamic pricing in high-dimensions
- On the \(\ell^\infty\)-norms of the singular vectors of arbitrary powers of a difference matrix with applications to sigma-delta quantization
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- Thin-shell concentration for zero cells of stationary Poisson mosaics
- On fast decoding of high-dimensional signals from one-bit measurements
- Analysis of hard-thresholding for distributed compressed sensing with one-bit measurements
- Generalized high-dimensional trace regression via nuclear norm regularization
- On some aspects of recovery of sparse signals in high dimensions from nonlinear measurements using compressed sensing
- On the atomic decomposition of coorbit spaces with non-integrable kernel
- Phase retrieval by binary questions: which complementary subspace is closer?
- Noisy 1-bit compressive sensing: models and algorithms
- 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
- Quantized compressed sensing: a survey
- Robust 1-bit compressed sensing via hinge loss minimization
- Memoryless scalar quantization for random frames
- An approach to one-bit compressed sensing based on probably approximately correct learning theory
- Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
- Representation and coding of signal geometry
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- One-bit compressed sensing with partial Gaussian circulant matrices
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- Sparse probit linear mixed model
- Computing one-bit compressive sensing via zero-norm regularized DC loss model and its surrogate
- The landscape of empirical risk for nonconvex losses
- Robust decoding from binary measurements with cardinality constraint least squares
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Sparse recovery from saturated measurements
- Estimation in high dimensions: a geometric perspective
- High-dimensional estimation with geometric constraints
- Flavors of compressive sensing
- Classification scheme for binary data with extensions
- Simple classification using binary data
- Sparse learning for large-scale and high-dimensional data: a randomized convex-concave optimization approach
- AdaBoost and robust one-bit compressed sensing
- A simple homotopy proximal mapping algorithm for compressive sensing
This page was built for publication: One-bit compressed sensing by linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2841676)
