
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Cross LowDimension Pursuit for Sparse Signal Recovery from Incomplete Measurements Based on Permuted Block Diagonal Matrix
Zaixing HE Takahiro OGAWA Miki HASEYAMA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E94A
No.9
pp.17931803 Publication Date: 2011/09/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E94.A.1793 Print ISSN: 09168508 Type of Manuscript: PAPER Category: Digital Signal Processing Keyword: sparse recovery, sparsest solution, compressed sensing, permuted block diagonal matrix, greedy algorithms, orthogonal matching pursuit, ^{1}norm minimization, basis pursuit,
Full Text: PDF>>
Summary:
In this paper, a novel algorithm, Cross Lowdimension 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 highdimension sparse recovery problem into two (or more) groups of highly lowdimension 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 ^{1}norm minimization algorithms. Moreover, we demonstrate both theoretically and empirically that the proposed algorithm can reliably recover a sparse signal from highly incomplete measurements.


