Search

This paper studies the convergence properties of the well-known message-passing algorithm for convex optimisation. Under the assumption of pairwise separability and scaled diagonal dominance, asymptotic convergence is established and a simple bound for the convergence rate is provided for message-passing. In comparison with previous results, our results do not require the given convex program to have known convex pairwise components and that our bound for the convergence rate is tighter and simpler. When specialised to quadratic optimisation, we generalise known results by providing a very simple bound for the convergence rate.

A layered construction of LDPC codes on 3-dimensional rectangular lattices is explored in this letter. By analyzing the governing conditions of in-layer polygons and inter-layer polygons, and elaborately selecting the slopes of in-layer and inter-layer lines, we remove all the 6-cycles as well as inter-layer 8-cycles which results in a class of LDPC codes without small trapping sets. We further remove the in-layer 8-cycles to design a class of LDPC codes with girth 10.

Gaussian belief propagation algorithm &#x0028 GaBP &#x0029 is one of the most important distributed algorithms in signal processing and statistical learning involving Markov networks. It is well known that the algorithm correctly computes marginal density functions from a high dimensional joint density function over a Markov network in a finite number of iterations when the underlying Gaussian graph is acyclic. It is also known more recently that the algorithm produces correct marginal means asymptotically for cyclic Gaussian graphs under the condition of walk summability &#x0028 or generalised diagonal dominance &#x0029 . This paper extends this convergence result further by showing that the convergence is exponential under the generalised diagonal dominance condition, and provides a simple bound for the convergence rate. Our results are derived by combining the known walk summability approach for asymptotic convergence analysis with the control systems approach for stability analysis.

In general, Gaussian belief propagation (BP) is not guaranteed to converge in loopy graphs. But when Gaussian BP converges to a fixed point of its update equations, the exact means of the marginal distributions can be obtained. However, given a Gaussian graphical model, whether Gaussian BP would have fixed points is unknown. Moreover, the relation between the convergence of Gaussian BP and its fixed points is not clear. To answer these questions, the necessary and sufficient existence condition and an easily verifiable sufficient existence condition of fixed points of Gaussian BP are proposed. Conditioned on the existence of fixed points of Gaussian BP, the convergence conditions of outgoing messages' parameters are analyzed, where outgoing message denotes the message flowing from a variable node to a factor node on a factor graph. It is proved that outgoing messages' precisions (the reciprocal of variance) would converge if there exist fixed points for Gaussian BP. This provides an elegant interpretation of the convergence condition of outgoing messages' precisions. On the other hand, to guarantee the convergence of outgoing messages' means, a sufficient condition for Gaussian models with a single loop and a sufficient condition that can be checked without obtaining the converged outgoing messages' precisions are derived. The relations between the convergence conditions of outgoing messages' parameters and those of incoming messages' parameters are also revealed, making any convergence condition of outgoing messages valid for verifying the convergence of incoming messages. Numerical results are presented to corroborate the newly established theories.

This letter deals with variational inference for Dirichlet process mixtures (DPM) models. We propose a combined message-passing algorithm introducing belief propagation (BP) into the original mean field (MF) rules, which leads to a more precise approximate posterior in DPM. To compute the BP message, we change an exponential distribution to a non-exponential utilizing a flexible expression of Dirac delta function. Therefore, BP rules can be used to handle such functions, resulting to a local exact expectation instead of approximate expectation from the original MF method. Simulation results show that the proposed combined BP–MF algorithm results in a significant performance improvement compared to the state-of-the-art inference methods.

Ultrasound (US) is widely used as a low-cost alternative to computed tomography or magnetic resonance and primarily for preliminary imaging. Since speckle intensity in US images is inherently stochastic, readers are often challenged in their ability to identify the pathological regions in a volume of a large number of images. This paper introduces a generalized approach for volumetric segmentation of structures in US images and volumes. We employ an iterative random walks (IRW) solver, a random forest learning model, and a gradient vector flow (GVF) based interframe belief propagation technique for achieving cross-frame volumetric segmentation. At the start, a weak estimate of the tissue structure is obtained using estimates of parameters of a statistical mechanics model of US tissue interaction. Ensemble learning of these parameters further using a random forest is used to initialize the segmentation pipeline. IRW is used for correcting the contour in various steps of the algorithm. Subsequently, a GVF-based interframe belief propagation is applied to adjacent frames based on the initialization of contour using information in the current frame to segment the complete volume by frame-wise processing. We have experimentally evaluated our approach using two different datasets. Intravascular ultrasound (IVUS) segmentation was evaluated using 10 pullbacks acquired at 20 MHz and thyroid US segmentation is evaluated on 16 volumes acquired at $\text{11}\text{--}\text{16}$ MHz. Our approach obtains a Jaccard score of $\text{0.937} \pm \text{0.022}$ for IVUS segmentation and $\text{0.908} \pm \text{0.028}$ for thyroid segmentation while processing each frame in $\text{1.15} \pm \text{0.05}\;\text{s}$ for the IVUS and in $\text{1.23} \pm \text{0.27}\;\text{s}$ for thyroid segmentation without the need of any computing accelerators such as GPUs.

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson–Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

