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

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 R-n generated by k-sparse vectors is bounded below by k(left perpendicular lg(n/k) right perpendicular + 1) and above by left perpendicular 2k lg(en) right perpendicular. 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) measurements, given only the signs of the measurement vector. This result holds for all probability measures on R-n. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.