Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4
Expander Recovery Performance of Bipartite Graphs With Girth Greater Than 4
复制标题
周长大于4的二分图的扩展恢复性能
DOI：
10.1109/tsipn.2018.2889229
复制
发表时间：
2019
影响因子：
3.2
通讯作者：
Xia Shu-Tao
中科院分区：
文献类型：
--
作者：
Lu Weizhi;Li Weiyu;Zhang Wei;Xia Shu-Tao
扩展恢复是一种迭代算法，旨在恢复具有线性复杂度的二进制矩阵测量的稀疏信号。本文研究了围长大于4的二部图的扩展恢复性能，它可以与列相关性等于0或1的二元矩阵相关联。对于这样的图，扩展恢复被证明可以实现与传统的基追踪恢复相同的性能，因为信号是分离的。与广泛用于扩展器恢复的随机图相比，我们研究的图倾向于呈现更好的经验性能。此外，其特殊的结构，使扩展恢复的迭代次数从<inline-formula><tex-math notation="LaTeX">$O（n\log k）$</tex-math></inline-formula>次减少到正好<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>次在串行恢复，并从<inline-formula><tex-math notation="LaTeX">$\mathcal {O}（\log k）$</tex-math></inline-formula>次减少到正好一次在并行恢复。
Expander recovery is an iterative algorithm designed to recover sparse signals measured with binary matrices with linear complexity. In the paper, we study the expander recovery performance of the bipartite graph with girth greater than 4, which can be associated with a binary matrix with column correlations equal to either 0 or 1. For such a graph, expander recovery is proved to achieve the same performance as the traditional basis pursuit recovery, as the signal is dissociated. Compared to random graphs widely used for expander recovery, the graph we study tends to present better empirical performance. Furthermore, its special structure enables reducing the iteration number of expander recovery from <inline-formula><tex-math notation="LaTeX">$O(n\log k)$</tex-math></inline-formula> times to exactly <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula> times in serial recovery, and from <inline-formula><tex-math notation="LaTeX">$\mathcal {O}(\log k)$</tex-math></inline-formula> times to exactly one time in parallel recovery.