Belief Propagation (BP), a distributed, message-passing algorithm, has been widely used in different disciplines including information theory, artificial intelligence, statistics and optimization problems in graphical models such as Bayesian networks and Markov random fields. Despite BP algorithm has a great success in many application fields and many progress about BP algorithm has been made, the rigorous analysis about the correctness and convergence of BP algorithm are known in only a few cases for arbitrary graph. In this paper, we will investigate the correctness and convergence of BP algorithm for determining the optimal solutions of the Chinese postman problem in both undirected and directed graphs. As a main result, we prove that BP algorithm converges to the optimal solution of the undirected Chinese postman problem within O(n) iterations where n represents the number of vertices, provided that the optimal solution is unique. For the directed case, we consider the directed Chinese postman problem with capacity and show that BP algorithm also converges to its optimal solution after O(n) iterations, as long as its corresponding linear programming relaxation has the unique optimal solution.

Conditional distributions, as defined by the Markov category framework, are studied in the setting of matrix algebras (quantum systems). Their construction as linear unital maps are obtained via a categorical Bayesian inversion procedure. Simple criteria establishing when such linear maps are positive are obtained. Several examples are provided, including the standard EPR scenario, where the EPR correlations are reproduced in a purely compositional (categorical) manner. A comparison between the Bayes map, the Petz recovery map, and the Leifer-Spekkens acausal belief propagation is provided, illustrating some similarities and key differences., Comment: In Proceedings QPL 2021, arXiv:2109.04886

A quantum stabilizer code over GF$(q)$ corresponds to a classical additive code over GF$(q^2)$ that is self-orthogonal with respect to a symplectic inner product. We study the decoding of quantum low-density parity-check (LDPC) codes over binary finite fields GF$(q=2^l)$ by the sum-product algorithm, also known as belief propagation (BP). Conventionally, a message in a nonbinary BP for quantum codes over GF$(2^l)$ represents a probability vector over GF$(2^{2l})$, inducing high decoding complexity. In this paper, we explore the property of the symplectic inner product and show that scalar messages suffice for BP decoding of nonbinary quantum codes, rather than vector messages necessary for the conventional BP. Consequently, we propose a BP decoding algorithm for quantum codes over GF$(2^l)$ by passing scalar messages so that it has low computation complexity. The algorithm is specified in log domain by using log-likelihood ratios (LLRs) of the channel statistics to have a low implementation cost. Moreover, techniques such as message normalization or offset can be naturally applied in this algorithm to mitigate the effects of short cycles to improve BP performance. This is important for nonbinary quantum codes since they may have more short cycles compared to binary quantum codes. Several computer simulations are provided to demonstrate these advantages. The scalar-based strategy can also be used to improve the BP decoding of classical linear codes over GF$(2^l)$ with many short cycles., Comment: correct the definition of {\cal S}^\perp on page 4 and equation (17)

We introduce novel belief propagation algorithms to estimate the marginals of a high dimensional probability distribution. They involve natural (co)homological constructions relevant for a localised description of statistical systems.

In this paper, we perform a belief propagation (BP) decoding threshold analysis of spatially coupled (SC) turbo-like codes (TCs) (SC-TCs) on the additive white Gaussian noise (AWGN) channel. We review Monte-Carlo density evolution (MC-DE) and efficient prediction methods, which determine the BP thresholds of SC-TCs over the AWGN channel. We demonstrate that instead of performing time-consuming MC-DE computations, the BP threshold of SC-TCs over the AWGN channel can be predicted very efficiently from their binary erasure channel (BEC) thresholds. From threshold results, we conjecture that the similarity of MC-DE and predicted thresholds is related to the threshold saturation capability as well as capacity-approaching maximum a posteriori (MAP) performance of an SC-TC ensemble.

Sparse Bayesian Learning (SBL), initially proposed in the Machine Learning (ML) literature, is an efficient and well-studied framework for sparse signal recovery. SBL uses hierarchical Bayes with a decorrelated Gaussian prior in which the variance profile is also to be estimated. This is more sparsity inducing than e.g. a Laplacian prior. However, SBL does not scale with problem dimensions due to the computational complexity associated with the matrix inversion in Linear Mimimum Mean Squared Error (LMMSE) estimation. To address this issue, various low complexity approximate Bayesian inference techniques have been introduced for the LMMSE component, including Variational Bayesian (VB) inference, Space Alternating Variational Estimation (SAVE) or Message Passing (MP) algorithms such as Belief Propagation (BP) or Expectation Propagation (EP) or Approximate MP (AMP). These algorithms may converge to the correct LMMSE estimate. However, in ML we are often also interested in having posterior variance information. SBL via BP or SAVE provides (largely) underestimated variance estimates. AMP style algorithms may provide more accurate variance information. The State Evolution analysis may show convergence of the (sum) MSE to the MMSE value. But we are interested also in the MSE of the individual components. To this end, utilizing the random matrix theory results, we show that in the large system limit, under i.i.d. entries in the measurement matrix, the per component MSE predicted by BP or xAMP converges to the Bayes optimal value.

We consider the problem of recovering an unknown $k$-factor, hidden in a weighted random graph. For $k=1$ this is the planted matching problem, while the $k=2$ case is closely related to the planted travelling salesman problem. The inference problem is solved by exploiting the information arising from the use of two different distributions for the weights on the edges inside and outside the planted sub-graph. We argue that, in the large size limit, a phase transition can appear between a full and a partial recovery phase as function of the signal-to-noise ratio. We give a criterion for the location of the transition., 21 pages, 4 figures

