Cross Low-Dimension Pursuit for Sparse Signal Recovery from Incomplete Measurements Based on Permuted Block Diagonal Matrix
Cross Low-Dimension Pursuit for Sparse Signal Recovery from Incomplete Measurements Based on Permuted Block Diagonal Matrix
复制标题
DOI：
10.1587/transfun.e94.a.1793
复制
发表时间：
2011-09
期刊：
影响因子：
--
通讯作者：
Zaixing He;Takahiro Ogawa;M. Haseyama
中科院分区：
文献类型：
--
作者：
Zaixing He;Takahiro Ogawa;M. Haseyama
本文提出了一种基于新结构稀疏矩阵——置换块对角（PBD）矩阵的交叉低维追踪算法，以便从不完整的线性测量中恢复稀疏信号。该方法的主要思想是利用PBD矩阵将高维稀疏恢复问题转换为两组（或更多）组高度低维问题，并以迭代方式从它们中交叉恢复原始信号的条目。通过使用 PBD 矩阵对足够稀疏的信号进行采样，所提出的算法可以有效地恢复它。与传统算法相比，它具有以下优点：（1）复杂度低，即该算法具有线性复杂度，远低于现有算法，包括正交匹配追踪等贪婪算法；（2）恢复能力高，即该算法可以恢复比l1范数最小化算法少得多的稀疏信号。此外，我们从理论上和经验上证明，所提出的算法可以从高度不完整的测量中可靠地恢复稀疏信号。
In this paper, a novel algorithm, Cross Low-dimension Pursuit, based on a new structured sparse matrix, Permuted Block Diagonal (PBD) matrix, is proposed in order to recover sparse signals from incomplete linear measurements. The main idea of the proposed method is using the PBD matrix to convert a high-dimension sparse recovery problem into two (or more) groups of highly low-dimension problems and crossly recover the entries of the original signal from them in an iterative way. By sampling a sufficiently sparse signal with a PBD matrix, the proposed algorithm can recover it efficiently. It has the following advantages over conventional algorithms: (1) low complexity, i.e., the algorithm has linear complexity, which is much lower than that of existing algorithms including greedy algorithms such as Orthogonal Matching Pursuit and (2) high recovery ability, i.e., the proposed algorithm can recover much less sparse signals than even l1-norm minimization algorithms. Moreover, we demonstrate both theoretically and empirically that the proposed algorithm can reliably recover a sparse signal from highly incomplete measurements.