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

Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2007年第6期2007卷 L06001-L06001页

作者： Zhou, Jie Ma, Hui Zhou, Haijun Chinese Acad Sci Inst Theoret Phys Beijing 100080 Peoples R China

In a finite-connectivity spin glass at the zero-temperature limit, long-range correlations exist among the unfrozen vertices (whose spin values are non-fixed). Such long-range frustrations are partially removed through the first-step replica-symmetry-broken (1RSB) cavity theory, but residual long-range frustrations may still persist in this mean-field solution. By way of population dynamics, here we perform a perturbation-percolation analysis to calculate the magnitude of long-range frustrations in the 1RSB solution of a given spin-glass system. We study two well-studied model systems, the minimal vertex-cover problem and the maximal 2-satisfiability problem. This work points to a possible way of improving the zero-temperature 1RSB mean-field theory of spin glasses.

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

来源：评论

学校读者我要写书评

暂无评论

The cavity approach for Steiner trees packing problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2018年第12期2018卷 123401-123401页

作者： Braunsteinh, Alfredo Muntoni, Anna Paola Politecn Torino DISAT Corso Duca Abruzzi 24 Turin Italy Italian Inst Genet Med HuGeF Via Nizza 52 Turin Italy Coll Carlo Alberto Via Real Coll 1 Moncalieri Italy INFN Sez Torino Via P Giuria 1 I-10125 Turin Italy PSL Univ Sorbonne Univ Dept Phys ENS Lab Phys TheorEcole Normale SuperCNRS F-75005 Paris France

The belief propagation approximation, or cavity method, has been recently applied to several combinatorial optimization problems in its zero-temperature implementation, the max-sum algorithm. In particular, recent developments to solve the edge-disjoint paths problem and the prize-collecting Steiner tree problem on graphs have shown remarkable results for several classes of graphs and for benchmark instances. Here we propose a generalization of these techniques for two variants of the Steiner trees packing problem where multiple 'interacting' trees have to be sought within a given graph. Depending on the interaction among trees we distinguish the vertex-disjoint Steiner trees problem, where trees cannot share nodes, from the edge-disjoint Steiner trees problem, where edges cannot be shared by trees but nodes can be members of multiple trees. Several practical problems of huge interest in network design can be mapped into these two variants, for instance, the physical design of very large scale integration (VLSI) chips. The formalism described here relies on two components edge-variables that allows us to formulate a massage-passing algorithm for the V-DStP and two algorithms for the E-DStP differing in the scaling of the computational time with respect to some relevant parameters. We will show that through one of the two formalisms used for the edge-disjoint variant it is possible to map the max-sum update equations into a weighted maximum matching problem over proper bipartite graphs. We developed a heuristic procedure based on the max-sum equations that shows excellent performance in synthetic networks (in particular outperforming standard multi-step greedy procedures by large margins) and on large benchmark instances of VLSI for which the optimal solution is known, on which the algorithm found the optimum in two cases and the gap to optimality was never larger than 4%.

关键词： message-passing algorithms optimization over networks

来源：评论

学校读者我要写书评

暂无评论

Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2012年第8期2012卷 P08009-P08009页

作者： Krzakala, Florent Mezard, Marc Sausset, Francois Sun, Yifan Zdeborova, Lenka CNRS F-75005 Paris France ESPCI ParisTech UMR Gulliver 7083 F-75005 Paris France Univ Paris 11 F-91405 Orsay France CNRS UMR8626 LPTMS F-91405 Orsay France Beihang Univ LMIB Beijing 100191 Peoples R China Beihang Univ Sch Math & Syst Sci Beijing 100191 Peoples R China CEA Saclay IPhT Inst Phys Theor F-91191 Gif Sur Yvette France CENS Lab Leon Brillouin CNRS URA 2306 F-91191 Gif Sur Yvette France

Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make fewer measurements than were considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in Krzakala et al (2012 Phys. Rev. X 2 021005) a strategy that allows compressed sensing to be performed at acquisition rates approaching the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation maximization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distributions of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.

关键词： cavity and replica method message-passing algorithms error correcting codes statistical inference

来源：评论

学校读者我要写书评

暂无评论

The large deviations of the whitening process in random constraint satisfaction problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第5期2016卷 053401-053401页

作者： Braunstein, Alfredo Dall'Asta, Luca Semerjian, Guilhem Zdeborova, Lenka Politecn Torino Corso Duca Abruzzi 24 I-10129 Turin Italy Human Genet Fdn Via Nizza 52 I-10126 Turin Italy Collegio Carlo Alberto Via Real Collegio 30 I-10024 Moncalieri Italy Univ Paris 06 Sorbonne Univ PSL Res Univ LPTENSEcole Normale SuperCNRSUMR 8549 24 Rue Lhomond F-75005 Paris France Univ Paris Saclay CEA CNRS Inst Phys Theor F-91191 Gif Sur Yvette France