In this paper, we work on the symbolwise maximum a posteriori probability (MAP) estimation of channel input symbol from m (≥ 2) received words (traces) having inser- tion/deletion/substitution (IDS) errors, where the errors are independent between m received words. This problem is motivated by readout process in next-generation sequencers of DNA storage. The MAP estimation is based on the belief propagation algorithm on a factor graph, which represents the joint probability of a channel input word and m pairs of channel output word and drift vector. We also propose a heuristic estimation algorithm for m ≥ 4 to reduce the computational complexity. Simulation results show the relation between channel IDS error rate and estimation error rate.

Bounds on information combining are entropic inequalities that determine how the information, or entropy, of a set of random variables can change when they are combined in certain prescribed ways. Such bounds play an important role in information theory, particularly in coding and Shannon theory. The arguably most elementary kind of information combining is the addition of two binary random variables, i.e. a CNOT gate, and the resulting quantities are fundamental when investigating belief propagation and polar coding. In this work we will generalize the concept to R\'enyi entropies. We give optimal bounds on the conditional R\'enyi entropy after combination, based on a certain convexity or concavity property and discuss when this property indeed holds. Since there is no generally agreed upon definition of the conditional R\'enyi entropy, we consider four different versions from the literature. Finally, we discuss the application of these bounds to the polarization of R\'enyi entropies under polar codes., Comment: 14 pages, accepted for presentation at ISIT 2020

© 2020 IEEE. We study a problem of constructing codes that transform a channel with high bit error rate (BER) into one with low BER (at the expense of rate). Our focus is on obtaining codes with smooth (graceful) input-output BER curves (as opposed to threshold-like curves typical for long error-correcting codes).This paper restricts attention to binary erasure channels (BEC) and contains two contributions. First, we introduce the notion of Low Density Majority Codes (LDMCs). These codes are non-linear sparse-graph codes, which output majority function evaluated on randomly chosen small subsets of the data bits. This is similar to Low Density Generator Matrix codes (LDGMs), except that the XOR function is replaced with the majority. We show that even with a few iterations of belief propagation (BP) the attained input-output curves provably improve upon performance of any linear systematic code. The effect of nonlinearity bootstraping the initial iterations of BP, suggests that LDMCs should improve performance in various applications where LDGMs have been used traditionally.Second, we establish several two-point converse bounds that lower bound the BER achievable at one erasure probability as a function of BER achieved at another one. The novel nature of our bounds is that they are specific to subclasses of codes (linear systematic and non-linear systematic) and outperform similar bounds implied by the area theorem for the EXIT function.

Gaussian belief propagation (BP) finds extensive applications in signal processing but it is not guaranteed to converge in loopy graphs. In order to determine whether Gaussian BP would converge, one could directly use the classical convergence conditions of Gaussian BP, such as diagonal dominance, walk-summabilitiy, and convex decomposition. These classical conditions assume that the convergence conditions for Gaussian BP precisions and means are the same, which has been proved to be unnecessary. Generally, the condition for guaranteeing the convergence of Gaussian BP precisions is looser than that of Gaussian BP means. Moreover, the convergence of Gaussian BP means could be improved by damping when Gaussian BP precisions converge. Therefore, the convergence of Gaussian BP precisions is a prerequisite for guaranteeing the convergence of Gaussian BP means. This paper derives a simple convergence condition for Gaussian BP precisions, which can be verified in a distributed way. Through numerical examples, it is found that there exists scenarios where the new condition is satisfied but the classical conditions are not.

With the rapid increase in the number of large-scale distributed cameras and the rapid increase in the monitoring range of the camera network, how to accurately recognize and analyze abnormal behavior is still a challenging problem. In addition, the appearance of moving objects between different cameras without overlapping fields of view undergoes significant changes, making it difficult to obtain accurate association Therefore, multiobjects association and abnormal behavior detection for massive data analysis in multisensor monitoring network are proposed in this paper, which firstly uses belief propagation to associate multiple objects, extracts the object’s behavior trajectory characteristics, and then builds a long short-term memory classification network to realize automatic classification of abnormal behaviors. Multiobject association fully considers the timing correlation and object detection probability, as well as the statistical dependence of the measurement on the association matrix. The experimental results show that our proposed method can achieve a high classification accuracy and sensitivity, which meets the requirements of automatic classification of abnormal behavior in complex monitoring network. This further shows that this research has practical application value.

The community detection problem involves making inferences about node labels in a graph, based on observing the graph edges. This paper studies the effect of additional, non-graphical side information on the phase transition of exact recovery in the binary stochastic block model (SBM) with $n$ nodes. When side information consists of noisy labels with error probability $\alpha$, it is shown that phase transition is improved if and only if $\log(\frac{1-\alpha}{\alpha})=\Omega(\log(n))$. When side information consists of revealing a fraction $1-\epsilon$ of the labels, it is shown that phase transition is improved if and only if $\log(1/\epsilon)=\Omega(\log(n))$. For a more general side information consisting of $K$ features, two scenarios are studied: (1)~$K$ is fixed while the likelihood of each feature with respect to corresponding node label evolves with $n$, and (2)~The number of features $K$ varies with $n$ but the likelihood of each feature is fixed. In each case, we find when side information improves the exact recovery phase transition and by how much. The calculated necessary and sufficient conditions for exact recovery are tight except for one special case. In the process of deriving inner bounds, a variation of an efficient algorithm is proposed for community detection with side information that uses a partial recovery algorithm combined with a local improvement procedure.

