An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory
Mehmet Eren Ahsen, Mathukumalli Vidyasagar; 20(11):1−23, 2019.
Abstract
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 \Rn generated by k-sparse vectors is bounded below by k(⌊lg(n/k)⌋+1) and above by ⌊2klg(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(klgn) measurements, given only the signs of the measurement vector. This result holds for \textit{all} probability measures on \Rn. The theory is also applicable to the case of noisy labels, where the signs of the measurements are flipped with some unknown probability.
© JMLR 2019. (edit, beta) |