|||
1. 总结了2001到2010年之间,利用稀疏矩阵来做稀疏表示和恢复的方案和算法。阐述了linear sketch的思想与应用,并对稀疏矩阵做稀疏表示和恢复的方案做了定义和分类。
文章把稀疏矩阵做稀疏表示和恢复的方案分为两类:for-each and for all. For all方案:一个测量矩阵A应用于整个信号;而for-each方案的测量矩阵A有多个随机的分布组成。
2. 文章回顾了for-each的三种算法。分别是count-min and count-median、Count-Sketch、Sub-linear algorithms。
Count-min和Count-Median算法是很native的方案。考虑稀疏矩阵A,A是由d个w×n的矩阵连接成的。对于每个w×n的矩阵,记为A(hs),每一列都正好有一个1,位置为hs(i),其他值为0. y=Ax,获得了m维测量矢量y,y也是由d个w维矢量组成。对于第s个w维矢量,每一个y都至少有一个x的线性组合。对于方程 ,省略号中的数据多数为零。这样的话,x可能对多个y有贡献,而其中最小的那个y,就是最大可能的近似。这就是count-min算法的思想。然而这只是考虑非负信号,对于普通信号count-min就不适合了。然后考虑count-median算法,这次不是去最小的那个y,而是取中值(注意中值不是均值)。因为对于一个普通信号,其他的x对y的影响可能是正的也可能是负的,中值最有可能是原始信号的值。
Count-Sketch算法也是很朴实的想法,和count-min的思想近似。但是矩阵的生成方式不太相同,前面的矩阵是0/1随机矩阵,这里hs(i)是1/-1,决定于rs,i的值是1/-1. 这里的x的求解依然是取中值,不过由于随机矩阵中的系数hs(i)可能是1,可能是-1,所以要乘以rs,i。
Sub-linear algorithms是另一种算法。考虑x只有一个系数非零,可以用bit-tester matrix来获得x。bit-test matrix就是说每一列的值都是对应列序号的二进制,有log(n)行,为了在全零的时候能够得到x的值,又加了一排全1,也就是总共有log(n)+1行。但是没有信号只有一个非零值,所以先用hash函数,将这些非零值都分隔开。如果从一个预定的函数族中随机选择hash函数,将不同的测量值hash到同一个位置的概率非常小(hash函数可以做到分隔各个非零值吗?毕竟非零值的位置是未知的)。
3. 文章还回顾了for all的几种算法。首先阐述并证明了RIP(1)可以用于验证方案是否可以利用l1-minimization做稀疏恢复。然后描述了EMP and SMP、Connections to Message-Passing Algorithms、HHS and Sub-linear Algorithms.
满足RIP(2)的矩阵A,利用l1-minimization可以获得精确的结果。但是稀疏矩阵不能满足RIP(2),除非这个矩阵很大。文章阐述并证明了RIP(1)可以用于验证方案是否可以利用l1-minimization做稀疏恢复(这个地方不太懂)。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-5-3 06:38
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社