The belief propagation (BP) algorithm is a message-passing algorithm that is used for solving probabilistic inference problems. In practice, the BP algorithm performs well as a heuristic in many application fields. However, the theoretical understanding of BP is limited. To improve the theoretical understanding of BP, the BP algorithm has been applied to many well-understood combinatorial optimization problems. In this paper, we consider BP applied to the maximum-weight independent set (MWIS) and minimum spanning tree (MST) problems. Sanghavi et al. (2009) [12] applied the BP algorithm to the MWIS problem. We denote their algorithm by BP-MWIS. They showed that if the LP relaxation of the MWIS problem has a unique integral optimal solution and BP-MWIS converges, then BP-MWIS finds the optimal solution. Also, they showed that if the LP relaxation has a non-integral optimal solution, then BP-MWIS does not converge. In this paper, we precisely characterize the graphs for which BP-MWIS is guaranteed to find the optimal solution, regardless of the node weights. Bayati et al. (2008) [2] applied the BP algorithm to the MST problem. We denote their algorithm by BP-MST. They showed that if BP-MST converges, then it finds the optimal solution. In this paper, however, we provide an instance for which BP-MST does not converge. Also, since this instance is small and simple, we believe that BP-MST does not converge for most instances encountered in practice.

Community detection is considered for a stochastic block model graph of n vertices, with K vertices in the planted community, edge probability p for pairs of vertices both in the community, and edge probability q for other pairs of vertices. The main focus of the paper is on weak recovery of the community based on the graph G, with o(K) misclassified vertices on average, in the sublinear regime n1-o(1) ≤ K ≤ o(n). A critical parameter is the effective signal-to-noise ratio λ = K2(p - q)2 / ((n - K)q), with λ = 1 corresponding to the Kesten–Stigum threshold. We show that a belief propagation (BP) algorithm achieves weak recovery if λ > 1 / e, beyond the Kesten–Stigum threshold by a factor of 1 / e. The BP algorithm only needs to run for log*n + O(1) iterations, with the total time complexity O(|E|log*n), where log*n is the iterated logarithm of n. Conversely, if λ ≤ 1 / e, no local algorithm can asymptotically outperform trivial random guessing. Furthermore, a linear message-passing algorithm that corresponds to applying a power iteration to the nonbacktracking matrix of the graph is shown to attain weak recovery if and only if λ > 1. In addition, the BP algorithm can be combined with a linear-time voting procedure to achieve the information limit of exact recovery (correctly classify all vertices with high probability) for all K ≥ (n / logn) (ρBP + o(1)), where ρBP is a function of p / q.

Seismic reflection pre‐stack angle gathers can be simultaneously inverted within a joint facies and elastic inversion framework using a hierarchical Bayesian model of elastic properties and categorical classes of rock and fluid properties. The Bayesian prior implicitly supplies low frequency information via a set of multivariate compaction trends for each rock and fluid type, combined with a Markov random field model of lithotypes, which carries abundance and continuity preferences. For the likelihood, we use a simultaneous, multi‐angle, convolutional model, which quantifies the data misfit probability using wavelets and noise levels inferred from well ties. Under Gaussian likelihood and facies‐conditional prior models, the posterior has simple analytic form, and the maximum a‐posteriori inversion problem boils down to a joint categorical/continuous non‐convex optimisation problem. To solve this, a set of alternative, increasingly comprehensive optimisation strategies is described: (i) an expectation–maximisation algorithm using belief propagation, (ii) a globalisation of method (i) using homotopy, and (iii) a discrete space approach using simulated annealing. We find that good‐quality inversion results depend on both sensible, elastically separable facies definitions, modest resolution ambitions, reasonably firm abundance and continuity parameters in the Markov random field, and suitable choice of algorithm. We suggest usually two to three, perhaps four, unknown facies per sample, and usage of the more expensive methods (homotopy or annealing) when the rock types are not strongly distinguished in acoustic impedance. Demonstrations of the technique on pre‐stack depth‐migrated field data from the Exmouth basin show promising agreements with lithological well data, including prediction accuracy improvements of 24% in vp/vs and twofold in density, in comparison to a standard simultaneous inversion. Much clearer and extensive recovery of the thin Pyxis gas field was evident using stronger coupling in the Markov random field model and use of the homotopy or annealing algorithms.

