Performance Bounds of Compressive Classification under Perturbation

Abstract Recently, compressive sensing based classification, which is called compressive classification, has drawn a lot of attention, since it works directly in the compressive domain with low complexity. However, existing literatures assume perfectly known measurement matrix during compressive classification, which is impossible in many practical situations. In this paper, we focus on studying the performance of classification based on the compressive measurements under the perturbation, where the perturbation models the uncertainty of the measurement matrix. The upper and the lower bounds on the probability of misclassification of the compressive classification are evaluated by utilizing the Kullback-Leibler and Chernoff distances. Our results indicate that the performance depends on the variance of the perturbation when the perturbation obeys Gaussian distribution with zero mean. Moreover, compared with the one without perturbation, the performance of the compressive classification can be improved when the perturbation in each hypothesis is different from each other. Motivated by these observations, we design an improved sparse representation classification (SRC) framework by incorporating the perturbation item into the SRC framework and propose several enhanced SRC schemes for performance improvement. The experiments on MNIST datasets validate that the proposed SRC schemes outperform the existing standard SRC scheme.