Sparse approximation based on a random overcomplete basis

Abstract

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.

35 pages, 11 figures

Cited by in corpus (10)

• Exhaustive search for sparse variable selection in linear regression
• Exploiting Restricted Boltzmann Machines and Deep Belief Networks in Compressed Sensing
• One mask to rule them all: Writing arbitrary distributions of radiant exposure by scanning a single illuminated spatially-random screen
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Effective implementation of $l_0$-Regularised Compressed Sensing with Chaotic-Amplitude-Controlled Coherent Ising Machines
• Highly Versatile FPGA-Implemented Cyber Coherent Ising Machine
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Evaluation of Generalized Degrees of Freedom for Sparse Estimation by Replica Method
• Reconstructing Sparse Signals via Greedy Monte-Carlo Search
• Approximate cross-validation formula for Bayesian linear regression