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

53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)

作者： Kumar, Santhosh Vem, Avinash Narayanan, Krishna Pfister, Henry D. Texas A&M Univ Dept Elect & Comp Engn College Stn TX 77843 USA Duke Univ Dept Elect & Comp Engn Durham NC 27706 USA

ISBN: (纸本)9781509018246

The focus of this article is on low-complexity capacity-achieving coding schemes for write-once memory (WOM) systems. The construction is based on spatially-coupled compound LDGM/LDPC codes. Both noiseless systems and systems with read errors are considered. Compound LDGM/LDPC codes are known to achieve capacity under MAP decoding for the closely related Gelfand-Pinsker problem and their coset decomposition provides an elegant way to encode the messages while simultaneously providing error protection. The application of compound codes to the WOM system is new. The main result is that spatial coupling enables these codes to achieve the capacity region of the 2-write WOM system with low-complexity message-passing encoding and decoding algorithms.

关键词： data storage LDGM codes LDPC codes message-passing algorithms spatial coupling write-once memory system

来源：评论

学校读者我要写书评

暂无评论

Belief-Propagation Reconstruction for Compressed Sensing: Quantization vs. Gaussian Approximation 53

Belief-Propagation Reconstruction for Compressed Sensing: Qu...

引用

53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)

作者： Lian, Mengke Pfister, Henry D. Duke Univ Dept Elect & Comp Engn Durham NC 27706 USA

ISBN: (纸本)9781509018246

This work considers the compressed sensing (CS) of i.i.d. signals with sparse measurement matrices and belief-propagation (BP) reconstruction. In general, BP reconstruction for CS requires the passing of messages that are distributions over the real numbers. To implement this in practice, one typically uses either quantized distributions or a Gaussian approximation. In this work, we use density evolution to compare the reconstruction performance of these two methods. Since the reconstruction performance depends on the signal realization, this analysis makes use of a novel change of variables to analyze the performance for a typical signal. Simulation results are provided to support the results.

关键词： compressed sensing density evolution LDPC codes message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第5期000卷 P05013-P05013页

作者： Barbier, Jean Schuelke, Christophe Krzakala, Florent Ecole Normale Super CNRS UMR 8550 Phys Stat Lab F-75231 Paris France Univ Paris 06 F-75231 Paris France Univ Paris 06 Sorbonne Univ UMR 8550 F-75231 Paris France Univ Paris Diderot Sorbonne Paris Cite F-75205 Paris France Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy

We study the behavior of approximate message-passing (AMP), a solver for linear sparse estimation problems such as compressed sensing, when the i.i.d matrices-for which it has been specifically designed-are replaced by structured operators, such as Fourier and Hadamard ones. We show empirically that after proper randomization, the structure of the operators does not significantly affect the performances of the solver. Furthermore, for some specially designed spatially coupled operators, this allows a computationally fast and memory efficient reconstruction in compressed sensing up to the information-theoretical limit. We also show how this approach can be applied to sparse superposition codes, allowing the AMP decoder to perform at large rates for moderate block length.

关键词： message-passing algorithms error-correcting codes statistical inference

来源：评论

学校读者我要写书评

暂无评论

Blind sensor calibration using approximate message passing

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第11期2015卷 1-1页

作者： Schuelke, Christophe Caltagirone, Francesco Zdeborova, Lenka Univ Paris 07 Sorbonne Paris Cite F-75013 Paris France Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Ecole Normale Super CNRS Lab Phys Stat UMR 8550 F-75231 Paris France Univ Paris 06 F-75231 Paris France CEA Saclay Inst Phys Theor F-91191 Gif Sur Yvette France CNRS URA 2306 F-91191 Gif Sur Yvette France

The ubiquity of approximately sparse data has led a variety of communities to take great interest in compressed sensing algorithms. Although these are very successful and well understood for linear measurements with additive noise, applying them to real data can be problematic if imperfect sensing devices introduce deviations from this ideal signal acquisition process, caused by sensor decalibration or failure. We propose a message passing algorithm called calibration approximate message passing (Cal-AMP) that can treat a variety of such sensor-induced imperfections. In addition to deriving the general form of the algorithm, we numerically investigate two particular settings. In the first, a fraction of the sensors is faulty, giving readings unrelated to the signal. In the second, sensors are decalibrated and each one introduces a different multiplicative gain to the measurements. Cal-AMP shares the scalability of approximate message passing, allowing us to treat large sized instances of these problems, and experimentally exhibits a phase transition between domains of success and failure.

关键词： message-passing algorithms statistical inference

来源：评论

学校读者我要写书评

暂无评论

Typical reconstruction limits for distributed compressed sensing based on l_2,1-norm minimization and Bayesian optimal reconstruction

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2015年第5期000卷 P05029-P05029页

作者： Shiraki, Yoshifumi Kabashima, Yoshiyuki NTT Corp NTT Commun Sci Lab Atsugi Kanagawa 2430198 Japan Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Yokohama Kanagawa 2268502 Japan

The distributed compressed sensing framework provides an efficient compression scheme of multichannel signals that are sparse in some domains and highly correlated with one another. In particular, a signal model called the joint sparse model 2 (JSM-2) or multiple measurement vector problem, in which all sparse signals share their support, is important for dealing with practical problems such as magnetic resonance imaging and magnetoencephalography. In this paper, we investigate the typical reconstruction performance of JSM-2 problems for two schemes. One is l(2,1)-norm minimization reconstruction and the other is Bayesian optimal reconstruction. Employing the replica method, we show that the reconstruction performance of both schemes which exploit the knowledge of the sharing of the signal support overcomes that of their corresponding approaches for the single-channel compressed sensing problem. We also develop a computationally feasible approximate algorithm for performing the Bayes optimal scheme to validate our theoretical estimation. Our replica-based analysis numerically indicates that the spinodal point of the Bayesian reconstruction disappears, which implies that a fundamental reconstruction limit can be achieved by the BP-based approximate algorithm in a practical amount of time when the number of channels is sufficiently large. The results of the numerical experiments of both reconstruction schemes agree excellently with the theoretical evaluation.

