# An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory

arXiv: https://arxiv.org/abs/1710.07973 · HTML: https://mlsanity.com/paper/1710.07973/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Oct 2017.

## Built on by (most cited first, 4 of 4)

- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributions](https://mlsanity.com/paper/2211.16333/) (2022)
- [Improved Generalization Bound and Learning of Sparsity Patterns for Data-Driven Low-Rank Approximation](https://mlsanity.com/paper/2209.08281/) (2022)
- [Just Least Squares: Binary Compressive Sampling with Low Generative Intrinsic Dimension](https://mlsanity.com/paper/2111.14486/) (2021)

## Abstract (arXiv)

In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces in ℝn generated by k-sparse vectors is bounded below by k lg (n/k) and above by 2k lg (n/k), plus some round-off terms. By coupling this estimate with well-established results in PAC learning theory, we show that a consistent algorithm can recover a k-sparse vector with O(k lg (n/k)) measurements, given only the signs of the measurement vector. This result holds for textitall probability measures on ℝn. It is further shown that random sign-flipping errors result only in an increase in the constant in the O(k lg (n/k)) estimate. Because constructing a consistent algorithm is not straight-forward, we present a heuristic based on the ℓ1-norm support vector machine, and illustrate that its computational performance is superior to a currently popular method.