We study the maximum weight matching (MWM) problem for general graphs through the max-product belief propagation (BP) and related Linear Programming (LP). The BP approach provides distributed heuristics for finding the maximum a posteriori (MAP) assignment in a joint probability distribution represented by a graphical model (GM), and respective LPs can be considered as continuous relaxations of the discrete MAP problem. It was recently shown that a BP algorithm converges to the correct MAP/MWM assignment under a simple GM formulation of MWM, as long as the corresponding LP relaxation is tight. First, under the motivation for forcing the tightness condition, we consider a new GM formulation of MWM, say C-GM, using non-intersecting odd-sized cycles in the graph; the new corresponding LP relaxation, say C-LP, becomes tight for more MWM instances. However, the tightness of C-LP now does not guarantee such convergence and correctness of the new BP on C-GM. To address the issue, we introduce a novel graph transformation applied to C-GM, which results in another GM formulation of MWM, and prove that the respective BP on it converges to the correct MAP/MWM assignment, as long as C-LP is tight. Finally, we also show that C-LP always has half-integral solutions, which leads to an efficient BP-based MWM heuristic consisting of making sequential, “cutting plane”, modifications to the underlying GM. Our experiments show that this BP-based cutting plane heuristic performs, as well as that based on traditional LP solvers.

Hole filling is one of the key issues in generating virtual view from video-plus-depth sequence by depth-image-based rendering. Hole filling method based on Markov random fields (MRF) is a practical way for view synthesis, but the traditional ones might introduce some foreground textures to the hole regions, and suffer from high computational complexity. In this letter, a fast MRF-based hole filling method is proposed for view synthesis, which is formulated as an energy minimization problem and is solved with loopy belief propagation (LBP). The energy function is optimized by employing the depth information to prevent the foreground textures filling holes. Furthermore, the LBP process maintains the visual consistency in the synthesized view by reserving all useful candidate labels. In addition, efficient belief propagation strategy is developed to optimize the LBP process, whose computational complexity is reduced to be linear with the number of candidate labels. Experimental results demonstrate the effectiveness of the proposed method with low running time and good visual consistency.

Analyzing the solution space structure and evolution of 3-satisfiability (3-SAT) problem is an important way to study the difficulty of the solving satisfiability (SAT) problem. However, there is no unified analysis model for the spatial structure and evolution of solutions under different constraint densities. The analysis of different phase transition points and solution regions is based on different metric analysis models. The solution space of 3-SAT problem is obtained by planting strategy and belief propagation. According to the distribution of the influence of frozen variables on the solution, a label propagation algorithm based on planting strategy is proposed, is used to find the solution cluster, and then the structure entropy is used to measure its structure information. The structure entropy analysis model of 3-SAT problem solution space is established, and the unified analysis framework of solution space evolution and satisfiability phase transition is given. The experimental results show that the model is effective and can accurately analyze the evolution process of solution space and satisfiability phase transition, and verify the accuracy of interference phase transition point threshold predicted by long-range frustration theory.

Rateless coding such as Luby transform (LT) codes is representative of rate adaptive solutions to improve the frequency efficiency of transmitting data over a time-varying wireless channel. Also, these type of codes use belief propagation (BP) decoding which searches for encoded packets with degree 1 among the large numbers of encoded packets. This method fails if no encoded packets with degree 1 exist. However, in reality, small numbers of input packets are often encountered. In this paper, we have proposed a decoding algorithm that increases the performance of these codes for the small number of source packets. After the failure of BP decoding, to recover the remaining source packets, we use a method which keeps on decoding using the encoded packets whose degrees are not one. This algorithm continues until a degree 1 packet emerges in one of the iterations of this decoding process. Then, decoding algorithm switches back to the traditional BP decoding.

In this letter, we propose a pair of blind detectors for spatial modulation multiple-input multiple-output (MIMO) systems based on the clustering concept. Specifically, an improved K-means clustering (KMC) with lower-complexity detector is first proposed to avoid the error floor effects and to reduce the imposed complexity of the conventional KMC detector by employing an initial centroid optimizer. Furthermore, an affinity propagation (AP) detector is developed based on the belief propagation concept, where the number of clusters is not required in the clustering process by using the intelligence information exchanges. The results show that the proposed KMC detector can efficiently avoid the occurrence of error floor effects, while the proposed AP detector is capable of achieving better performance than that of the conventional KMC detector.

In a paper that initiated the modern study of the stochastic block model (SBM), Decelle, Krzakala, Moore, and Zdeborova, backed by Mossel, Neeman, and Sly, conjectured that detecting clusters in the symmetric SBM in polynomial time is always possible above the Kesten-Stigum (KS) threshold, while it is possible to detect clusters information theoretically (i.e., not necessarily in polynomial time) below the KS threshold when the number of clusters k is at least 4. Massoulie, Mossel et al., and Bordenave, Lelarge, and Massoulie proved that the KS threshold is in fact efficiently achievable for k = 2, while Mossel et al. proved that it cannot be crossed at k = 2. The above conjecture remained open for k ≥ 3. This paper proves the two parts of the conjecture, further extending the results to general SBMs. For the efficient part, an approximate acyclic belief propagation (ABP) algorithm is developed and proved to detect communities for any k down to the KS threshold in quasi-linear time. Achieving this requires showing optimality of ABP in the presence of cycles, a challenge for message-passing algorithms. The paper further connects ABP to a power iteration method on a nonbacktracking operator of generalized order, formalizing the interplay between message passing and spectral methods. For the information-theoretic part, a nonefficient algorithm sampling a typical clustering is shown to break down the KS threshold at k = 4. The emerging gap is shown to be large in some cases, making the SBM a good case study for information-computation gaps. © 2017 Wiley Periodicals, Inc.

