A PAC learning approach to one-bit compressed sensing

M. Eren Ahsen; M. Vidyasagar

doi:10.1109/ACC.2015.7171993

A PAC learning approach to one-bit compressed sensing

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	ACC 2015 - 2015 American Control Conference
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	4228-4230
Number of pages	3
ISBN (Electronic)	9781479986842
DOIs	https://doi.org/10.1109/ACC.2015.7171993
State	Published - Jul 28 2015
Externally published	Yes
Event	2015 American Control Conference, ACC 2015 - Chicago, United States Duration: Jul 1 2015 → Jul 3 2015

Publication series

Name	Proceedings of the American Control Conference
Volume	2015-July
ISSN (Print)	0743-1619

Other

Other	2015 American Control Conference, ACC 2015
Country/Territory	United States
City	Chicago
Period	7/1/15 → 7/3/15

ASJC Scopus subject areas

Electrical and Electronic Engineering

Online availability

10.1109/ACC.2015.7171993

Library availability

Discover UIUC Full Text

Cite this

A PAC learning approach to one-bit compressed sensing. / Eren Ahsen, M.; Vidyasagar, M.
ACC 2015 - 2015 American Control Conference. Institute of Electrical and Electronics Engineers Inc., 2015. p. 4228-4230 7171993 (Proceedings of the American Control Conference; Vol. 2015-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Eren Ahsen, M & Vidyasagar, M 2015, A PAC learning approach to one-bit compressed sensing. in ACC 2015 - 2015 American Control Conference., 7171993, Proceedings of the American Control Conference, vol. 2015-July, Institute of Electrical and Electronics Engineers Inc., pp. 4228-4230, 2015 American Control Conference, ACC 2015, Chicago, United States, 7/1/15. https://doi.org/10.1109/ACC.2015.7171993

@inproceedings{9a7c8a67564e45e5aca09dda44981d3b,

title = "A PAC learning approach to one-bit compressed sensing",

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.",

author = "{Eren Ahsen}, M. and M. Vidyasagar",

note = "Publisher Copyright: {\textcopyright} 2015 American Automatic Control Council.; 2015 American Control Conference, ACC 2015 ; Conference date: 01-07-2015 Through 03-07-2015",

year = "2015",

month = jul,

day = "28",

doi = "10.1109/ACC.2015.7171993",

language = "English (US)",

series = "Proceedings of the American Control Conference",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "4228--4230",

booktitle = "ACC 2015 - 2015 American Control Conference",

address = "United States",

}

TY - GEN

T1 - A PAC learning approach to one-bit compressed sensing

AU - Eren Ahsen, M.

AU - Vidyasagar, M.

PY - 2015/7/28

Y1 - 2015/7/28

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84940903308&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84940903308&partnerID=8YFLogxK

U2 - 10.1109/ACC.2015.7171993

DO - 10.1109/ACC.2015.7171993

M3 - Conference contribution

AN - SCOPUS:84940903308

T3 - Proceedings of the American Control Conference

SP - 4228

EP - 4230

BT - ACC 2015 - 2015 American Control Conference

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2015 American Control Conference, ACC 2015

Y2 - 1 July 2015 through 3 July 2015

ER -

A PAC learning approach to one-bit compressed sensing

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this