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

Optimization of decentralized random field estimation networks under communication constraints through Monte Carlo methods

引用

DIGITAL SIGNAL PROCESSING 2014年 34卷 16-28页

作者： Uney, Murat Cetin, Mujdat Sabanci Univ Fac Engn & Nat Sci TR-34956 Istanbul Turkey

We propose a new methodology for designing decentralized random field estimation schemes that takes the tradeoff between the estimation accuracy and the cost of communications into account. We consider a sensor network in which nodes perform bandwidth limited two-way communications with other nodes located in a certain range. The in-network processing starts with each node measuring its local variable and sending messages to its immediate neighbors followed by evaluating its local estimation rule based on the received messages and measurements. Local rule design for this two-stage strategy can be cast as a constrained optimization problem with a Bayesian risk capturing the cost of transmissions and penalty for the estimation errors. A similar problem has been previously studied for decentralized detection. We adopt that framework for estimation, however, the corresponding optimization schemes involve integral operators that are impossible to evaluate exactly, in general. We employ an approximation framework using Monte Carlo methods and obtain an optimization procedure based on particle representations and approximate computations. The procedure operates in a message-passing fashion and generates results for any distributions if samples can be produced from, e.g., the marginals. We demonstrate graceful degradation of the estimation accuracy as communication becomes more costly. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Decentralized estimation Communication constrained inference Random fields message passing algorithms Monte Carlo methods Wireless sensor networks

来源：评论

学校读者我要写书评

暂无评论

Deterministic generative models for fast feature discovery

引用

DATA MINING AND KNOWLEDGE DISCOVERY 2001年第4期5卷 337-363页

作者： Westerdijk, M Barber, D Wiegerinck, W Univ Nijmegen Dept Med Phys & Biophys Nijmegen Netherlands

We propose a vector quantisation method which does not only provide a compact description of data vectors in terms codebook vectors, but also gives an explanation of codebook vectors as binary combinations of elementary features. This corresponds to the intuitive notion that, in the real world, patterns can be usefully thought of as being constructed by compositions from simpler features. The model can be understood as a generative model, in which the codebook vector is generated by a hidden binary state vector. The model is non-probabilistic in the sense that it assigns each data vector to a single codebook vector. We describe exact and approximate learning algorithms for learning deterministic feature representations. In contrast to probabilistic models, the deterministic approach allows the use of message propagation algorithms within the learning scheme. These are compared with standard mean-field/Gibbs sampling learning. We show that Generative Vector Quantisation gives a good performance in large scale real world tasks like image compression and handwritten digit analysis with up to 400 data dimensions.

关键词： vector quantisation feature discovery generative models mean-field methods message passing algorithms handwritten digits analysis image compression

来源：评论

学校读者我要写书评

暂无评论

Synchronization over Z(2) and community detection in signed multiplex networks with constraints

引用

JOURNAL OF COMPLEX NETWORKS 2015年第3期3卷 469-506页

作者： Cucuringu, Mihai Princeton Univ PACM Fine HallWashington Rd Princeton NJ 08544 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90095 USA

Finding group elements from noisy measurements of their pairwise ratios is also known as the group synchronization problem, first introduced in the context of the group SO(2) of planar rotations. The usefulness of synchronization over the group Z(2) has been demonstrated in recent algorithms for localization of sensor networks and three-dimensional structuring of molecules. In this paper, we focus on synchronization over Z(2), and consider the problem of identifying communities in a multiplex network when the interaction between the nodes is described by a signed (and possibly weighted) measure of similarity, and when the multiplex network has a natural partition into two communities, of possibly different sizes. In the setting where one has the additional information that certain subsets of nodes represent the same (unknown) group element, we consider and compare several algorithms for synchronization over Z(2), based on spectral and SDP relaxations, and message passing algorithms. In other words, all nodes within such a subset represent the same unknown group element, and one has available noisy pairwise measurements between pairs of nodes that belong to different non-overlapping subsets. Following a recent analysis of the eigenvector method for synchronization over SO(2), we analyse the robustness to noise of the eigenvector method for synchronization over Z(2), when the underlying graph of pairwise measurements is the Erdos-Renyi random graph, using results from the random matrix theory literature on the largest eigenvalue of rank-1 deformation of large random matrices. We also propose a message passing synchronization algorithm, inspired by the standard belief propagation algorithm, that outperforms the existing eigenvector synchronization algorithm only for certain classes of graphs and noise models, and enjoys the flexibility of incorporating additional constraints that may not be easily accommodated by any of the other spectral or SDP-based methods. We apply

关键词： eigenvectors group synchronization semidefinite programming multiplex networks spectral algorithms random matrix theory bipartite networks message passing algorithms voting networks

来源：评论

学校读者我要写书评

暂无评论

Phase Transitions and Sample Complexity in Bayes-Optimal Matrix Factorization

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第7期62卷 4228-4265页

