Classification from compressive representations of data

Compressive sensing proposes simple compression of sparse data at the expense of difficult data reconstruction. We focus here on the opportunities in terms of information recovery within the compressed data space, thus avoiding the expensive data reconstruction step. Specifically, we study here how the clustering ability of a dataset is affected by random projections. The proposed result has the advantage to give statistical insights for low dimensions, where traditional results are to no avail. Experiments show that it is possible to achieve high compression rate while preserving clustering abilities, at a low computational cost.