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

IEEE Global Communications Conference (GLOBECOM)

作者： Xia, Tian Wu, Hsiao-Chun Huang, Scott C-H. Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA Natl Tsing Hua Univ Dept Elect Engn Taipei Taiwan

ISBN: (纸本)9781479913534

Nonbinary low-density parity-check (LDPC) codes can lead to excellent error performance while the codewords are of short or moderate length. However, the high decoding complexity of non binary LDPC codes inevitably depreciates their practical values. The computational bottleneck arises from the check node processing in the iterative message passing (MP) algorithms which terminate when either all parity checks are satisfied or the maximum iteration number is reached. We have observed that for undecodable blocks, the MP algorithms always run up to the maximum iteration limit and therefore cannot generate the correct codeword. Thus, it would be better to terminate the algorithms early so as to save the unnecessary computational time and reduce the extra power consumption when undecodable blocks are experienced. In this paper, we propose a new T-tolerance stopping criterion for LDPC decoders by exploiting the fact that the total a posteriori probability (APP) should increase as the iteration number grows. Simulation results demonstrate that our proposed new T-tolerance criterion can greatly reduce the average iteration number (complexity) while restricting the decoding performance degradation within 0.1 dB in low bit-energy-to-noise ratio scenarios.

关键词： Iterative decoding nonbinary low-density parity-check (LDPC) codes message passing algorithms stopping criterion

来源：评论

学校读者我要写书评

暂无评论

A Novel Adaptive Iterative Detection Technique for Joint Estimation and Detection

A Novel Adaptive Iterative Detection Technique for Joint Est...

引用

21st Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC)

作者： Oguz, Onur Herzet, Cedric Vandendorpe, Luc Catholic Univ Louvain Commun & Remote Sensing Lab 2 Pl Levant B-1348 Louvain Belgium INRIA CTR Rene Bretag Atlan F-35000 Beaulieu France

ISBN: (纸本)9781424480166

Reliability of the communication systems depends hugely on the receiver performance where the synchronization and detection tasks need to be performed. Classically these two tasks are attended separately resulting in simple yet non-optimal receivers. During the last decade, a family of iterative receivers has been introduced to approximate the optimal solution to joint estimation and detection problem by means of the turbo principle. With the help of graph theory and the belief propagation framework these receiver structures are unified and soft information driven schemes emerged, leading to more reliable detection. The essence of these schemes lays in factorization of a global function whose marginal corresponds to the objective function and obtained via simple message passing algorithms. On the other hand, as far as our knowledge, all of the proposed structures pursue a specific factorization while devising their respective schemes. In this work utilizing a different factorization, we introduce a novel iterative receiver for joint equalization/detection problem. With the aid of Variational Bayesian approximation we show that the complexity can be reduced without sacrificing the error performance drastically.

关键词： Bayes methods adaptive iterative detection technique belief propagation communication system reliability equalisers equalization factorization graph theory graph theory iterative methods iterative receiver message passing message passing algorithms radio receivers synchronisation synchronization telecommunication network reliability turbo principle variational Bayesian approximation

来源：评论

学校读者我要写书评

暂无评论

GridPick: A High Density Puzzle Based Order Picking System with Decentralized Control

GridPick: A High Density Puzzle Based Order Picking System w...

引用

作者： Uludağ, Onur Auburn University

学位级别：Ph.D., Doctor of Philosophy

We develop a novel semi-automated order picking system called GridPick that enables high levels of throughput, space usage, and flexibility. The system uses unit sized conveyor modules in grid architecture to bring requested items to and away from the pick face dynamically and as needed to fulfill orders to the system. GridPick uses a message passing and negotiation algorithm with decentralized control rules, which is a relatively unexplored area in conveyor-based material handling systems. In the second part of the dissertation, we modify the GridPick system to allow picking from two sides of the grid. This enhancement allows higher throughput and an improved use of space when compared with single sided, traditional systems. To investigate structural properties of the system, we present a Petri Nets model. We use the model to verify deadlock conditions for the single-sided version of GridPick. We show that the system is deadlock free for up to a 4X4 grid and conjecture that the general case is also true.