We develop a computationally efficient approach for evaluating the information-theoretic term within belief space planning (BSP), where during belief propagation the state vector can be constant or augmented. We consider both unfocused and focused problem settings, whereas uncertainty reduction of the entire system or only of chosen variables is of interest, respectively. State-of-the-art approaches typically propagate the belief state, for each candidate action, through calculation of the posterior information (or covariance) matrix and subsequently compute its determinant (required for entropy). In contrast, our approach reduces runtime complexity by avoiding these calculations. We formulate the problem in terms of factor graphs and show that belief propagation is not needed, requiring instead a one-time calculation that depends on (the increasing with time) state dimensionality, and per-candidate calculations that are independent of the latter. To that end, we develop an augmented version of the matrix determinant lemma, and show that computations can be re-used when evaluating impact of different candidate actions. These two key ingredients and the factor graph representation of the problem result in a computationally efficient (augmented) BSP approach that accounts for different sources of uncertainty and can be used with various sensing modalities. We examine the unfocused and focused instances of our approach, and compare it with the state of the art, in simulation and using real-world data, considering problems such as autonomous navigation in unknown environments, measurement selection and sensor deployment. We show that our approach significantly reduces running time without any compromise in performance.

Abrupt motions commonly cause conventional tracking methods to fail because they violate the motion smoothness constraint. To overcome this problem, we propose a novel SIFT flow tracker (SFT) and integrate it into a sparse representation-based tracking framework. In this method, we first introduce the SIFT flow method to address the tracking problem. The method can avoid the local-trap modes and cope with abrupt motion without any prior knowledge. Then, for obtaining the effective samples, we design a new hybrid sampling mechanism, which can sample the local and global predicted location according to confidence map. Finally, to adapt the target appearance variations, especially to partial occlusion, we embed SFT to L1 tracker and construct a unified framework to track both smooth and abrupt motion in time. Compared with several state-of-art tracking algorithms, experimental results demonstrate that our method achieves favorable performance in handling abrupt motion, even under target appearance variations including illumination changes, partial occlusion and pose changes.

Convergence and density evolution of a low-complexity iterative multiple-input multiple-output detection based on belief propagation over a ring-type pairwise graph are presented for binary data. The detection algorithm to be considered is effectively a forward–backward recursion and was originally proposed by Yoon and Chae in a work published in 2014, in which link-level performance, computational complexity, and convergence for Gaussian input were analyzed in detail. This paper presents the convergence proof and the density evolution framework for binary input to give an asymptotic performance in terms of average signal-to-interference-plus-noise ratio and bit error rate (BER) without channel coding. The BER curve obtained via density evolution shows a good match with the simulation results for uncoded BER in the paper by Yoon and Chae verifying the effectiveness of the analysis provided and the performance of the detection algorithm.

In this study, the authors present an improved min-sum (MS) algorithm based on density evolution (DE) called the DE MS algorithm for low-density parity check codes. First, they use DE theory to calculate the probability density function of the check-to-variable message of the belief propagation (BP) algorithm and the MS/normalised MS (NMS) algorithm and furthermore to calculate the normalised factor α . Then, α is modified further by using the weighted average. Finally, in order to ensure the decoding performance and reduce the hardware complexity, the same α is used for different signal-to-noise ratios. The simulation results show that a gain of about 0.2 dB can be achieved in comparison with the classical NMS algorithm. In addition, this algorithm can obtain the same decoding performance compared with the Linear Minimum Mean Square Error (LMMSE) MS algorithm whose decoding performance is very close to that of the BP algorithm, and it also saves around 24.57% of logic elements and 34.33% of memory bits compared with the LMMSE MS algorithm at the same time.

Presented a belief propagation method to calculate the belief of each node in a network.Proposed a measurement of influence between different types of relations using belief vectors.Presented a nonnegative matrix factorization based algorithm for link prediction in multi-relational networks.Theoretically proved the convergence and correctness of the proposed algorithm.Empirically demonstrated the proposed algorithm can achieve higher quality prediction results. Many real-world networks contain multiple types of interactions and relations. Link prediction in such multi-relational networks has become an important area in network analysis. For link prediction in multi-relational networks, we should consider the similarity and influence between different types of relations. In this paper, we propose a link prediction algorithm in multi-relational networks based on relational similarity. In the algorithm, a belief propagation method is presented to calculate the belief of each node and to construct the belief vector for each type of link. We use the similarity between belief vectors to measure the influence between different types of relations. Based on the influence between different relations, we present a nonnegative matrix factorization -based method for link prediction in multi-relational networks. The convergence and correctness of the presented method are proved. Our experimental results show that our method can achieve higher-quality prediction results than other similar algorithms.

Belief propagation (BP) has been applied in a variety of inference problems as an approximation tool. BP does not necessarily converge in loopy graphs, and even if it does, is not guaranteed to provide exact inference. Even so, BP is useful in many applications due to its computational tractability. In this article, we investigate a regularized BP scheme by focusing on loopy Markov graphs (MGs) induced by a multivariate Gaussian distribution in canonical form. There is a rich literature surrounding BP on Gaussian MGs (labelled Gaussian belief propagation or GaBP), and this is known to experience the same problems as general BP on graphs. GaBP is known to provide the correct marginal means if it converges (this is not guaranteed), but it does not provide the exact marginal precisions. We show that our adjusted BP will always converge, with sufficient tuning, while maintaining the exact marginal means. As a further contribution we show, in an empirical study, that our GaBP variant can accelerate GaBP and compares well with other GaBP-type competitors in terms of convergence speed and accuracy of approximate marginal precisions. These improvements suggest that the principle of regularized BP should be investigated in other inference problems. The selection of the degree of regularization is addressed through the use of two heuristics. A by-product of GaBP is that it can be used to solve linear systems of equations; the same is true for our variant and we make an empirical comparison with the conjugate gradient method.

