Sparse approximation based on a random overcomplete basis
Sparse approximation based on a random overcomplete basis
复制标题
DOI：
10.1088/1742-5468/2016/06/063302
复制
发表时间：
2016-06-01
影响因子：
2.4
通讯作者：
Kabashima, Yoshiyuki
中科院分区：
文献类型：
--
作者：
Nakanishi-Ohno, Yoshinori;Obuchi, Tomoyuki;Kabashima, Yoshiyuki
我们讨论了一种基于使用过完备基的稀疏逼近策略，并评估了随机矩阵用作此基础时的性能。根据给定的压缩率，从给定的过完备基中选择基向量的小组合，使得它们以尽可能小的失真来压缩地表示目标数据。作为选择方法，我们研究了基于l（0）和l（1）的方法，分别采用穷举搜索和l（1）范数正则化技术。的性能进行评估的失真和压缩率之间的权衡关系。首先，我们评估的性能分析的情况下，该方法进行了理想的，使用统计力学的方法。然后，通过对有限尺寸系统进行数值实验，并将结果外推到无限尺寸极限，证实了分析结果。我们的结果澄清了这样一个事实，即基于l（0）的方法大大优于基于l（1）的方法。我们的分析的一个有趣的结果是，对于基于l（0）和l（1）的方法，在过完备基的大尺寸限制中，对于任何固定的压缩率r，任何小的失真值都是可以实现的。这两种方法之间的差异表现在为了实现失真的期望值所需的过完备基的大小上。随着期望的失真减小，所需的大小分别对于基于l（0）和基于l（1）的方法以多项式和指数方式增长。其次，我们研究了两个著名的算法，正交匹配追踪和近似消息传递的实际性能，当它们被用来执行的l（0）和l（1）为基础的方法，分别。我们的研究表明，正交匹配追踪实现了更好的性能比精确执行的l（1）为基础的方法，以及近似的消息传递。然而，对于基于l（0）的方法，仍然存在设计比正交匹配追踪更有效的贪婪算法的空间。最后，我们评估的算法时，他们被应用到图像数据压缩的性能。
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.