Ahsen, M Eren and Vidyasagar, Mathukumalli
(2015)
An approach to onebit compressed sensing based on probably approximately correct learning theory.
In: 54th IEEE Conference on Decision and Control, CDC 2015, 1518 December,2015, KitaKuOsaka,Japan.
Full text not available from this repository.
(
Request a copy)
Abstract
This paper builds upon earlier work of the authors in formulating the onebit 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 VapnikChervonenkis (VC) dimension of the set of halfspaces 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 VCdimension of halfspaces 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.
[error in script]
Actions (login required)

View Item 