Random constraint satisfaction problems undergo several phase transitions as the ratio between the number of constraints and the number of variables is varied. When this ratio exceeds the satisfiability threshold no more solutions exist;the satisfiable phase, for less constrained problems, is itself divided in an unclustered regime and a clustered one. In the latter solutions are grouped in clusters of nearby solutions separated in configuration space from solutions of other clusters. In addition the rigidity transition signals the appearance of so-called frozen variables in typical solutions: beyond this threshold most solutions belong to clusters with an extensive number of variables taking the same values in all solutions of the cluster. In this paper we refine the description of this phenomenon by estimating the location of the freezing transition, corresponding to the disappearance of all unfrozen solutions (not only typical ones). We also unveil phase transitions for the existence and uniqueness of locked solutions, in which all variables are frozen. From a technical point of view we characterize atypical solutions with a number of frozen variables different from the typical value via a large deviation study of the dynamics of a stripping process (whitening) that unveils the frozen variables of a solution, building upon recent works on atypical trajectories of the bootstrap percolation dynamics. Our results also bear some relevance from an algorithmic perspective, previous numerical studies having shown that heuristic algorithms of various kinds usually output unfrozen solutions.

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

来源：评论

学校读者我要写书评

暂无评论

A message-passing approach to random constraint satisfaction problems with growing domains

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2011年第2期2011卷 P02019-P02019页

作者： Zhao, Chunyan Zhou, Haijun Zheng, Zhiming Xu, Ke Beihang Univ State Key Lab Software Dev Environm Beijing 100191 Peoples R China Beihang Univ Sch Math & Syst Sci Beijing 100191 Peoples R China Chinese Acad Sci Inst Theoret Phys Beijing 100190 Peoples R China Beihang Univ LMIB Beijing 100191 Peoples R China

message-passing algorithms based on belief propagation (BP) are implemented on a random constraint satisfaction problem (CSP) referred to as model RB, which is a prototype of hard random CSPs with growing domain size. In model RB, the number of candidate discrete values (the domain size) of each variable increases polynomially with the variable number N of the problem formula. Although the satisfiability threshold of model RB is exactly known, finding solutions for a single problem formula is quite challenging and attempts have been limited to cases of N similar to 10(2). In this paper, we propose two different kinds of message-passing algorithms guided by BP for this problem. Numerical simulations demonstrate that these algorithms allow us to find a solution for random formulas of model RB with constraint tightness slightly less than p(cr), the threshold value for the satisfiability phase transition. To evaluate the performance of these algorithms, we also provide a local search algorithm (random walk) as a comparison. Besides this, the simulated time dependence of the problem size N and the entropy of the variables for growing domain size are discussed.

关键词： classical phase transitions (theory) cavity and replica method disordered systems (theory) message-passing algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximate survey propagation for statistical inference

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第2期2019卷 023401-023401页

作者： Antenucci, Fabrizio Krzakala, Florent Urbani, Pierfrancesco Zdeborova, Lenka Univ Paris Saclay CNRS CEA Inst Phys Theor F-91191 Gif Sur Yvette France CNR NANOTEC Inst Nanotechnol Rome Unit Soft & Living Matter Lab Piazzale Aldo Moro 5 I-00185 Rome Italy CNRS Lab Phys Stat Paris France Sorbonnes Univ Paris France PSL Univ Ecole Normale Suprieure Paris France

Approximate message passing algorithm enjoyed considerable attention in the last decade. In this paper we introduce a variant of the AMP algorithm that takes into account glassy nature of the system under consideration. We coin this algorithm as the approximate survey propagation (ASP) and derive it for a class of low-rank matrix estimation problems. We derive the state evolution for the ASP algorithm and prove that it reproduces the one-step replica symmetry breaking (1RSB) fixed-point equations, well-known in physics of disordered systems. Our derivation thus gives a concrete algorithmic meaning to the 1RSB equations that is of independent interest. We characterize the performance of ASP in terms of convergence and mean-squared error as a function of the free Parisi parameter s. We conclude that when there is a model mismatch between the true generative model and the inference model, the performance of AMP rapidly degrades both in terms of MSE and of convergence, while for well-chosen values of the Parisi parameter s ASP converges in a larger regime and can reach lower errors. Among other results, our analysis leads us to a striking hypothesis that whenever s (or other parameters) can be set in such a way that the Nishimori condition M = Q > 0 is restored, then the corresponding algorithm is able to reach mean-squared error as low as the Bayes-optimal error obtained when the model and its parameters are known and exactly matched in the inference procedure. The remaining drawback is that we have not found a procedure that would systematically find a value of s leading to such low errors, this is a challenging problem let for future work.