关键词： Puzzle based storage systems Grid based intralogistics Decentralized control Semi automated order picking message passing algorithms Flexible and modular logistics solutions Multi agent modeling with petri nets Verification of structural properties with petri nets Deadlock free analysis

来源：评论

学校读者我要写书评

暂无评论

(Dis)assortative partitions on random regular graphs

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2022年第39期55卷 395004-395004页

作者： Behrens, Freya Arpino, Gabriel Kivva, Yaroslav Zdeborova, Lenka Ecole Polytech Fed Lausanne EPFL Stat Phys Computat Lab Lausanne Switzerland Univ Cambridge Dept Engn Invenia Labs Cambridge England Ecole Polytech Fed Lausanne EPFL Business Analyt Lab Lausanne Switzerland

We study the problem of assortative and disassortative partitions on random dregular graphs. Nodes in the graph are partitioned into two non-empty groups. In the assortative partition every node requires at least H of their neighbors to be in their own group. In the disassortative partition they require less than H neighbors to be in their own group. Using the cavity method based on analysis of the belief propagation algorithm we establish for which combinations of parameters (d, H) these partitions exist with high probability and for which they do not. For H > [d/2] we establish that the structure of solutions to the assortative partition problems corresponds to the so-called frozen-one-step replica symmetry breaking. This entails a conjecture of algorithmic hardness of finding these partitions efficiently. For H <= [d/2] we argue that the assortative partition problem is algorithmically easy on average for all d. Further we provide arguments about asymptotic equivalence between the assortative partition problem and the disassortative one, going through a close relation to the problem of single-spin-flip-stable states in spin glasses. In the context of spin glasses, our results on algorithmic hardness imply a conjecture that gapped single spin flip stable states are hard to find which may be a universal reason behind the observation that physical dynamics in glassy systems display convergence to marginal stability.

关键词： random graphs phase transitions partitions cavity method disordered systems message passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithmic Pure States for the Negative Spherical Perceptron

引用

JOURNAL OF STATISTICAL PHYSICS 2022年第2期189卷 27-27页

作者： El Alaoui, Ahmed Sellke, Mark Cornell Univ Dept Stat & Data Sci Ithaca NY 14850 USA Stanford Univ Artment Math Stanford CA 94305 USA

We consider the spherical perceptron with Gaussian disorder. This is the set S of points sigma is an element of R-N on the sphere of radius root N satisfying >= kappa root N for all 1 infinity, M/N -> alpha. T... 详细信息

We consider the spherical perceptron with Gaussian disorder. This is the set S of points sigma is an element of R-N on the sphere of radius root N satisfying < g(a), sigma > >= kappa root N for all 1 <= a <= M, where (g(a))(a=1)(M) are independent standard gaussian vectors and kappa is an element of R is fixed. Various characteristics of S such as its measure and the largest M for which it is non-empty, were computed heuristically in statistical physics in the asymptotic regime N -> infinity, M/N -> alpha. The case kappa < 0 is of special interest as S is conjectured to exhibit a hierarchical tree-like geometry known as full replica-symmetry breaking (FRSB) close to the satisfiability threshold alpha(SAT)(kappa), whose characteristics are captured by a Parisi variational principle akin to the one appearing in the Sherrington-Kirkpatrick model. In this paper we design an efficient algorithm which, given oracle access to the solution of the Parisi variational principle, exploits this conjectured FRSB structure for kappa < 0 and outputs a vector (sigma) over cap satisfying < g(a),(sigma) over cap > >= kappa root N for all 1 <= a <= M and lying on a sphere of non-trivial radius root(q) over barN, where (q) over bar is an element of (0,1) is the right-end of the support of the associated Parisi measure. We expect (sigma) over cap to be approximately the barycenter of a pure state of the spherical perceptron. Moreover we expect that (q) over bar -> 1 as alpha -> alpha(SAT)(kappa), so that < g(a),(sigma) over cap >/vertical bar(sigma) over cap vertical bar >= kappa-o(1) near criticality.

关键词： Spherical perceptron Constraint satisfaction message passing algorithms Full replica symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

Phase transitions in the q-coloring of random hypergraphs

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2017年第50期50卷

