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
- Democracy in action: quantization, saturation, and compressive sensing
- Dequantizing Compressed Sensing: When Oversampling and Non-Gaussian Constraints Combine
- scientific article; zbMATH DE number 194093 (Why is no real title available?)
- scientific article; zbMATH DE number 3385043 (Why is no real title available?)
- 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
(82)- Sparse recovery from inaccurate saturated measurements
- Sigma delta quantization with harmonic frames and partial Fourier ensembles
- Sparse probit linear mixed model
- The landscape of empirical risk for nonconvex losses
- On recovery guarantees for one-bit compressed sensing on manifolds
- Non-Gaussian hyperplane tessellations and robust one-bit compressed sensing
- On the \(\ell^\infty\)-norms of the singular vectors of arbitrary powers of a difference matrix with applications to sigma-delta quantization
- Memoryless scalar quantization for random frames
- Sparse classification: a scalable discrete optimization perspective
- AdaBoost and robust one-bit compressed sensing
- Adaptive iterative hard thresholding for least absolute deviation problems with sparsity constraints
- Covariance estimation under one-bit quantization
- Phase retrieval by binary questions: which complementary subspace is closer?
- Stability of 1-bit compressed sensing in sparse data reconstruction
- Dimension reduction by random hyperplane tessellations
- The stochastic geometry of unconstrained one-bit data compression
- Thin-shell concentration for zero cells of stationary Poisson mosaics
- Generalized high-dimensional trace regression via nuclear norm regularization
- On the asymptotic variance of the debiased Lasso
- Quantized compressed sensing for random circulant matrices
- Hypothesis testing for high-dimensional sparse binary regression
- Quantization of compressive samples with stable and robust recovery
- A simple homotopy proximal mapping algorithm for compressive sensing
- One-bit compressed sensing with non-Gaussian measurements
- Fast and RIP-optimal transforms
- Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements
- Estimation in high dimensions: a geometric perspective
- Sparse learning for large-scale and high-dimensional data: a randomized convex-concave optimization approach
- Error bounds for consistent reconstruction: random polytopes and coverage processes
- A unified framework for linear dimensionality reduction in L1
- Robust Decoding from 1-Bit Compressive Sampling with Ordinary and Regularized Least Squares
- Quantized compressed sensing: a survey
- Classification scheme for binary data with extensions
- Statistical mechanics approach to 1-bit compressed sensing
- 1-bit compressive sensing: reformulation and RRSP-based sign recovery theory
- Quantization and compressive sensing
- Sparse recovery from saturated measurements
- Representation and coding of signal geometry
- High-dimensional estimation with geometric constraints
- Flavors of compressive sensing
- Simple classification using binary data
- Dynamic pricing in high-dimensions
- An approach to one-bit compressed sensing based on probably approximately correct learning theory
- One-bit compressed sensing via \(\ell_p\) \((0<p<1)\)-minimization method
- Robust 1-bit compressed sensing via hinge loss minimization
- Analysis of hard-thresholding for distributed compressed sensing with one-bit measurements
- One-bit compressed sensing with partial Gaussian circulant matrices
- Estimation of block sparsity in compressive sensing
- Real-valued embeddings and sketches for fast distance and similarity estimation
- Quantization-aware phase retrieval
- On fast decoding of high-dimensional signals from one-bit measurements
- Two-stage approach to multivariate linear regression with sparsely mismatched data
- One-bit compressive sensing of dictionary-sparse signals
- Endpoint results for Fourier integral operators on noncompact symmetric spaces
- On the atomic decomposition of coorbit spaces with non-integrable kernel
- Characterization of \(\ell_1\) minimizer in one-bit compressed sensing
- One-bit compressed sensing by greedy algorithms
- One-bit sensing, discrepancy and Stolarsky's principle
- Advances in Neural Networks – ISNN 2005
- Iteratively consistent one-bit phase retrieval
- Robust sensing of low-rank matrices with non-orthogonal sparse decomposition
- A unified approach to uniform signal recovery from nonlinear observations
- Robust one-bit compressed sensing with partial circulant matrices
- Compressive phase retrieval: Optimal sample complexity with deep generative priors
- UNIFORM-IN-SUBMODEL BOUNDS FOR LINEAR REGRESSION IN A MODEL-FREE FRAMEWORK
- Just least squares: binary compressive sampling with low generative intrinsic dimension
- Performance bounds of the intensity-based estimators for noisy phase retrieval
- A reliable iteration algorithm for one-bit compressive sensing on the unit sphere
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- On some aspects of recovery of sparse signals in high dimensions from nonlinear measurements using compressed sensing
- Robust decoding from binary measurements with cardinality constraint least squares
- Outlier robust and sparse estimation of linear regression coefficients
- Computing one-bit compressive sensing via zero-norm regularized DC loss model and its surrogate
- Binary iterative hard thresholding converges with optimal number of measurements for 1-bit compressed sensing
- Attribute-efficient learning of halfspaces with malicious noise: near-optimal label complexity and noise tolerance
- _1-penalized multinomial regression: estimation, inference, and prediction, with an application to risk factor identification for different dementia subtypes
- Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness
- A resolution of the Gaussian hyperplane tessellation conjecture on the sphere
- Robust instance optimal phase-only compressed sensing
- Estimation of sparse linear regression coefficients under L-subexponential covariates
- High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
- Noisy 1-bit compressive sensing: models and algorithms
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)
