  Performing signal processing tasks on compressive measurements of data has
received great attention in recent years. In this paper, we extend previous
work on compressive dictionary learning by showing that more general random
projections may be used, including sparse ones. More precisely, we examine
compressive K-means clustering as a special case of compressive dictionary
learning and give theoretical guarantees for its performance for a very general
class of random projections. We then propose a memory and computation efficient
dictionary learning algorithm, specifically designed for analyzing large
volumes of high-dimensional data, which learns the dictionary from very sparse
random projections. Experimental results demonstrate that our approach allows
for reduction of computational complexity and memory/data access, with
controllable loss in accuracy.