作者： Kabashima, Yoshiyuki Krzakala, Florent Mezard, Marc Sakata, Ayaka Zdeborova, Lenka Tokyo Inst Technol Dept Math & Comp Sci Yokohama Kanagawa 2268502 Japan PSL Res Univ Ecole Normale Super Lab Phys Stat F-75005 Paris France Sorbonne Univ Univ Paris 06 F-75005 Paris France PSL Res Univ Ecole Normale Super Dept Phys F-75005 Paris France Inst Stat Math Tachikawa Tokyo 1908562 Japan Grad Univ Adv Sci SOKENDAI Hayama Kanagawa 2400193 Japan Commissariat Energie Atom Saclay F-91191 Gif Sur Yvette France CNRS Inst Phys Theor F-91191 Gif Sur Yvette France

We analyze the matrix factorization problem. Given a noisy measurement of a product of two matrices, the problem is to estimate back the original matrices. It arises in many applications, such as dictionary learning, blind matrix calibration, sparse principal component analysis, blind source separation, low rank matrix completion, robust principal component analysis, or factor analysis. It is also important in machine learning: unsupervised representation learning can often be studied through matrix factorization. We use the tools of statistical mechanics-the cavity and replica methods-to analyze the achievability and computational tractability of the inference problems in the setting of Bayes-optimal inference, which amounts to assuming that the two matrices have random-independent elements generated from some known distribution, and this information is available to the inference algorithm. In this setting, we compute the minimal mean-squared-error achievable, in principle, in any computational time, and the error that can be achieved by an efficient approximate message passing algorithm. The computation is based on the asymptotic state-evolution analysis of the algorithm. The performance that our analysis predicts, both in terms of the achieved mean-squared-error and in terms of sample complexity, is extremely promising and motivating for a further development of the algorithm.

关键词： Statistical inference probabilistic matrix factorization dictionary learning message passing algorithms phase transitions sparse coding statistical physics computational barriers statistical and computational tradeoff

来源：评论

学校读者我要写书评

暂无评论

Counter Braids: A Novel Counter Architecture for Per-Flow Measurement 08

Counter Braids: A Novel Counter Architecture for Per-Flow Me...

引用

International Conference on Measurement and Modeling of Computer Systems

作者： Lu, Yi Montanari, Andrea Prabhakar, Balaji Dharmapurikar, Sarang Kabbani, Abdul Stanford Univ Dept EE Stanford CA 94305 USA Stanford Univ Dept EE & Stats Stanford CA 94305 USA Stanford Univ Dept EE & CS Stanford CA 94305 USA Nuova Syst Inc San Jose CA 95134 USA

ISBN: (纸本)9781605580050

Fine-grained network measurement requires routers and Switches to Update large arrays of counters at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount. of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at;link speed. This has made accurate per-flow measurement complex and expensive, and motivated approximate methods that detect and measure only the large flows. This paper revisits the problem of accurate per-flow measurement. We present a counter architecture, called Counter Braids, inspired by sparse random graph codes. In a nutshell, Counter Braids "compresses while counting". It solves the central problems (counter space and flow-to-counter association) of per-flow measurement by "braiding" a hierarchy of counters with random graphs. Braiding results in drastic space reduction by sharing counters among flows;and using random graphs generated on-the-fly with hash functions avoids the storage of flow-to-counter association. The Counter Braids architecture is optimal (albeit with a complex decoder) as it achieves the maximum compression rate asymptotically. For implementation, we present a low-complexity message passing decoding algorithm, which can recover flow sizes with essentially zero error. Evaluation on Internet traces demonstrates that almost all flow sizes are recovered exactly with only a few bits of counter space per flow.

关键词： Statistics Counters Network Measurement message passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimization of the Sherrington-Kirkpatrick Hamiltonian 60

Optimization of the Sherrington-Kirkpatrick Hamiltonian

引用

60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Montanari, Andrea Stanford Univ Dept Elect Engn Stanford CA 94305 USA Stanford Univ Dept Stat Stanford CA 94305 USA

ISBN: (纸本)9781728149523

Let A be a symmetric random matrix with independent and identically distributed Gaussian entries above the diagonal. We consider the problem of maximizing the quadratic form associated to A over binary vectors. In the language of statistical physics, this amounts to finding the ground state of the Sherrington-Kirkpatrick model of spin glasses. The asymptotic value of this optimization problem was characterized by Parisi via a celebrated variational principle, subsequently proved by Talagrand. We give an algorithm that, for any epsilon > 0, outputs a feasible solution whose value is at least (1 - epsilon) of the optimum, with probability converging to one as the dimension n of the matrix diverges. The algorithm's time complexity is of order n(2). It is a message-passing algorithm, but the specific structure of its update rules is new. As a side result, we prove that, at (low) non-zero temperature, the algorithm constructs approximate solutions of the Thouless-Anderson-Palmer equations.

关键词： Sherrington-Kirkpatrick spin glasses replica symmetry breaking message passing algorithms

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT MONTE CARLO APPROACH FOR OPTIMIZING DECENTRALIZED ESTIMATION NETWORKS CONSTRAINED BY UNDIRECTED TOPOLOGIES

AN EFFICIENT MONTE CARLO APPROACH FOR OPTIMIZING DECENTRALIZ...