关键词： message-passing algorithms statistical inference analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A dynamical mean-field theory for learning in restricted Boltzmann machines

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2020年第10期2020卷

作者： Cakmak, Burak Opper, Manfred Tech Univ Berlin Artificial Intelligence Grp Berlin Germany

We define a message-passing algorithm for computing magnetizations in restricted Boltzmann machines, which are Ising models on bipartite graphs introduced as neural network models for probability distributions over spin configurations. To model nontrivial statistical dependencies between the spins' couplings, we assume that the rectangular coupling matrix is drawn from an arbitrary bi-rotation invariant random matrix ensemble. Using the dynamical functional method of statistical mechanics we exactly analyze the dynamics of the algorithm in the large system limit. We prove the global convergence of the algorithm under a stability criterion and compute asymptotic convergence rates showing excellent agreement with numerical simulations.

关键词： cavity and replica method machine learning message-passing algorithms spin glasses

来源：评论

学校读者我要写书评

暂无评论

Shortest node-disjoint paths on random graphs

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2014年第7期000卷 P07009-P07009页

作者： De Bacco, C. Franz, S. Saad, D. Yeung, C. H. CNRS LPTMS F-91405 Orsay France Univ Paris 11 F-91405 Orsay France Aston Univ Nonlinear & Complex Res Grp Birmingham B4 7ET W Midlands England Hong Kong Univ Sci & Technol Dept Phys Hong Kong Hong Kong Peoples R China Hong Kong Inst Educ Dept Sci & Environm Studies Tai Po Hong Kong Peoples R China

A localized method to distribute paths on random graphs is devised, aimed at finding the shortest paths between given source/destination pairs while avoiding path overlaps at nodes. We propose a method based on message-passing techniques to process global information and distribute paths optimally. Statistical properties such as scaling with system size and number of paths, average path-length and the transition to the frustrated regime are analyzed. The performance of the suggested algorithm is evaluated through a comparison against a greedy algorithm.

关键词： cavity and replica method message-passing algorithms optimization over networks

来源：评论

学校读者我要写书评

暂无评论

Constraint satisfaction problems with isolated solutions are hard

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2008年第12期2008卷 P12004-P12004页

作者： Zdeborova, Lenka Mezard, Marc Univ Paris Sud LPTMS UMR8626 CNRS F-91405 Orsay France Los Alamos Natl Lab Div Theoret Los Alamos NM 87545 USA Los Alamos Natl Lab Ctr Nonlinear Studies Los Alamos NM 87545 USA

We study the phase diagram and the algorithmic hardness of the random 'locked' constraint satisfaction problems, and compare them to the commonly studied 'non-locked' problems like satisfiability of Boolean formulae or graph coloring. The special property of the locked problems is that clusters of solutions are isolated points. This simplifies significantly the determination of the phase diagram, which makes the locked problems particularly appealing from the mathematical point of view. On the other hand, we show empirically that the clustered phase of these problems is extremely hard from the algorithmic point of view: the best known algorithms all fail to find solutions. Our results suggest that the easy/hard transition (for currently known algorithms) in the locked problems coincides with the clustering transition. These should thus be regarded as new benchmarks of really hard constraint satisfaction problems.

关键词： analysis of algorithms message-passing algorithms random graphs networks typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Typical reconstruction performance for distributed compressed sensing based on l_2,1-norm regularized least square and Bayesian optimal reconstruction: influences of noise

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第6期2016卷 063304-063304页

作者： Shiraki, Yoshifumi Kabashima, Yoshiyuki NTT Corp NTT Commun Sci Labs Atsugi Kanagawa 2430198 Japan Tokyo Inst Technol Dept Math & Comp Sci Yokohama Kanagawa 2268502 Japan

A signal model called joint sparse model 2 (JSM-2) or the multiple measurement vector problem, in which all sparse signals share their support, is important for dealing with practical signal processing problems. In this paper, we investigate the typical reconstruction performance of noisy measurement JSM-2 problems for l(2,1)-norm regularized least square reconstruction and the Bayesian optimal reconstruction scheme in terms of mean square error. Employing the replica method, we show that these schemes, which exploit the knowledge of the sharing of the signal support, can recover the signals more precisely as the number of channels increases. In addition, we compare the reconstruction performance of two different ensembles of observation matrices: one is composed of independent and identically distributed random Gaussian entries and the other is designed so that row vectors are orthogonal to one another. As reported for the single-channel case in earlier studies, our analysis indicates that the latter ensemble offers better performance than the former ones for the noisy JSM-2 problem. The results of numerical experiments with a computationally feasible approximation algorithm we developed for this study agree with the theoretical estimation.

关键词： analysis of algorithms message-passing algorithms source and channel coding

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：