Bounds on the Number of Measurements for Reliable Compressive Classification

DOI10.1109/TSP.2016.2599496zbMATH Open1414.94508arXiv1607.02801OpenAlexW2470411918MaRDI QIDQ4621030FDOQ4621030

Authors: Hugo Reboredo, Francesco Renna, Robert Calderbank, M. R. D. Rodrigues 

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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: i) 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; ii) 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.

Full work available at URL: https://arxiv.org/abs/1607.02801

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (5)

• 2D compressed learning: support matrix machine with bilinear random projections
• The effect of intrinsic dimension on the Bayes-error of projected quadratic discriminant classification
• Tighter guarantees for the compressive multi-layer perceptron
• Structure from randomness in halfspace learning with the zero-one loss
• Compressive classification: where wireless communications meets machine learning

This page was built for publication: Bounds on the Number of Measurements for Reliable Compressive Classification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621030)