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(h_s)，每一列都正好有一个1，位置为h_s(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随机矩阵，这里h_s(i)是1/-1，决定于r_s,i的值是1/-1. 这里的x的求解依然是取中值，不过由于随机矩阵中的系数h_s(i)可能是1，可能是-1，所以要乘以r_s,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做稀疏恢复（这个地方不太懂）。

      

转载本文请联系原作者获取授权，同时请注明本文来自洪雁科学网博客。
链接地址：https://blog.sciencenet.cn/blog-353784-499984.html

上一篇：NetCompress - The realization of Real Network Codes
下一篇：Partial network coding: concept, performance, and applicatio