Repository logo
 

Bounds on the Number of Measurements for Reliable Compressive Classification

Published version
Peer-reviewed

Change log

Authors

Reboredo, H 
Calderbank, R 
Rodrigues, MRD 

Abstract

This paper studies the classification of high-dimensional Gaussian signals from low-dimensional noisy, linear measurements. In particular, it provides upper bounds (sufficient conditions) on the number of measurements required to drive the probability of misclassification to zero in the low-noise regime, both for random measurements and designed ones. Such bounds reveal two important operational regimes that are a function of the characteristics of the source: 1) when the number of classes is less than or equal to the dimension of the space spanned by signals in each class, reliable classification is possible in the low-noise regime by using a one-vs-all measurement design; 2) when the dimension of the spaces spanned by signals in each class is lower than the number of classes, reliable classification is guaranteed in the low-noise regime by using a simple random measurement design. Simulation results both with synthetic and real data show that our analysis is sharp, in the sense that it is able to gauge the number of measurements required to drive the misclassification probability to zero in the low-noise regime.

Description

Keywords

compressed sensing, compressive classification, classification, dimensionality reduction, Gaussian mixture models, measurement design, phase transitions, random measurements

Journal Title

IEEE Transactions on Signal Processing

Conference Name

Journal ISSN

1053-587X
1941-0476

Volume Title

64

Publisher

IEEE
Sponsorship
European Commission (655282)
This work was supported by Royal Society International Exchanges Scheme IE120996. The work of H. Reboredo was supported by the Fundação para a Ciência e Tecnologia, Portugal, under Doctoral Grant SFRH/BD/81543/2011. ˆ The work of F. Renna was carried out in part when he was in the Department of Electronic and Electrical Engineering of University College London, and was supported by the European Union’s Horizon 2020 Research and Innovation Programme under the Marie Skłodowska-Curie Grant 655282. The work of R. Calderbank was supported in part by AFOSR under Award FA 9550-13-1-0076. The work of M. R. D. Rodrigues was supported by the EPSRC under Research Grant EP/K033166/1.