引用

15th IEEE/SP Workshop on Statistical Signal Processing

作者： Uney, Murat Cetin, Muejdat Sabanci Univ Fac Engn & Nat Sci TR-34956 Istanbul Turkey

ISBN: (纸本)9781424427093

We consider a decentralized estimation network subject to communication constraints such that nearby platforms can communicate with each other through low capacity links rendering an undirected graph. After transmitting symbols based on its measurement, each node outputs an estimate for the random variable it is associated with as a function of both the measurement and incoming messages from neighbors. We are concerned with the underlying design problem and handle it through a Bayesian risk that penalizes the cost of communications as well as estimation errors, and constraining the feasible set of communication and estimation rules local to each node by the undirected communication graph. We adopt an iterative solution previously proposed for decentralized detection networks which can be carried out in a message passing fashion under certain conditions. For the estimation case, the integral operators involved do not yield closed form solutions in general so we utilize Monte Carlo methods. We achieve an iterative algorithm which yields an approximation to an optimal decentralized estimation strategy in a person by person sense subject to such constraints. In an example, we present a quantification of the trade-off between the estimation accuracy and cost of communications using the proposed algorithm.

关键词： Decentralized estimation communication constrained inference random-field estimation message passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Estimation of Gaussian Processes in Markov-Middleton Impulsive Noise 1

Estimation of Gaussian Processes in Markov-Middleton Impulsi...

引用

1st Global Power, Energy and Communication Conference (IEEE GPECOM)

作者： Mirbadin, Anoush Kiani, Ehsan Vannucci, Armando Colavolpe, Giulio Univ Parma Dept Engn & Architecture I-43124 Parma Italy

ISBN: (纸本)9781538680865

This work addresses the estimation of Gaussian signals over power line channels which are impaired by impulsive noise. The Markov-Middleton model is used to describe the memory and the multi-interferer nature of the impulsive noise. The estimation of Gaussian samples has been obtained by using a message passing algorithm. The message passing approach involves estimation of the channel states, approximation of the Gaussian mixtures and estimation of the correlated Gaussian samples. Correlation of channel states and correlation of input samples results in a loopy factor graph. To implement message passing on a loopy factor graph, we divide the graph in two main parts that exchange their messages by using a parallel iterative schedule. The lower part detects the channel states using the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm and the upper part estimates the signal samples using a Kalman smoother. The proposed approach extensively reduces the complexity of the overall estimation process.

关键词： power line communications impulsive noise Markov-Middleton model Bayesian estimation message passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Sparse Channel Estimation Based on BP-MF Improved Algorithm in SC-FDE System 3

Sparse Channel Estimation Based on BP-MF Improved Algorithm ...

引用

3rd IEEE International Conference on Computer and Communications (ICCC)

作者： Yong, Liuliang Wang, Zhongyong Guo, Qiuge Zhengzhou Univ ZZU Sch Informat Engn Zhengzhou Henan Peoples R China

ISBN: (纸本)9781509063529

A low complexity sparse Bayesian channel estimation algorithm has been proposed for SC-FDE receiver. The algorithm of combined belief propagation with mean field (BP-MF) applied into the Bayesian Hierarchical prior Model is obtained at first, and then use the algorithm of an generalized approximate message passing (GAMP) by approximating the algorithm of BP. Then the channel estimated values that are obtained in first iteration are sorted from big to small, and these small values are deleted to further reduce the complexity of computational. Finally, the MF method is applied to the Frequency Domain Equalization. The experiment results demonstrate that the proposed method has nearly the same performance compared to the MF algorithm in estimation precision of the channel and Bit Error Rate (BER), and it also has much less computational complexity.

关键词： bayesian hierarchical model SC-FDE message passing algorithms sparse channel channel estimation

来源：评论

学校读者我要写书评

暂无评论

Sparse Channel Estimation Based on Improved BP-MF Algorithm in SC-FDE System

Sparse Channel Estimation Based on Improved BP-MF Algorithm ...

引用

International Conference on Computer Systems, Electronics and Control (ICCSEC)

作者： Wang, Chao Li, Zhi-yuan Huang, Lei China Shipbldg Ind Corp Res Inst 713 Zhengzhou Henan Peoples R China

ISBN: (纸本)9781538635735

A low complexity sparse Bayesian channel estimation algorithm was proposed for SC-FDE receiver. The proposed algorithm firstly applies the combined belief propagation and mean field (BP-MF) algorithm to the Bayesian Hierarchical Prior Model and obtained by approximating some BP messages using generalized approximate message passing (GAMP) algorithm. Then we put the channel estimated values that are acquired from the first iteration in such an order-from big to small and further reduce the computational complexity, we eliminate some small value to achieve this goal. Finally, we applied the MF method to the Frequency Domain Equalization. Numerical results demonstrate that the proposed method has nearly the same performance as compared to the MF algorithm in estimation precision of the channel and Bit Error Rate (BER) while it has much less computational complexity as compared to the MF algorithm.

关键词： Bayesian hierarchical model SC-FDE message passing algorithms sparse channel channel estimation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：