Ways to Sparse Representation: A Comparative Study

Many algorithms have been proposed to achieve sparse representation over redundant dictionaries or transforms. A comprehensive understanding of these algorithms is needed when choosing and designing algorithms for particular applications. This research studies a representative algorithm for each category, matching pursuit (MP), basis pursuit (BP), and noise shaping (NS), in terms of their sparsifying capability and computational complexity. Experiments show that NS has the best performance in terms of sparsifying capability with the least computational complexity. BP has good sparsifying capability, but is computationally expensive. MP has relatively poor sparsifying capability and the computations are heavily dependent on the problem scale and signal complexity. Their performance differences are also evaluated for three typical applications of time-frequency analyses, signal denoising, and image coding. NS has good performance for time-frequency analyses and image coding with far fewer computations. However, NS does not perform well for signal denoising. This study provides guidelines for choosing an algorithm for a given problem and for designing or improving algorithms for sparse representation.