作者： Gabrie, Marylou Dani, Varsha Semerjian, Guilhem Zdeborova, Lenka PSL Res Univ Ecole Normale Super Lab Phys Stat Dept Phys 24 Rue Lhomond F-75005 Paris France Univ Paris Diderot Sorbonne Paris Cite 24 Rue Lhomond F-75005 Paris France Univ Paris 06 UPMC Sorbonne Univ 24 Rue Lhomond F-75005 Paris France CNRS 24 Rue Lhomond F-75005 Paris France PSL Res Univ Lab Phys Theor Dept Phys Ecole Normale Super 24 Rue Lhomond F-75005 Paris France Univ New Mexico Albuquerque NM 87131 USA Univ Paris Saclay Inst Phys Theor CNRS CEA F-91191 Gif Sur Yvette France

We study in this paper the structure of solutions in the random hypergraph coloring problem and the phase transitions they undergo when the density of constraints is varied. Hypergraph coloring is a constraint satisfaction problem where each constraint includes K variables that must be assigned one out of q colors in such a way that there are no monochromatic constraints, i.e. there are at least two distinct colors in the set of variables belonging to every constraint. This problem generalizes naturally coloring of random graphs (K = 2) and bicoloring of random hypergraphs (q = 2), both of which were extensively studied in past works. The study of random hypergraph coloring gives us access to a case where both the size q of the domain of the variables and the arity K of the constraints can be varied at will. Our work provides explicit values and predictions for a number of phase transitions that were discovered in other constraint satisfaction problems but never evaluated before in hypergraph coloring. Among other cases we revisit the hypergraph bicoloring problem (q = 2) where we find that for K = 3 and K = 4 the colorability threshold is not given by the one-step-replica-symmetry-breaking analysis as the latter is unstable towards more levels of replica symmetry breaking. We also unveil and discuss the coexistence of two different 1RSB solutions in the case of q = 2, K >= 4. Finally we present asymptotic expansions for the density of constraints at which various phase transitions occur, in the limit where q and/or K diverge.

关键词： phase transitions message passing algorithms random graphs cavity method disordered systems constraint satisfaction problem

来源：评论

学校读者我要写书评

暂无评论

Compressed sensing reconstruction using expectation propagation

引用

JOURNAL OF PHYSICS A-MATHEMATICAL AND THEORETICAL 2020年第18期53卷

作者： Braunstein, Alfredo Muntoni, Anna Paola Pagnani, Andrea Pieropan, Mirko Politccn Torino Dept Appl Sci & Technol DISAT Corso Duca Abruzzi 24 Turin Italy IRCCS Candiolo IIGM SP143Km 395 I-10060 Candiolo TO Italy Coll Carlo Alberto Via Real Coll 30 Moncalieri Italy Ist Nazl Fis Nucl Sez Torino Via P Giuria 1 Turin Italy Univ Paris Lab Phys Ecole Normale Super CNRS Univ PSLSorbonne UnivENS F-75005 Paris France Sorbonne Univ Lab Computat & Quantitat Biol Inst Biol Paris Seine CNRS F-75005 Paris France

Many interesting problems in fields ranging from telecommunications to computational biology can be formalized in terms of large underdetermined systems of linear equations with additional constraints or regularizers. One of the most studied, the compressed sensing problem, consists in finding the solution with the smallest number of non-zero components of a given system of linear equations y = Fw for known measurement vector and sensing matrix F. Here, we will address the compressed sensing problem within a Bayesian inference framework where the sparsity constraint is remapped into a singular prior distribution (called Spike-and-Slab or Bernoulli-Gauss). A solution to the problem is attempted through the computation of marginal distributions via expectation propagation, an iterative computational scheme originally developed in statistical physics. We will show that this strategy is more accurate for statistically correlated measurement matrices. For computational strategies based on the Bayesian framework such as variants of belief propagation, this is to be expected, as they implicitly rely on the hypothesis of statistical independence among the entries of the sensing matrix. Perhaps surprisingly, the method outperforms uniformly all the other state-of-the-art methods in our tests.

关键词： expectation propagation compressed sensing message passing algorithms Bayesian inference inverse problems

来源：评论

学校读者我要写书评

暂无评论

Gibbs states and the set of solutions of random constraint satisfaction problems

