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

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第11期52卷 4753-4766页

作者： Moallemi, Ciamac C. Van Roy, Benjamin Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than painvise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge.

关键词： belief propagation distributed averaging distributed consensus distributed signal processing Gaussian Markov random fields max-product algorithm message-passing algorithms min-sum algorithm sum-product algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence of Min-Sum message-passing for Convex Optimization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第4期56卷 2041-2050页

作者： Moallemi, Ciamac C. Van Roy, Benjamin Columbia Univ Grad Sch Business New York NY 10027 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

We establish that the min-sum message-passing algorithm and its asynchronous variants converge for a large class of unconstrained convex optimization problems, generalizing existing results for pairwise quadratic optimization problems. The main sufficient condition is that of scaled diagonal dominance. This condition is similar to known sufficient conditions for asynchronous convergence of other decentralized optimization algorithms, such as coordinate descent and gradient descent.

关键词： message-passing algorithms decentralized optimization convex optimization

来源：评论

学校读者我要写书评

暂无评论

Distributed Pilot Decontamination Enhancing Link Reliability in Industrial IoT Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2024年第22期11卷 37071-37083页

作者： Kim, Hong Ki Kim, Sunho Lee, Yoon Ku Lee, Sang Hyun Korea Univ Sch Elect Engn Seoul 02841 South Korea

Industrial Internet of Things networks require large-volume data delivery across interdependent mission-critical components. This imposes stringent ultrareliable low-latency communication requirements. In this regard, cell-free network architecture has risen as a compelling solution to shorten distances between devices and access points (APs). In cell-free networks, APs simultaneously serve devices with shared time-frequency resources, utilizing channel state information acquired via pilot signals from devices. However, a limited number of orthogonal pilot sequences entails the pilot reuse across multiple links. This results in the interference among pilot signals, which, in turn, degrades the overall link utilities. A skillful pilot assignment (PA) mitigates such interference, while the combinatorial nature of handling pilot-sharing groups limits the development of an efficient protocol. This work develops a survey propagation-inspired distributed PA framework, originating from statistical physics to address the equilibrium among particle interactions, which successfully interprets the consensus among pilot-sharing groups in the PA task. This facilitates distributed and efficient addressing of complex solution spaces, leading to computation-efficient solutions.

关键词： Industrial Internet of Things Channel estimation Interference Contamination Coherence Uplink Task analysis Cell-free massive multiple-input-multiple-output (MIMO) Industrial Internet of Things (IIoT) message-passing algorithms pilot assignment (PA) survey propagation (SP)

来源：评论

学校读者我要写书评

暂无评论

Resource Allocation via message passing

引用

INFORMS JOURNAL ON COMPUTING 2011年第2期23卷 205-219页

作者： Moallemi, Ciamac C. Van Roy, Benjamin Columbia Univ Grad Sch Business New York NY 10027 USA Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We propose a message-passing paradigm for resource allocation problems. This serves to connect ideas from the message-passing literature, which has primarily grown out of the communications, statistical physics, and artificial intelligence communities, with a problem central to operations research. This also provides a new framework for decentralized management that generalizes price-based systems by allowing incentives to vary across activities and consumption levels. We demonstrate that message-based incentives, which are characterized by a new equilibrium concept, lead to system-optimal behavior for convex resource allocation problems yet yield allocations superior to those from price-based incentives for nonconvex problems. We describe a distributed and asynchronous message-passing algorithm for computing equilibrium messages and allocations, and we demonstrate its merits in the context of a network resource allocation problem.

关键词： message-passing algorithms min-sum algorithm resource allocation convex optimization decentralized optimization

来源：评论

学校读者我要写书评

暂无评论

Geographic gossip: Efficient averaging for sensor networks

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2008年第3期56卷 1205-1216页

作者： Dimakis, Alexandros D. G. Sarwate, Anand D. Wainwright, Martin J. Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA

Gossip algorithms for distributed computation are attractive due to their simplicity, distributed nature, and robustness in noisy and uncertain environments. However, using standard gossip algorithms can lead to a significant waste of energy by repeatedly recirculating redundant information. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is related to the slow mixing times of random walks on the communication graph. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing geographic routing combined with a simple resampling method, we demonstrate substantial gains over previously proposed gossip protocols. For regular graphs such as the ring or grid, our algorithm improves standard gossip by factors of n and root n, respectively. For the more challenging case of random geometric graphs, our algorithm computes the true average to accuracy E using O((n(1.5)/root log n) log epsilon(-1)) radio transmissions, which yields a root n/log n factor improvement over standard gossip algorithms. We illustrate these theoretical results with experimental comparisons between our algorithm and standard methods as applied to various classes of random fields.

关键词： aggregation problems consensus problems distributed signal processing gossip algorithms message-passing algorithms random geometric graphs sensor networks

来源：评论

学校读者我要写书评

暂无评论

Exchange of Limits: Why Iterative Decoding Works

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第4期57卷 2169-2187页

作者： Korada, Satish Babu Urbanke, Ruediger L. Ecole Polytech Fed Lausanne Sch Comp & Commun Sci CH-1015 Lausanne Switzerland

