Performance Study of Various Sparse Representation Methods Using Redundant Frames

Sparse representations have recently received wide attention because of their numerous potential applications. In this paper, we consider sparse representations of signals with at most L non-zero coefficients using a frame F of size M in C^N. We bound the average distortion of such a representation for any arbitrary frame F by a numerical lower bound that is only a function of the sparsity epsiv = L/N of the representation, and the redundancy (r-1) = M/N-1 of F. This numerical lower bound is shown to be much stronger than the analytical and asymptotic bounds of in low dimensions (e.g. N = 6,8, 10), but it is much less straightforward to compute. We then study the performance of randomly generated frames with respect to this numerical lower bound, and to the analytical and asymptotic bounds. When the optimal sparse representation algorithm is used, it is observed that randomly generated frames perform about 2 dB away from the theoretical lower bound in low dimensions. We use the greedy orthogonal matching pursuit (OMP) algorithm to study the performance of randomly generated frames in higher dimensions. For small values of epsiv, randomly generated frames using OMP perform close to the lower bound and the results suggest that the loss of the sub-optimal search using orthogonal matching pursuit algorithm grows as a function of epsiv. As N grows, a concentration phenomenon for the performance of randomly generated frames about their average is observed in all cases, even when using the OMP algorithm.