Binary Sparse Signal Recovery with Binary Matching Pursuit
Binary Sparse Signal Recovery with Binary Matching Pursuit
复制标题
通过二进制匹配追踪进行二进制稀疏信号恢复
DOI：
10.1088/1361-6420/abf903
复制
发表时间：
2021
期刊：
影响因子：
2.1
通讯作者：
李海锋
中科院分区：
文献类型：
--
作者：
温金明;李海锋
在通信和信号处理的许多应用中，我们经常需要从稀疏噪声线性测量中获取K-稀疏二进制信号。在这项工作中，我们首先开发了一种算法，称为二进制匹配追踪（BMP）恢复的K-稀疏二进制信号。根据每次迭代是否显式地形成残差向量，我们开发了两种BMP实现，分别称为显式BMP和隐式BMP。分析了它们的复杂度，结果表明，与最快的批量正交匹配追踪（OMP）算法相比，显式BMP算法和隐式BMP算法的复杂度分别提高了n/（2K）和K倍。最后，利用感知矩阵的互相关性和约束等距性，给出了稀疏信号支持度稳定恢复的充分条件。仿真测试表明，隐式BMP算法比批处理OMP算法快约n/（2K）倍或更多倍，漏检率和虚警率降低约20%或更多。
In numerous applications from communications and signal processing, we often need to acquire a K-sparse binary signal from sparse noisy linear measurements. In this work, we first develop an algorithm called binary matching pursuit (BMP) to recover the K-sparse binary signal. According to whether the residual vector is explicitly formed or not at each iteration, we develop two implementations of BMP which are respectively called explicit BMP and implicit BMP. We then analyze their complexities and show that, compared to the batch-orthogonal matching pursuit (OMP), which is the fastest implementation of OMP, the improvements of the explicit and implicit BMP algorithms are respectively n/(2K) and K times when some quantities are pre-computed. Finally, we provide sharp sufficient conditions of stable recovery of the support of the sparse signal using mutual coherence and restricted isometry property of the sensing matrix. Simulation tests indicate that the implicit BMP algorithm is around or more than n/(2K) times faster than batch-OMP with around or more than 20% lower rates of missed detection and false alarm.