In this paper, a co-segmentation algorithm based on 3D heat diffusion named co-diffusion is proposed. The image set is considered as a metal cuboid, and the K heat sources with constant temperature, which maximize the sum of the temperature of the system under anisotropic heat diffusion, are found to cluster the image set. The co-diffusion co-segmentation is an intuitive extension of the diffusion segmentation in Kim et al. (Proceedings of ICCV, 2011) while the performance is greatly improved. Comparatively, the proposed algorithm advances in the following three aspects: (1) The proposed algorithm can obtain better optimization because the heat diffusion is directly solved in 3D image set space, while the algorithm in Kim et al. (2011) deals with many independent 2D heat diffusions and solves the optimization by approximate belief propagation. (2) The marginal gain of every candidate heat source is globally determined in the image set, which can effectively compensate the wrong segmentations caused by the locality of the 2D image diffusion (Kim et al. 2011). (3) The K heat sources are chosen in image set while the algorithm (Kim et al. 2011) appoints mandatory K heat sources to each image in set, which will inevitably cause wrong segmentations for some images. The superiority of the proposed co-diffusion segmentation method is examined and demonstrated through a large number of experiments by using some typical datasets.

Let Φ be a uniformly distributed random k -SAT formula with n variables and m clauses. Nonconstructive arguments show that Φ is satisfiable for clause/variable ratios m / n ⩽ r k − SAT ∼ 2 k ln 2 with high probability. Yet no efficient algorithm is known to find a satisfying assignment beyond m / n ∼ 2 k ln ( k )/ k with a nonvanishing probability. On the basis of deep but nonrigorous statistical mechanics ideas, a message passing algorithm called Belief Propagation Guided Decimation has been put forward (Mézard, Parisi, Zecchina: Science 2002; Braunstein, Mézard, Zecchina: Random Struc. Algorithm 2005). Experiments suggested that the algorithm might succeed for densities very close to r k − SAT for k = 3, 4, 5 (Kroc, Sabharwal, Selman: SAC 2009). Furnishing the first rigorous analysis of this algorithm on a nontrivial input distribution, in the present article we show that Belief Propagation Guided Decimation fails to solve random k -SAT formulas already for m / n = O (2 k / k ), almost a factor of k below the satisfiability threshold r k − SAT . Indeed, the proof refutes a key hypothesis on which Belief Propagation Guided Decimation hinges for such m / n .

Sparsely spread code division multiple access (SCDMA) is a non-orthogonal superposition coding scheme that allows concurrent communications between a base station and multiple users over a common channel. However, the detection performance of an SCDMA system is mainly determined by its signature matrix, which should be sparse to facilitate the belief propagation (BP) detection. On the other hand, to guarantee good maximum likelihood (ML) detection performance, the minimum Euclidean distance for the equivalent signal constellation after multi-user superposition should be maximized. In this paper, a code distance analysis is proposed for SCDMA systems with a finite number of users and spreading lengths. Based on this analysis, good signature matrices whose factor graphs have very few short cycles and possess large superposed signal constellation distances are designed. The proposed signature matrices have both good BP and ML detection performances. Moreover, their BP detection performances exactly converge to their ML detection performances with few iterations. It is worth pointing out that the proposed signature matrix design could be directly applied to the 5G non-orthogonal multiple access systems.

In this paper, we propose an optimized belief propagation (OBP) based progressive edge-growth (PEG) method for constructing quasi-cyclic low density parity check (QC-LDPC) codes. In this proposed method, Tanner graphs are built by progressively appending the check nodes rather than the variable nodes. Moreover, this OBP-PEG method considers three new constraint conditions to select the QC-LDPC code sets constructed by the PEG method. Compared with the PEG-based QC-LDPC decoders, the proposed OBP-PEG decoders decrease the number of the input ports of check-node processer by up to 25%, accelerates the convergence speed by up to 11.7% in layered decoding process, and improves the success probability by up to ten times in constructing fast-convergence QC-LDPC codes.

We formalize the class of “sequential local algorithms" and show that these algorithms fail to find satisfying assignments on random instances of the “Not-All-Equal-$K$-SAT” (NAE-$K$-SAT) problem if the number of message passing iterations is bounded by a function moderately growing in the number of variables and if the clause-to-variable ratio is above $(1+o_K(1)){2^{K-1}\over K}\ln^2 K$ for sufficiently large $K$. Sequential local algorithms are those that iteratively set variables based on some local information and/or local randomness and then recurse on the reduced instance. Our model captures some weak abstractions of natural algorithms such as Survey Propagation (SP)-guided as well as Belief Propagation (BP)-guided decimation algorithms---two widely studied message-passing--based algorithms---when the number of message-passing rounds in these algorithms is restricted to be growing only moderately with the number of variables. The approach underlying our paper is based on an intricate geometry of th...

