An approach to one-bit compressed sensing based on probably approximately correct learning theory

Ahsen, M Eren and Vidyasagar, Mathukumalli (2019) An approach to one-bit compressed sensing based on probably approximately correct learning theory. Journal of Machine Learning Research, 20. ISSN 1532-4435

[img]
Preview
Text
17-504.pdf

Download (369kB) | Preview

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 VapnikChervonenkis (VC-) dimension of the set of half-spaces in Rn generated by k-sparse vectors is bounded below by k(blg(n=k)c + 1) and above by b2k lg(en)c. 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 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]
IITH Creators:
IITH CreatorsORCiD
Vidyasagar, MathukumalliUNSPECIFIED
Item Type: Article
Uncontrolled Keywords: Indexed in Scopus and WoS.
Subjects: Electrical Engineering
Divisions: Department of Electrical Engineering
Depositing User: Library Staff
Date Deposited: 29 Oct 2019 04:59
Last Modified: 29 Oct 2019 04:59
URI: http://raiith.iith.ac.in/id/eprint/6873
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 6873 Statistics for this ePrint Item