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...
详细信息
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.
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.
In underwater acoustics, wave propagation can be greatly disrupted by random fluctuations in the ocean environment. In particular, phase measurements of the complex pressure field can be heavily noisy and can defeat c...
详细信息
ISBN:
(纸本)9783319937649;9783319937632
In underwater acoustics, wave propagation can be greatly disrupted by random fluctuations in the ocean environment. In particular, phase measurements of the complex pressure field can be heavily noisy and can defeat conventional direction-of-arrival (DOA) estimation algorithms. In this paper, we propose a new Bayesian approach to address such phase noise through an informative prior on the measurements. This is combined to a sparse assumption on the directions of arrival to achieve a highly-resolved estimation and integrated into a message-propagation algorithm referred to as the "paSAMP" algorithm (for Phase-Aware Swept Approximate messagepassing). Our algorithm can be seen as an extension of the recent phase-retrieval algorithm "prSAMP" to phase-aware priors. Experiments on simulated data mimicking real environments demonstrate that paSAMP outperform conventional approaches (e.g. classic beamforming) in terms of DOA estimation. paSAMP also proves to be more robust to additive noise than other variational methods (e.g. based on mean-field approximation).
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....
详细信息
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.
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...
详细信息
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.
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 i...
详细信息
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 messagepassing algorithm. The messagepassing 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 messagepassing 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.
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 th...
详细信息
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 messagepassing are provided for finding the minima.
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 Mo...
详细信息
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 messagepassing (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.
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 H...
详细信息
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 messagepassing (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.
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 satisfa...
详细信息
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.
暂无评论