In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) c * sqrt((d_+)ln(d_+)) for a certain constant c>0.

The max-product belief propagation (BP) is a popular message-passing heuristic for approximating a maximum-a-posteriori assignment in a joint distribution represented by a graphical model. In the past years, it has been shown that BP can solve a few classes of linear programming (LP) formulations to combinatorial optimization problems including maximum weight matching, shortest path, and network flow, i.e., BP can be used as a message-passing solver for certain combinatorial optimizations. However, those LPs and corresponding BP analysis are very sensitive to underlying problem setups, and it has been not clear what extent these results can be generalized to. In this paper, we obtain a generic criteria that BP converges to the optimal solution of given LP and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, traveling salesman, cycle packing, vertex/edge cover, and network flow.

The topic of the rank minimization problem with affine constraints has been well studied in recent years. However, in many applications the data can exhibit other structures beyond simply being low rank. For example, images and videos present complex spatio-temporal structures, which are largely ignored by current affine rank minimization (ARM) methods. In this paper, we propose a novel approximate message passing (AMP)-based approach that is capable of capturing additional structures in the matrix entries, and can be implemented in a wide range of applications with little or no modification. Using probabilistic low-rank factorization, we derive our generalized AMP-based algorithm as an approximation of the loopy belief propagation algorithm. In addition, we apply a rank selection strategy and an expectation-maximization estimation strategy that adaptively obtain the optimal value of the algorithmic parameters. Then, we discuss the specializations of our proposed algorithm to the applications of structured ARM problems, such as compressive hyperspectral imaging and compressive video surveillance. Simulation results with both synthetic and real data demonstrate that the proposed algorithm yields the state-of-the-art reconstruction performance while maintaining competitive computational complexity.

Generalized Linear Models (GLMs), where a random vector $\mathbf{x}$ is observed through a noisy, possibly nonlinear, function of a linear transform $\mathbf{z}=\mathbf{Ax}$ arise in a range of applications in nonlinear filtering and regression. Approximate Message Passing (AMP) methods, based on loopy belief propagation, are a promising class of approaches for approximate inference in these models. AMP methods are computationally simple, general, and admit precise analyses with testable conditions for optimality for large i.i.d. transforms $\mathbf{A}$. However, the algorithms can easily diverge for general $\mathbf{A}$. This paper presents a convergent approach to the generalized AMP (GAMP) algorithm based on direct minimization of a large-system limit approximation of the Bethe Free Energy (LSL-BFE). The proposed method uses a double-loop procedure, where the outer loop successively linearizes the LSL-BFE and the inner loop minimizes the linearized LSL-BFE using the Alternating Direction Method of Multipliers (ADMM). The proposed method, called ADMM-GAMP, is similar in structure to the original GAMP method, but with an additional least-squares minimization. It is shown that for strictly convex, smooth penalties, ADMM-GAMP is guaranteed to converge to a local minima of the LSL-BFE, thus providing a convergent alternative to GAMP that is stable under arbitrary transforms. Simulations are also presented that demonstrate the robustness of the method for non-convex penalties as well.

In this paper, we study the approximate message passing (AMP) algorithm for $L_{\frac{1}{2}}$ regularization. We propose an improved half iterative thresholding algorithm, which is inspired by belief propagation in graphical model. Further, we study the convergence property of the new algorithm. Through extensive simulations, we show that the iterative thresholding algorithms based on AMP for several nonconvex regularization approaches have strong reconstruction capabilities and high phase transition.

Scanned images of historical documents often suffer from bleed-through, which refers to the ink on one side seeping through the paper and appearing on the other side. In this paper, a new conditional random field (CRF)-based method is proposed to remove the bleed-through from the scanned images of historical images. The proposed method only requires the scanned image of one side, referred as a blind method. In general, the scanned historical document image is composed of three components: foreground, bleed-through, and background. By assuming Gaussian distributions of the three components, the proposed method establishes conditional probability distribution (CPD) models of the three components first. The parameters of the component CPD models are estimated based on an initial segmentation of the input image. Then, CRFs are used to capture the relations between observed pixels in the scanned image and the corresponding labels as well as the spatial relation between the adjacent labels. The belief propagation algorithm is used to calculate the probabilities of different labels for each pixel. Once the labeling is completed by choosing the most possible label for each pixel, the bleed-through component is removed from the input historical image by a random-filling inpainting algorithm. Experimental results on the real data set show that the proposed method preserves the foreground component very well and removes the bleed-through effectively.

The directed L-distance minimal dominating set (MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erd$\acute{o}$s R$\acute{e}$nyi (ER) random graph and regular random graph, but this work can be extended to any type of networks. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation algorithm does not converge when the inverse temperature exceeds a threshold on either an ER random network or regular random network. Second, the entropy density of replica symmetric theory has a transition point at a finite inverse temperature on a regular random graph when the node degree exceeds 4 and on an ER random graph when the node degree exceeds 6.6; there is no entropy transition point (or $\beta=\infty$) in other circumstances. Third, the results of the replica symmetry (RS) theory are in perfect agreement with those of belief propagation (BP) algorithm while the results of the belief propagation decimation (BPD) algorithm are better than those of the greedy heuristic algorithm.