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ⁿ generated by k-sparse vectors is bounded below by k([lg(n/k)]+1) and above by [2k lg(en)]. 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ⁿ. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.