Compressive K-SVD

Dictionary learning algorithms design a dictionary that is specifically tailored to enable sparse representation of a given set of training signals. In turn, the increased sparsity of the signals with respect to this dictionary enables significantly improved performance in a variety of state-of-the-art signal processing tasks, e.g. compressive sensing. However, while these algorithms typically assume that all training data is fully available, this may not be the case in practice. In fact, the high cost of acquiring each signal or the sheer amount of data to be acquired may motivate us to take a compressive sensing (CS) approach, taking only a few CS measurements of each signal. In this paper, we present a novel algorithm for learning a dictionary on a set of training signals using only compressive sensing measurements of them. Our proposed algorithm is a generalization of the well-known K-SVD algorithm and preserves its convergence properties. Experimental results on synthetically generated data verify that our proposed algorithm can recover the generating dictionary atoms from CS measurements alone (so long as enough measurements of enough training signals are available), even for the case of noisy measurements. Finally, we show that compressive K-SVD (CK-SVD) can also be used to aid in signal reconstruction and compressive classification on the CS measurements.