关键词： message-passing algorithms source and channel coding communication supply and information networks

来源：评论

学校读者我要写书评

暂无评论

Belief-Propagation Reconstruction for Compressed Sensing: Quantization vs. Gaussian Approximation

Belief-Propagation Reconstruction for Compressed Sensing: Qu...

引用

Annual Allerton Conference on Communication, Control, and Computing

作者： Mengke Lian Henry D. Pfister Department of Electrical and Computer Engineering Duke University NC 27708 United States

ISBN: (纸本)9781509018253

关键词： compressed sensing density evolution LDPC codes message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

On Decoding Irregular Tanner Codes With Local-Optimality Guarantees

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第1期60卷 191-211页

作者： Halabi, Nissim Even, Guy Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora et al., Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e. g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter exists (whereby notably is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise threshol

关键词： Error bounds factor graphs graph cover IDPC codes linear programming (LP) decoding local optimality max-product algorithm maximum-likelihood (ML) certificate memoryless binary-input output-symmetric (MBIOS) channel message-passing algorithms min-sum algorithm Tanner codes thresholds

来源：评论

学校读者我要写书评

暂无评论

Dynamic Check message Majority-Logic Decoding Algorithm for Non-binary LDPC Codes

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1356-1364页

作者： Lu, Yichao Peng, Xiao Tian, Guifen Goto, Satoshi Waseda Univ Grad Sch IPS Kitakyushu Fukuoka 8080135 Japan NEC Corp Ltd Kawasaki Kanagawa 2128520 Japan CSRD Toshiba Kawasaki Kanagawa 2118666 Japan

Majority-logic algorithms are devised for decoding non-binary LDPC codes in order to reduce computational complexity. However, compared with conventional belief propagation algorithms, majority-logic algorithms suffer from severe bit error performance degradation. This paper presents a low-complexity reliability-based algorithm aiming at improving error correcting ability of majority-logic algorithms. Reliability measures for check nodes are novelly introduced to realize mutual update between variable message and check message, and hence more efficient reliability propagation can be achieved, similar to belief-propagation algorithm. Simulation results on NB-LDPC codes with different characteristics demonstrate that our algorithm can reduce the bit error ratio by more than one order of magnitude and the coding gain enhancement over ISRB-MLGD can reach 0.2-2.0 dB, compared with both the ISRB-MLGD and IISRB-MLGD algorithms. Moreover, simulations on typical LDPC codes show that the computational complexity of the proposed algorithm is closely equivalent to ISRB-MLGD algorithm, and is less than 10% of Min-max algorithm. As a result, the proposed algorithm achieves a more efficient trade-off between decoding computational complexity and error performance.

关键词： non-binary LDPC codes majority-logic decoding iterative decoding message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable detection of statistically significant communities and hierarchies, using message passing for modularity

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2014年第51期111卷 18144-18149页

作者： Zhang, Pan Moore, Cristopher Santa Fe Inst Santa Fe NM 87501 USA

Modularity is a popular measure of community structure. However, maximizing the modularity can lead to many competing partitions, with almost the same modularity, that are poorly correlated with each other. It can also produce illusory "communities" in random graphs where none exist. We address this problem by using the modularity as a Hamiltonian at finite temperature and using an efficient belief propagation algorithm to obtain the consensus of many partitions with high modularity, rather than looking for a single partition that maximizes it. We show analytically and numerically that the proposed algorithm works all of the way down to the detectability transition in networks generated by the stochastic block model. It also performs well on real-world networks, revealing large communities in some networks where previous work has claimed no communities exist. Finally we show that by applying our algorithm recursively, subdividing communities until no statistically significant subcommunities can be found, we can detect hierarchical structure in real-world networks more efficiently than previous methods.

关键词： networks community detection message-passing algorithms statistical significance phase transitions

来源：评论

学校读者我要写书评

暂无评论

The Network Source Location Problem: Ground State Energy, Entropy and Effects of Freezing

引用

JOURNAL OF STATISTICAL PHYSICS 2014年第2期156卷 301-335页

作者： Huang, Haiping Raymond, Jack Wong, K. Y. Michael Hong Kong Univ Sci & Technol Dept Phys Clear Water Bay Hong Kong Peoples R China Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy

Ground state entropy of the network source location problem is evaluated at both the replica symmetric level and one-step replica symmetry breaking level using the entropic cavity method. The regime that is a focus of this study, is closely related to the vertex cover problem with randomly quenched covered nodes. The resulting entropic message passing inspired decimation and reinforcement algorithms are used to identify the optimal location of sources in single instances of transportation networks. The conventional belief propagation without taking the entropic effect into account is also compared. We find that in the glassy phase the entropic message passing inspired decimation yields a lower ground state energy compared to the belief propagation without taking the entropic effect. Using the extremal optimization algorithm, we study the ground state energy and the fraction of frozen hubs, and extend the algorithm to collect statistics of the entropy. The theoretical results are compared with the extremal optimization results.

关键词： Cavity method Disordered systems (theory) Entropy message-passing algorithms Transportation networks

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：