Ahsen, M Eren and Vidyasagar, Mathukumalli
(2019)
An approach to onebit compressed sensing based on probably approximately correct learning theory.
Journal of Machine Learning Research, 20.
ISSN 15324435
Abstract
In this paper, the problem of onebit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning. It is shown that the VapnikChervonenkis (VC) dimension of the set of halfspaces in Rn generated by ksparse vectors is bounded below by k(blg(n=k)c + 1) and above by b2k lg(en)c. By coupling this estimate with wellestablished results in PAC learning theory, we show that a consistent algorithm can recover a ksparse vector with O(k lg n) measurements, given only the signs of the measurement vector. This result holds for 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.
[error in script]
Actions (login required)

View Item 