Sparse approximation based on a random overcomplete basis

作者：Nakanishi Ohno Yoshinori^*; Obuchi Tomoyuki; Okada Masato; Kabashima Yoshiyuki

来源：Journal of Statistical Mechanics: Theory and Experiment , 2016, 2016(6): 063302.

DOI：10.1088/1742-5468/2016/06/063302

• analysis of algorithms
• heuristics
• source and channel coding
• statistical inference

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 l(0)- and l(1)-based methods, which employ the exhaustive search and l(1)-norm regularization techniques, respectively. The performance is assessed in terms of the trade-off relation between the 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. The analytical result is then confirmed by performing numerical experiments on finite size systems, and extrapolating the results to the infinite-size limit. Our result clarifies the fact that the l(0)-based method greatly outperforms the l(1)-based one. An interesting outcome of our analysis is that any small value of distortion is achievable for any fixed compression rate r in the large-size limit of the overcomplete basis, for both the l(0)- and l(1)-based methods. The difference between these two methods is manifested in the size of the overcomplete basis that is required in order to achieve the desired value for the distortion. As the desired distortion decreases, the required size grows in a polynomial and an exponential manners for the l(0)- and l(1)-based methods, respectively. 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 l(0)- and l(1)-based methods, respectively. Our examination shows that orthogonal matching pursuit achieves a much better performance than the exact execution of the l(1)-based method, as well as approximate message passing. However, regarding the l(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.

• 出版日期2016-6