检索结果-内蒙古大学图书馆

Failure Analysis of the interval-passing algorithm for Compressed Sensing

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第4期66卷 2466-2486页

作者： Yakimenka, Yauhen Rosnes, Eirik Univ Tartu Inst Comp Sci EE-50409 Tartu Estonia Simula UiB N-5020 Bergen Norway

In this work, we perform a complete failure analysis of the interval-passing algorithm (IPA) for compressed sensing. The IPA is an efficient iterative algorithm for reconstructing a k-sparse nonnegative n-dimensional real signal x from a small number of linear measurements y. In particular, we show that the IPA fails to recover x from y if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance to the success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover x if and only if the support of x contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Two heuristics to locate small-size termatiko sets are presented. For binary column-regular measurement matrices with no 4-cycles, we provide a lower bound on the termatiko distance, defined as the smallest size of a nonempty termatiko set. For measurement matrices constructed from the parity-check matrices of array low-density parity-check codes, upper bounds on the termatiko distance equal to half the best known upper bound on the minimum distance are provided for column-weight at most 7, while for column-weight 3, the exact termatiko distance and its corresponding multiplicity are provided. Next, we show that adding redundant rows to the measurement matrix does not create new termatiko sets, but rather potentially removes termatiko sets and thus improves performance. An algorithm is provided to efficiently search for such redundant rows. Finally, we present numerical results for different specific measurement matrices and also for protograph-based ensembles of measurement matrices, as well as simulation results of IPA performance, showing the influence of small-size termatiko sets.

关键词： Compressed sensing interval-passing algorithm low-density parity-check (LDPC) codes message-passing algorithm stopping sets termatiko sets

来源：评论

学校读者我要写书评

暂无评论

Verification-Based interval-passing algorithm for Compressed Sensing

引用

IEEE SIGNAL PROCESSING LETTERS 2013年第10期20卷 933-936页

作者： Wu, Xiaofu Yang, Zhen Nanjing Univ Posts & Telecommun Inst Signal Proc & Transmiss Nanjing 210003 Jiangsu Peoples R China

We propose a verification-based interval-passing (IP) algorithm for iteratively reconstruction of nonnegative sparse signals using parity check matrices of low-density parity check (LDPC) codes as measurement matrices. The proposed algorithm can be considered as an improved IP algorithm by further incorporation of the mechanism of verification algorithm. It is proved that the proposed algorithm performs always better than either the IP algorithm or the verification algorithm. Simulation results are also given to demonstrate the superior performance of the proposed algorithm.

关键词： Compressed sensing interval-passing algorithm low-density parity-check (LDPC) codes sparse measurements verification algorithm

来源：评论

学校读者我要写书评

暂无评论

interval-passing algorithm for Non-Negative Measurement Matrices: Performance and Reconstruction Analysis

引用

IEEE JOURNAL ON EMERGING AND SELECTED TOPICS IN CIRCUITS AND SYSTEMS 2012年第3期2卷 424-432页

作者： Ravanmehr, Vida Danjean, Ludovic Vasic, Bane Declercq, David Univ Arizona Dept Elect & Comp Engn Tucson AZ 85721 USA Univ Cergy Pontoise CNRS ETIS ENSEA F-95000 Cergy Pontoise France

We consider the interval-passing algorithm (IPA), an iterative reconstruction algorithm for reconstruction of non-negative sparse real-valued signals from noise-free measurements. We first generalize the IPA by relaxing the original constraint that the measurement matrix must be binary. The new algorithm operates on any non-negative sparse measurement matrix. We give a performance comparison of the generalized IPA with the reconstruction algorithms based on 1) linear programming and 2) verification decoding. Then we identify signals not recoverable by the IPA on a given measurement matrix, and show that these signals are related to stopping sets responsible to failures of iterative decoding algorithms on the binary erasure channel (BEC). Contrary to the results of the iterative decoding on the BEC, the smallest stopping set of a measurement matrix is not the smallest configuration on which the IPA fails. We analyze the recovery of sparse signals on subsets of stopping sets via the IPA and provide sufficient conditions on the exact recovery of sparse signals. Reconstruction performance of the IPA using the IEEE 802.16e LDPC codes as measurement matrices are given to show the effect of stopping sets in the performance of the IPA.

关键词： Compressed sensing interval-passing algorithm iterative reconstruction algorithm low-density parity-check codes message-passing algorithm stopping sets

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：