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

The planted matching problem: Phase transitions and exact results

Annals of Applied Probability 2021年第6期31卷 2663-2720页

作者： Moharrami, Mehrdad Moore, Cristopher Xu, Jiaming Coordinated Science Lab University of Illinois at Urbana-Champaign United States Santa Fe Institute United States The Fuqua School of Business Duke University United States

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs Kn,n. For some unknown perfect matching M∗, the weight of an edge is drawn from one distribution P if e ∈ M∗ and an... 详细信息

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs K_n,n. For some unknown perfect matching M^∗, the weight of an edge is drawn from one distribution P if e ∈ M^∗ and another distribution Q if e ∈/ M^∗. Our goal is to infer M^∗, exactly or approximately, from the edge weights. In this paper we take P = exp(λ) and Q = exp(1/n), in which case the maximum-likelihood estimator of M^∗ is the minimum-weight matching M_min. We obtain precise results on the overlap between M^∗ and M_min, that is, the fraction of edges they have in common. For λ ≥ 4 we have almost perfect recovery, with overlap 1 − o(1) with high probability. For λ < 4 the expected overlap is an explicit function α(λ) < 1: we compute it by generalizing Aldous’ celebrated proof of the ζ(2) conjecture for the unplanted model, using local weak convergence to relate K_n,n to a type of weighted infinite tree, and then deriving a system of differential equations from a message-passing algorithm on this tree. © Institute of Mathematical Statistics, 2021

关键词： Combinatorial optimization Local weak convergence message-passing algorithms Phase transitions Planted problems Random graphs

来源：评论

学校读者我要写书评

暂无评论

Deep Expectation-Consistent Approximation for Phase Retrieval 57

Deep Expectation-Consistent Approximation for Phase Retrieva...

引用

57th Asilomar Conference on Signals, Systems and Computers

作者： Shastri, Saurav K. Ahmad, Rizwan Schniter, Philip Ohio State Univ Dept ECE Columbus OH 43210 USA Ohio State Univ Dept BME Columbus OH 43210 USA

ISBN: (纸本)9798350325744

The expectation consistent (EC) approximation framework is a state-of-the-art approach for solving (generalized) linear inverse problems with high-dimensional random forward operators and i.i.d. signal priors. In image inverse problems, however, both the forward operator and image pixels are structured, which plagues traditional EC implementations. In this work, we propose a novel incarnation of EC that exploits deep neural networks to handle structured operators and signals. For phase-retrieval, we propose a simplified variant called "deepECpr" that reduces to iterative denoising. In experiments recovering natural images from phaseless, shot-noise corrupted, coded-diffraction-pattern measurements, we observe accuracy surpassing the state-of-the-art prDeep (Metzler et al., 2018) and Diffusion Posterior Sampling (Chung et al., 2023) approaches with two-orders-of-magnitude complexity reduction.

关键词： Expectation-Consistent Approximation Generalized Linear Model Phase Retrieval message-passing algorithms Plug-and-Play algorithms

来源：评论

学校读者我要写书评

暂无评论

A low-complexity universal scheme for rate-constrained distributed regression using a wireless sensor network

A low-complexity universal scheme for rate-constrained distr...

引用

33rd IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Fernandes, Avon Loy Raginsky, Maxim Coleman, Todd Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Duke Univ Dept Elect & Comp Engn Durham NC 27706 USA

ISBN: (纸本)9781424414833

We propose a scheme for rate-constrained distributed nonparametric regression using a wireless sensor network. The scheme is universal across a wide range of sensor noise models, including unbounded and nonadditive noise;it has low complexity, requiring simple operations such as uniform scalar quantization with dither and message passing between neighboring nodes in the network;and attains minimax optimality for regression functions in common smoothness classes. We present theoretical results on the trade-off between the compression rate and the MSE and demonstrate empirical performance of the scheme using simulations.

关键词： sensor networks nonparametric estimation rate-distortion theory message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Spatially-Coupled Codes for Write-Once Memories 53