引用

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA 2007年第25期104卷 10318-10323页

作者： Krzakala, Florent Montanari, Andrea Ricci-Tersenghi, Federico Semerjian, Guilhem Zdeborova, Lenka Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA Ecole Super Phys & Chim Ind Ville Paris Lab Phys Chim Theor F-75005 Paris France Univ Paris 06 Ecole Normale Super Phys Theor Lab F-75005 Paris France Univ Roma La Sapienza Ist Nazl Fis Mat Dipartimento Fis I-00185 Rome Italy Univ Roma La Sapienza Ist Nazl Fis Mat CNR I-00185 Rome Italy Univ Paris 11 Lab Phys Theor & Modeles Stat F-91405 Orsay France

An instance of a random constraint satisfaction problem defines a random subset S (the set of solutions) of a large product space chi(N) (the set of assignments). We consider two prototypical problem ensembles (random k-satisfiability and q-coloring of random regular graphs) and study the uniform measure with support on S. As the number of constraints per variable increases, this measure first decomposes into an exponential number of pure states ("clusters") and subsequently condensates over the largest such states. Above the condensation point, the mass carried by the n largest states follows a Poisson-Dirichlet process. For typical large instances, the two transitions are sharp. We determine their precise location. Further, we provide a formal definition of each phase transition in terms of different notions of correlation between distinct variables in the problem. The degree of correlation naturally affects the performances of many search/sampling algorithms. Empirical evidence suggests that local Monte Carlo Markov chain strategies are effective up to the clustering phase transition and belief propagation up to the condensation point. Finally, refined message passing techniques (such as survey propagation) may also beat this threshold.

关键词： message passing algorithms phase transitions random graphs

来源：评论

学校读者我要写书评

暂无评论

A New Stopping Criterion for Fast Low-Density Parity-Check Decoders

A New Stopping Criterion for Fast Low-Density Parity-Check D...

引用

IEEE Global Communications Conference

作者： Tian Xia Hsiao-Chun Wu Scott C. H. Huang School of Electrical Engineering and Computer Science Louisiana State University Baton Rouge 70803 USA|c|

ISBN: (纸本)9781479913510

Nonbinary low-density parity-check (LDPC) codes can lead to excellent error performance while the codewords are of short or moderate length. However, the high decoding complexity of nonbinary LDPC codes inevitably depreciates their practical values. The computational bottleneck arises from the check node processing in the iterative message passing (MP) algorithms which terminate when either all parity checks are satisfied or the maximum iteration number is reached. We have observed that for undecodable blocks, the MP algorithms always run up to the maximum iteration limit and therefore cannot generate the correct codeword. Thus, it would be better to terminate the algorithms early so as to save the unnecessary computational time and reduce the extra power consumption when undecodable blocks are experienced. In this paper, we propose a new T-tolerance stopping criterion for LDPC decoders by exploiting the fact that the total a posteriori probability (APP) should increase as the iteration number grows. Simulation results demonstrate that our proposed new T-tolerance criterion can greatly reduce the average iteration number (complexity) while restricting the decoding performance degradation within 0.1 dB in low bit-energy-to-noise ratio scenarios.

关键词： Iterative decoding message passing algorithms nonbiliary low-density parity-check (LDPC) codes stopping criterion

来源：评论

学校读者我要写书评

暂无评论

Improving variational methods via pairwise linear response identities

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2017年第1期18卷

作者： Jack Raymond Federico Ricci-Tersenghi Dipartimento di Fisica La Sapienza University of Rome Rome Italy Dipartimento di Fisica INFN-Sezione di Roma1 and CNR-Nanotec La Sapienza University of Rome Rome Italy

Inference methods are often formulated as variational approximations: these approximations allow easy evaluation of statistics by marginalization or linear response, but these estimates can be inconsistent. We show that by introducing constraints on covariance, one can ensure consistency of linear response with the variational parameters, and in so doing inference of marginal probability distributions is improved. For the Bethe approximation and its generalizations, improvements are achieved with simple choices of the constraints. The approximations are presented as variational frameworks; iterative procedures related to message passing are provided for finding the minima.

关键词： graphical models linear response message passing algorithms statistical physics variational inference

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：