We consider communication over binary-input memoryless output-symmetric channels using low-density parity-check codes and message-passing decoding. The asymptotic (in the length) performance of such a combination for a fixed number of iterations is given by density evolution. Letting the number of iterations tend to infinity we get the density evolution (DE) threshold, the largest channel parameter so that the bit error probability tends to zero as a function of the iterations. In practice, we often work with short codes and perform a large number of iterations. It is, therefore, interesting to consider what happens if in the standard analysis we exchange the order in which the blocklength and the number of iterations diverge to infinity. In particular, we can ask whether both limits give the same threshold. Although empirical observations strongly suggest that the exchange of limits is valid for all channel parameters, we limit our discussion to channel parameters below the DE threshold. Specifically, we show that as long as the message reliabilities are bounded and other technical conditions are met, the bit error probability vanishes up to a nontrivial threshold regardless of how the limit is taken. This threshold is equal to the DE threshold when the minimum degree of the variable nodes is at least five and strictly less than the DE threshold for smaller degrees.

关键词： Density evolution error probability expansion LDPC message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

MAP estimation via agreement on trees: message-passing and linear programming

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2005年第11期51卷 3697-3717页

作者： Wainwright, MJ Jaakkola, TS Willsky, AS Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA Univ Calif Berkeley Dept Stat Berkeley CA 94720 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined-on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-related linear program (LP), which is derived from the Lagrangian dual of the upper bounds;and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.

关键词： approximate inference integer programming iterative decoding linear programming (LP) relaxation Markov random fields marginal polytope maximum a posteriori probability (MAP) estimation max-product algorithm message-passing algorithms min-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

Modeling and Mitigating Errors in Belief Propagation for Distributed Detection

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 2021年第5期69卷 3286-3297页

作者： Abdi, Younes Ristaniemi, Tapani Univ Jyvaskyla Fac Informat Technol Jyvaskyla 40014 Finland

We study the behavior of the belief-propagation (BP) algorithm affected by erroneous data exchange in a wireless sensor network (WSN). The WSN conducts a distributed multidimensional hypothesis test over binary random variables. The joint statistical behavior of the sensor observations is modeled by a Markov random field whose parameters are used to build the BP messages exchanged between the sensing nodes. Through linearization of the BP message-update rule, we analyze the behavior of the resulting erroneous decision variables and derive closed-form relationships that describe the impact of stochastic errors on the performance of the BP algorithm. We then develop a decentralized distributed optimization framework to enhance the system performance by mitigating the impact of errors via a distributed linear data-fusion scheme. Finally, we compare the results of the proposed analysis with the existing works and visualize, via computer simulations, the performance gain obtained by the proposed optimization.

关键词： Optimization Wireless sensor networks Sensors Signal processing algorithms Random variables Light rail systems Hardware Distributed systems cooperative communications likelihood-ratio test communication errors computation errors blind signal processing message-passing algorithms linear data-fusion factor graphs

来源：评论

学校读者我要写书评

暂无评论

Cayley Trees and Bethe Lattices: A concise analysis for mathematicians and physicists

引用

PHYSICA A-STATISTICAL MECHANICS AND ITS APPLICATIONS 2012年第12期391卷 3417-3423页

作者： Ostilli, M. Int Islamic Univ Malaysia Dept Computat & Theoret Sci Kuantan 25710 Pahang Malaysia INFM CNR SMC Stat Mech & Complex Ctr SMC Rome Italy

We review critically the concepts and the applications of Cayley Trees and Bethe Lattices in statistical mechanics in a tentative effort to remove widespread misuse of these simple, but yet important - and different - ideal graphs. We illustrate, in particular, two rigorous techniques to deal with Bethe Lattices, based respectively on self-similarity and on the Kolmogorov consistency theorem, linking the latter with the Cavity and Belief Propagation methods, more known to the physics community. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Rigorous results in statistical mechanics Solvable lattice models Exact results message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Max-product for maximum weight matching: Convergence, correctness, and LP duality

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第3期54卷 1241-1251页

作者： Bayati, Mobsen Shah, Devavrat Sharma, Mayank Microsoft Res Redmond WA 98052 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA

Max-product "belief propagation" (BP) is an iterative, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding and combinatorial optimization, which involve graphs with many cycles, theoretical results about both the correctness and convergence of the algorithm are known in only a few cases (see Section I for references). In this paper, we will prove the correctness and convergence of max-product for finding the maximum weight matching (MWM) in bipartite graphs. Even though the underlying graph of the MWM problem has many cycles, somewhat surprisingly we show that the max-product algorithm converges to the correct MWM as long as the MWM is unique. We provide a bound on the number of iterations required and show that for a graph of size n, the computational cost of the algorithm scales as O(n(3)), which is the same as the computational cost of the best known algorithms for finding the MWM. We also provide an interesting relation between the dynamics of the max-product algorithm and the auction algorithm, which is a well-known distributed algorithm for solving the MWM problem.

关键词： auction algorithm belief propagation (BP) distributed optimization linear programming Markov random fields maximum weight matching (MWM) max-product algorithm message-passing algorithms min-sum algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：