Spatially-Coupled Codes for Write-Once Memories

引用

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

来源：评论

学校读者我要写书评

暂无评论

Spectral inference methods on sparse graphs: theory and applications

Spectral inference methods on sparse graphs: theory and appl...

引用

作者： Alaa Saade Ecole Normale Superieure

学位级别：博士

In an era of unprecedented deluge of (mostly unstructured) data, graphs are proving more and more useful, across the sciences, as a flexible abstraction to capture complex relationships between com- plex objects. One of the main challenges arising in the study of such networks is the inference of macroscopic, large-scale properties af- fecting a large number of objects, based solely on the microscopic in- teractions between their elementary constituents. Statistical physics, precisely created to recover the macroscopic laws of thermodynamics from an idealized model of interacting particles, provides significant insight to tackle such complex networks. In this dissertation, we use methods derived from the statistical physics of disordered systems to design and study new algorithms for inference on graphs. Our focus is on spectral methods, based on certain eigenvectors of carefully chosen matrices, and sparse graphs, containing only a small amount of information. We develop an origi- nal theory of spectral inference based on a relaxation of various mean- field free energy optimizations. Our approach is therefore fully prob- abilistic, and contrasts with more traditional motivations based on the optimization of a cost function. We illustrate the efficiency of our approach on various problems, including community detection, randomized similarity-based clustering, and matrix completion.

关键词： non-backtracking operator Bethe Hessian spectral methods community detection spectral clustering matrix completion graphical models Bayesian inference mean-field approximations disordered systems belief propagation message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Scaling Probabilistic Inference Through message Contraction Optimization

Scaling Probabilistic Inference Through Message Contraction ...

引用

2023 Congress in Computer Science, Computer Engineering, and Applied Computing, CSCE 2023

作者： Villescas, Martin Roa Liu, Jin-Guo Wijnings, Patrick W.A. Stuijk, Sander Corporaal, Henk Eindhoven University of Technology Eindhoven Netherlands Guangzhou China

ISBN: (纸本)9798350327595

Within the realm of probabilistic graphical models, message-passing algorithms offer a powerful framework for efficient inference. When dealing with discrete variables, these algorithms essentially amount to the addition and multiplication of multidimensional arrays with labeled dimensions, known as factors. The complexity of these algorithms is dictated by the highest-dimensional factor appearing across all computations, a metric known as the induced tree width. Although state-of-the-art methods aimed at minimizing this metric have expanded the feasi-bility of exact inference, many real-world problems continue to be intractable. In this paper, we introduce a novel method for adding and multiplying factors that results in a substantial improvement in the inference performance, especially for increasingly complex models. Our approach aligns well with existing state-of-the-art methods designed to minimize the induced tree width, thereby further expanding the tractability spectrum of exact inference for more complex models. To demonstrate the efficacy of our method, we conduct a comparative evaluation against two other open-source libraries for probabilistic inference. Our approach exhibits an average speedup of 23 times for the UAI 2014 benchmark set. For the 10 most complex problems, the average speedup increases to 64 times, demonstrating its scalability. © 2023 IEEE.

关键词： Bayesian networks message-passing algorithms probabilistic graphical models probabilistic inference

来源：评论

学校读者我要写书评

暂无评论

On the number of circuits in random graphs

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2006年第6期2006卷 P06019-P06019页

作者： Marinari, Enzo Semerjian, Guilhem Univ Roma La Sapienza Dipartimento Fis I-00185 Rome Italy Univ Roma La Sapienza Ist Nazl Fis Nucl I-00185 Rome Italy Univ Roma La Sapienza CNR I-00185 Rome Italy

We apply in this paper (non-rigorous) statistical mechanics methods to the problem of counting long circuits in graphs. The outcomes of this approach have two complementary flavours. On the algorithmic side, we propose an approximate counting procedure, valid in principle for a large class of graphs. On a more theoretical side, we study the typical number of long circuits in random graph ensembles, reproducing rigorously known results and stating new conjectures.

