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

M. Eren Ahsen, M. Vidyasagar

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

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. As with earlier bounds, these bounds grow linearly with respect to with the sparsity dimension and logarithmically with the vector dimension,

Original languageEnglish (US)
Title of host publication54rd IEEE Conference on Decision and Control,CDC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages7377-7379
Number of pages3
ISBN (Electronic)9781479978861
DOIs
StatePublished - Feb 8 2015
Externally publishedYes
Event54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan
Duration: Dec 15 2015Dec 18 2015

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume54rd IEEE Conference on Decision and Control,CDC 2015
ISSN (Print)0743-1546

Other

Other54th IEEE Conference on Decision and Control, CDC 2015
CountryJapan
CityOsaka
Period12/15/1512/18/15

Keywords

  • Complexity theory
  • Compressed sensing
  • Measurement uncertainty
  • Presses
  • Statistical learning
  • Support vector machines
  • Yttrium

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'An approach to one-bit compressed sensing based on probably approximately correct learning theory'. Together they form a unique fingerprint.

Cite this