@inproceedings{21748cee060d4912a000e7913317dab9,
title = "An approach to one-bit compressed sensing based on probably approximately correct learning theory",
abstract = "This paper builds upon earlier work of the authors in formulating the one-bit compressed sensing (OBCS) problem as a problem in probably approximately correct (PAC) learning theory. It is shown that the solution to the OBCS problem consists of two parts. The first part is to determine the statistical complexity of OBCS by determining the Vapnik-Chervonenkis (VC-) dimension of the set of half-spaces generated by sparse vectors. The second is to determine the algorithmic complexity of the problem by developing a consistent algorithm. In this paper, we generalize the earlier results of the authors by deriving both upper and lower bounds on the VC-dimension of half-spaces generated by sparse vectors, even when the separating hyperplane need not pass through the origin.",
keywords = "Complexity theory, Compressed sensing, Measurement uncertainty, Presses, Statistical learning, Support vector machines, Yttrium",
author = "Ahsen, {M. Eren} and M. Vidyasagar",
note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 54th IEEE Conference on Decision and Control, CDC 2015 ; Conference date: 15-12-2015 Through 18-12-2015",
year = "2015",
month = feb,
day = "8",
doi = "10.1109/CDC.2015.7403384",
language = "English",
series = "Proceedings of the IEEE Conference on Decision and Control",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "7377--7379",
booktitle = "54rd IEEE Conference on Decision and Control,CDC 2015",
address = "United States",
}