Title :
A PAC learning approach to one-bit compressed sensing
Author :
Eren Ahsen, M. ; Vidyasagar, M.
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.
Keywords :
compressed sensing; computational complexity; learning (artificial intelligence); vectors; OBCS; PAC learning approach; VC; Vapnik- Chervonenkis dimension; computational complexity; half-spaces; one-bit compressed sensing; probably approximately correct learning theory; sparse vectors; vector dimension; Approximation algorithms; Compressed sensing; Measurement uncertainty; Presses; Sensors; Statistical learning; Upper bound;
Conference_Titel :
American Control Conference (ACC), 2015
Conference_Location :
Chicago, IL
Print_ISBN :
978-1-4799-8685-9
DOI :
10.1109/ACC.2015.7171993
