A PAC learning approach to one-bit compressed sensing

M. Eren Ahsen, M. Vidyasagar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, the problem of one-bit compressed sensing (OBCS) is formulated as a problem in probably approximately correct (PAC) learning theory. In particular, we study the set of half-spaces generated by sparse vectors, and derive explicit upper and lower bounds for the Vapnik- Chervonenkis (VC-) dimension. The upper bound implies that it is possible to achieve OBCS where the number of samples grows linearly with the sparsity dimension and logarithmically with the vector dimension, leaving aside issues of computational complexity. The lower bound implies that, for some choices of probability measures, at least this many samples are required.

Original languageEnglish (US)
Title of host publicationACC 2015 - 2015 American Control Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4228-4230
Number of pages3
ISBN (Electronic)9781479986842
DOIs
StatePublished - Jul 28 2015
Externally publishedYes
Event2015 American Control Conference, ACC 2015 - Chicago, United States
Duration: Jul 1 2015Jul 3 2015

Publication series

NameProceedings of the American Control Conference
Volume2015-July
ISSN (Print)0743-1619

Other

Other2015 American Control Conference, ACC 2015
CountryUnited States
CityChicago
Period7/1/157/3/15

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A PAC learning approach to one-bit compressed sensing'. Together they form a unique fingerprint.

Cite this