博文
Approximate Message Passing vs. Sparse Bayesian Learning?
|||
上周Nuit Blanche发了一篇博文《More intra-block correlation and sparse sensing matrices》，内容是The Ohio State University的Phil写给他的一封邮件，其中介绍了Phil组里最近投出的基于Approximate Message Passing (AMP)的压缩传感（Compressed Sensing, CS）算法。信中最后说道，“we get performance that meets or exceeds that of Bayesian or variational techniques, but with orders-of-magnitude reduction in complexity”，也就是说，AMP算法比稀疏贝叶斯学习（Sparse Bayesian Learning, SBL）算法性能要好，同时速度快了一个档次。但是这句话是值得商酌的，不正确的。我猜想Phil的意思是，在他们的文章中给出的试验条件和应用场合里（比如video/image coding），AMP比目前的SBL既好又快。
其实在很多情况下和实际应用中，SBL都比AMP性能远远优越。第一个情况就是，当传感矩阵(sensing matrix)或者字典矩阵（dictionary matrix）的列与列之间非常相关时，决大多数算法包括AMP算法性能都非常差。而SBL算法的性能却保持良好。这种情况多见于source localization and tracking (比如波达方向估计，脑源定位，雷达探测……），生物医学数据分析（比如基因表达中的特征提取，神经成像数据中的特征提取），以及计算视觉（比如基于稀疏表达的人脸识别，表情识别，视觉追踪等等）。实际上，SBL在这种情况下的优势已经部分的被我们实验室的师兄David Wipf证明过了。他在2011年的NIPS文章《Sparse Estimation with Structured Dictionaries》里，从数学上证明了在这种sensing matrix (or dictionary matrix)非常coherent的情况下，为什么SBL比Lasso性能要好。
为了让读者对这种情况下的各个压缩传感算法的性能有多差有个感性认识，我在提供了一个Matlab仿真程序供下载：http://dsp.ucsd.edu/~zhilin/papers/Localization.zip. 这个仿真程序模拟了一个简单的基于multiple snapshots的脑电源定位的试验，其中的sensing matrix(在EEG领域，叫做lead-field matrix）来自于由一个大脑模型构建的lead-field matrix（通常是100 x 10000维，但是我把它缩小成了50x400维，这样可以在1秒左右的时间里就可以获得结果）。这个sensing matrix的列与列之间的相关性可达0.99以上。我比较了我们实验室的三种成名算法，分别是M-FOCUSS,M-SBL和我的T-MSBL。读者可以看到SBL算法远远比M-FOCUSS算法好。读者也可以利用这个程序使用自己喜好的熟悉的算法，可以看到在这种情况下其它算法的性能非常差。
另外，在这里http://dsp.ucsd.edu/~zhilin/papers/Experiment.rar 我提供了一个基于single snapshot的源定位试验仿真程序。这里比较了14个算法的性能，可以看到SBL算法性能最好，尤其是T-MSBL。这个试验还有一个note,可以在这里下载：http://dsp.ucsd.edu/~zhilin/papers/comparison.pdf
除了上面这个情况外，当信号不是特别稀疏甚至根本不稀疏的时候，SBL算法也表现出很好的优势。在我的关于生理信号远程监控的文章《Low Energy Wireless Body-Area Networks for Fetal ECG Telemonitoring via the Framework of Block Sparse Bayesian Learning》中，大量的试验显示了BSBL能够以很高的质量直接恢复非稀疏的信号（i.e.,不借助于其它技术）。另外在我的文章《Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation》中，也显示了BSBL在无噪条件下并且已知Block Structure的情况下，可以仅仅只用M个测量值精确恢复一个有M个非零元素的长度为N的信号（N远远大于M,比如N=10M，非零元素的位置未知）。所以，大量的试验显示了SBL对于非稀疏，或者不是特别稀疏的信号有明显的优势。要知道，在绝大多数实际问题中，信号并不是特别稀疏的。在compressed sensing领域中，传统上大家通过寻找dictionary matrix来获得信号的稀疏表示。但是目前这个方向还正在发展，对很多非稀疏信号并不能找到有效的稀疏表示。而SBL从另外一个方向获得了突破。关于BSBL能够只用M个测量值精确恢复一个有M个非零元素的长度为N的信号，其实可以用我的文章《Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning》中的定理1来证明。所以这里就不过多展开了。
正因为在实际问题中，通常sensing matrix（或者dictonary matrix）列与列之间相关性很大，信号又并不很稀疏，导致了绝大多数已有的算法并不能达到特别理想的效果（或者效果还有很大的提升空间），而SBL则显示出了很大的优势。所以SBL作为压缩传感/稀疏信号处理的一个分支，越来越多的应用在很多实际问题中。我们实验室，作为开发SBL算法的主要实验室之一，已经和国内，美国，欧洲不少学校/研究机构开始了合作。相信明年会有大批应用的文章涌现。
当然，SBL的速度不快。但是这种情况正在转变。一个原因是，SBL可以转换成一个加权迭代的算法。比如，在我的文章《Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation》中，BSBL算法可以用group Lasso算法迭代3-4次实现。每年都有不少的更快的group Lasso算法提出来，所以可以预见BSBL算法也会越来越快。另外，现在也有不少比较快的SBL算法了。比如我上面这篇文章中的BSBL-BO算法，以及我们最近的CVPR 2012文章《Sparse Bayesian Multi-Task Learning for Predicting Cognitive Outcomes from Neuroimaging Measures in Alzheimer's Disease》中的基于固定点的快速算法。我现在还有几个更快的算法，大概下个月就要投出去了。
综上，基于Phil的那句可能会引起误会的话，我在这里把SBL的几个优势稍微讲解了一下。有兴趣的朋友可以去我网页http://dsp.ucsd.edu/~zhilin/ 或者https://sites.google.com/site/researchbyzhang/ 详细了解SBL算法，最近的发展和下载这篇博文中提到的文章（以及代码）。另外，我和武汉大学的孙洪老师，余磊朋友有一篇中文的邀请综述：《从稀疏到结构化稀疏：贝叶斯方法》（后半部分是我们实验室开发的一系列SBL算法），发表在最近的《信号处理》杂志上。网上可以下载到。
https://blog.sciencenet.cn/blog-765184-599713.html
下一篇：我们一篇脑电信号的压缩感知文章被IEEE T-BME接收了
其实在很多情况下和实际应用中，SBL都比AMP性能远远优越。第一个情况就是，当传感矩阵(sensing matrix)或者字典矩阵（dictionary matrix）的列与列之间非常相关时，决大多数算法包括AMP算法性能都非常差。而SBL算法的性能却保持良好。这种情况多见于source localization and tracking (比如波达方向估计，脑源定位，雷达探测……），生物医学数据分析（比如基因表达中的特征提取，神经成像数据中的特征提取），以及计算视觉（比如基于稀疏表达的人脸识别，表情识别，视觉追踪等等）。实际上，SBL在这种情况下的优势已经部分的被我们实验室的师兄David Wipf证明过了。他在2011年的NIPS文章《Sparse Estimation with Structured Dictionaries》里，从数学上证明了在这种sensing matrix (or dictionary matrix)非常coherent的情况下，为什么SBL比Lasso性能要好。
为了让读者对这种情况下的各个压缩传感算法的性能有多差有个感性认识，我在提供了一个Matlab仿真程序供下载：http://dsp.ucsd.edu/~zhilin/papers/Localization.zip. 这个仿真程序模拟了一个简单的基于multiple snapshots的脑电源定位的试验，其中的sensing matrix(在EEG领域，叫做lead-field matrix）来自于由一个大脑模型构建的lead-field matrix（通常是100 x 10000维，但是我把它缩小成了50x400维，这样可以在1秒左右的时间里就可以获得结果）。这个sensing matrix的列与列之间的相关性可达0.99以上。我比较了我们实验室的三种成名算法，分别是M-FOCUSS,M-SBL和我的T-MSBL。读者可以看到SBL算法远远比M-FOCUSS算法好。读者也可以利用这个程序使用自己喜好的熟悉的算法，可以看到在这种情况下其它算法的性能非常差。
另外，在这里http://dsp.ucsd.edu/~zhilin/papers/Experiment.rar 我提供了一个基于single snapshot的源定位试验仿真程序。这里比较了14个算法的性能，可以看到SBL算法性能最好，尤其是T-MSBL。这个试验还有一个note,可以在这里下载：http://dsp.ucsd.edu/~zhilin/papers/comparison.pdf
除了上面这个情况外，当信号不是特别稀疏甚至根本不稀疏的时候，SBL算法也表现出很好的优势。在我的关于生理信号远程监控的文章《Low Energy Wireless Body-Area Networks for Fetal ECG Telemonitoring via the Framework of Block Sparse Bayesian Learning》中，大量的试验显示了BSBL能够以很高的质量直接恢复非稀疏的信号（i.e.,不借助于其它技术）。另外在我的文章《Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation》中，也显示了BSBL在无噪条件下并且已知Block Structure的情况下，可以仅仅只用M个测量值精确恢复一个有M个非零元素的长度为N的信号（N远远大于M,比如N=10M，非零元素的位置未知）。所以，大量的试验显示了SBL对于非稀疏，或者不是特别稀疏的信号有明显的优势。要知道，在绝大多数实际问题中，信号并不是特别稀疏的。在compressed sensing领域中，传统上大家通过寻找dictionary matrix来获得信号的稀疏表示。但是目前这个方向还正在发展，对很多非稀疏信号并不能找到有效的稀疏表示。而SBL从另外一个方向获得了突破。关于BSBL能够只用M个测量值精确恢复一个有M个非零元素的长度为N的信号，其实可以用我的文章《Sparse Signal Recovery with Temporally Correlated Source Vectors Using Sparse Bayesian Learning》中的定理1来证明。所以这里就不过多展开了。
正因为在实际问题中，通常sensing matrix（或者dictonary matrix）列与列之间相关性很大，信号又并不很稀疏，导致了绝大多数已有的算法并不能达到特别理想的效果（或者效果还有很大的提升空间），而SBL则显示出了很大的优势。所以SBL作为压缩传感/稀疏信号处理的一个分支，越来越多的应用在很多实际问题中。我们实验室，作为开发SBL算法的主要实验室之一，已经和国内，美国，欧洲不少学校/研究机构开始了合作。相信明年会有大批应用的文章涌现。
当然，SBL的速度不快。但是这种情况正在转变。一个原因是，SBL可以转换成一个加权迭代的算法。比如，在我的文章《Extension of SBL Algorithms for the Recovery of Block Sparse Signals with Intra-Block Correlation》中，BSBL算法可以用group Lasso算法迭代3-4次实现。每年都有不少的更快的group Lasso算法提出来，所以可以预见BSBL算法也会越来越快。另外，现在也有不少比较快的SBL算法了。比如我上面这篇文章中的BSBL-BO算法，以及我们最近的CVPR 2012文章《Sparse Bayesian Multi-Task Learning for Predicting Cognitive Outcomes from Neuroimaging Measures in Alzheimer's Disease》中的基于固定点的快速算法。我现在还有几个更快的算法，大概下个月就要投出去了。
综上，基于Phil的那句可能会引起误会的话，我在这里把SBL的几个优势稍微讲解了一下。有兴趣的朋友可以去我网页http://dsp.ucsd.edu/~zhilin/ 或者https://sites.google.com/site/researchbyzhang/ 详细了解SBL算法，最近的发展和下载这篇博文中提到的文章（以及代码）。另外，我和武汉大学的孙洪老师，余磊朋友有一篇中文的邀请综述：《从稀疏到结构化稀疏：贝叶斯方法》（后半部分是我们实验室开发的一系列SBL算法），发表在最近的《信号处理》杂志上。网上可以下载到。
https://blog.sciencenet.cn/blog-765184-599713.html
下一篇：我们一篇脑电信号的压缩感知文章被IEEE T-BME接收了
