  We discuss a strategy of sparse approximation that is based on the use of an
overcomplete basis, and evaluate its performance when a random matrix is used
as this basis. A small combination of basis vectors is chosen from a given
overcomplete basis, according to a given compression rate, such that they
compactly represent the target data with as small a distortion as possible. As
a selection method, we study the $\ell_0$- and $\ell_1$-based methods, which
employ the exhaustive search and $\ell_1$-norm regularization techniques,
respectively. The performance is assessed in terms of the trade-off relation
between the representation distortion and the compression rate. First, we
evaluate the performance analytically in the case that the methods are carried
out ideally, using methods of statistical mechanics. Our result clarifies the
fact that the $\ell_0$-based method greatly outperforms the $\ell_1$-based one.
Second, we examine the practical performances of two well-known algorithms,
orthogonal matching pursuit and approximate message passing, when they are used
to execute the $\ell_0$- and $\ell_1$-based methods, respectively. Our
examination shows that orthogonal matching pursuit achieves a much better
performance than the exact execution of the $\ell_1$-based method, as well as
approximate message passing. However, regarding the $\ell_0$-based method,
there is still room to design more effective greedy algorithms than orthogonal
matching pursuit. Finally, we evaluate the performances of the algorithms when
they are applied to image data compression.