关键词： cavity and replica method message-passing algorithms random graphs networks

来源：评论

学校读者我要写书评

暂无评论

Model selection for degree-corrected block models

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2014年第5期2014卷 P05007-P05007页

作者： Yan, Xiaoran Shalizi, Cosma Jensen, Jacob E. Krzakala, Florent Moore, Cristopher Zdeborova, Lenka Zhang, Pan Zhu, Yaojia Univ So Calif Inst Informat Sci Marina Del Rey CA 90292 USA Carnegie Mellon Univ Dept Stat Pittsburgh PA 15213 USA Stanford Univ Dept Comp Sci Stanford CA 94305 USA Ecole Normale Super F-75005 Paris France Santa Fe Inst Santa Fe NM 87501 USA CEA Saclay Inst Phys Theor F-91190 Gif Sur Yvette France CNRS URA 2306 F-91190 Gif Sur Yvette France Microsoft Bellevue WA 98004 USA

The proliferation of models for networks raises challenging problems of model selection: the data are sparse and globally dependent, and models are typically high-dimensional and have large numbers of latent variables. Together, these issues mean that the usual model-selection criteria do not work properly for networks. We illustrate these challenges, and show one way to resolve them, by considering the key network-analysis problem of dividing a graph into communities or blocks of nodes with homogeneous patterns of links to the rest of the network. The standard tool for undertaking this is the stochastic block model, under which the probability of a link between two nodes is a function solely of the blocks to which they belong. This imposes a homogeneous degree distribution within each block;this can be unrealistic, so degree-corrected block models add a parameter for each node, modulating its overall degree. The choice between ordinary and degree-corrected block models matters because they make very different inferences about communities. We present the first principled and tractable approach to model selection between standard and degree-corrected block models, based on new large-graph asymptotics for the distribution of log-likelihood ratios under the stochastic block model, finding substantial departures from classical results for sparse graphs. We also develop linear-time approximations for log-likelihoods under both the stochastic block model and the degree-corrected model, using belief propagation. Applications to simulated and real networks show excellent agreement with our approximations. Our results thus both solve the practical problem of deciding on degree correction and point to a general approach to model selection in network analysis.

关键词： message-passing algorithms random graphs networks clustering techniques statistical inference

来源：评论

学校读者我要写书评

暂无评论

Statistical mechanics of complex neural systems and high dimensional data

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2013年第3期2013卷 P03014-P03014页

作者： Advani, Madhu Lahiri, Subhaneil Ganguli, Surya Stanford Univ Dept Appl Phys Stanford CA 94305 USA

Recent experimental advances in neuroscience have opened new vistas into the immense complexity of neuronal networks. This proliferation of data challenges us on two parallel fronts. First, how can we form adequate theoretical frameworks for understanding how dynamical network processes cooperate across widely disparate spatiotemporal scales to solve important computational problems? Second, how can we extract meaningful models of neuronal systems from high dimensional datasets? To aid in these challenges, we give a pedagogical review of a collection of ideas and theoretical methods arising at the intersection of statistical physics, computer science and neurobiology. We introduce the interrelated replica and cavity methods, which originated in statistical physics as powerful ways to quantitatively analyze large highly heterogeneous systems of many interacting degrees of freedom. We also introduce the closely related notion of message passing in graphical models, which originated in computer science as a distributed algorithm capable of solving large inference and optimization problems involving many coupled variables. We then show how both the statistical physics and computer science perspectives can be applied in a wide diversity of contexts to problems arising in theoretical neuroscience and data analysis. Along the way we discuss spin glasses, learning theory, illusions of structure in noise, random matrices, dimensionality reduction and compressed sensing, all within the unified formalism of the replica method. Moreover, we review recent conceptual connections between message passing in graphical models, and neural computation and learning. Overall, these ideas illustrate how statistical physics and computer science might provide a lens through which we can uncover emergent computational functions buried deep within the dynamical complexities of neuronal networks.

关键词： cavity and replica method spin glasses (theory) message-passing algorithms computational neuroscience

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：