Search

We develop a hybrid model-based data-driven seizure detection algorithm called Mutual Information-based CNN-Aided Learned factor graphs (MICAL) for detection of eclectic seizures from EEG signals. Our proposed method contains three main components: a neural mutual information (MI) estimator, 1D convolutional neural network (CNN), and factor graph inference. Since during seizure the electrical activity in one or more regions in the brain becomes correlated, we use neural MI estimators to measure inter-channel statistical dependence. We also design a 1D CNN to extract additional features from raw EEG signals. Since the soft estimates obtained as the combined features from the neural MI estimator and the CNN do not capture the temporal correlation between different EEG blocks, we use them not as estimates of the seizure state, but to compute the function nodes of a factor graph. The resulting factor graphs allows structured inference which exploits the temporal correlation for further improving the detection performance. On public CHB-MIT database, We conduct three evaluation approaches using the public CHB-MIT database, including 6-fold leave-four-patients-out cross-validation, all patient training; and per patient training. Our evaluations systematically demonstrate the impact of each element in MICAL through a complete ablation study and measuring six performance metrics. It is shown that the proposed method obtains state-of-the-art performance specifically in 6-fold leave-four-patients-out cross-validation and all patient training, demonstrating a superior generalizability.

We consider the application of the factor graph framework for symbol detection on linear inter-symbol interference channels. Based on the Ungerboeck observation model, a detection algorithm with appealing complexity properties can be derived. However, since the underlying factor graph contains cycles, the sum-product algorithm (SPA) yields a suboptimal algorithm. In this paper, we develop and evaluate efficient strategies to improve the performance of the factor graph-based symbol detection by means of neural enhancement. In particular, we consider neural belief propagation and generalizations of the factor nodes as an effective way to mitigate the effect of cycles within the factor graph. By applying a generic preprocessor to the channel output, we propose a simple technique to vary the underlying factor graph in every SPA iteration. Using this dynamic factor graph transition, we intend to preserve the extrinsic nature of the SPA messages which is otherwise impaired due to cycles. Simulation results show that the proposed methods can massively improve the detection performance, even approaching the maximum a posteriori performance for various transmission scenarios, while preserving a complexity which is linear in both the block length and the channel memory. [ABSTRACT FROM AUTHOR]

Sparse Code Multiple Access (SCMA) is a disruptive code-domain non-orthogonal multiple access (NOMA) scheme to enable future massive machine-type communication networks. As an evolved variant of code division multiple access (CDMA), multiple users in SCMA are separated by assigning distinctive sparse codebooks (CBs). Efficient multiuser detection is carried out at the receiver by employing the message passing algorithm (MPA) that exploits the sparsity of CBs to achieve error performance approaching to that of the maximum likelihood receiver. In spite of numerous research efforts in recent years, a comprehensive one-stop tutorial of SCMA covering the background, the basic principles, and new advances, is still missing, to the best of our knowledge. To fill this gap and to stimulate more forthcoming research, we provide a holistic introduction to the principles of SCMA encoding, CB design, and MPA based decoding in a self-contained manner. As an ambitious paper aiming to push the limits of SCMA, we present a survey of advanced decoding techniques with brief algorithmic descriptions as well as several promising directions.

This paper proposes a belief propagation (BP)-based algorithm for sequential detection and estimation of multipath component (MPC) parameters based on radio signals. Under dynamic channel conditions with moving transmitter/receiver, the number of MPCs, the MPC dispersion parameters, and the number of false alarm contributions are unknown and time-varying. We develop a Bayesian model for sequential detection and estimation of MPC dispersion parameters, and represent it by a factor graph enabling the use of BP for efficient computation of the marginal posterior distributions. At each time step, a snapshot-based parametric channel estimator provides parameter estimates of a set of MPCs which are used as noisy measurements by the proposed BP-based algorithm. It performs joint probabilistic data association, and estimation of the time-varying MPC parameters and the mean number of false alarm measurements, by means of the sum-product algorithm rules. The algorithm also exploits amplitude information enabling the reliable detection of “weak” MPCs with very low component signal-to-noise ratios (SNRs). The performance of the proposed algorithm compares well to state-of-the-art algorithms for high SNR MPCs, but it significantly outperforms them for medium or low SNR MPCs. Results using real radio measurements demonstrate the excellent performance of the proposed algorithm in realistic and challenging scenarios. [ABSTRACT FROM AUTHOR]

The design of methods for inference from time sequences has traditionally relied on statistical models that describe the relation between a latent desired sequence and the observed one. A broad family of model-based algorithms have been derived to carry out inference at controllable complexity using recursive computations over the factor graph representing the underlying distribution. An alternative model-agnostic approach utilizes machine learning (ML) methods. Here we propose a framework that combines model-based algorithms and data-driven ML tools for stationary time sequences. In the proposed approach, neural networks are developed to separately learn specific components of a factor graph describing the distribution of the time sequence, rather than the complete inference task. By exploiting stationary properties of this distribution, the resulting approach can be applied to sequences of varying temporal duration. Learned factor graphs can be realized using compact neural networks that are trainable using small training sets, or alternatively, be used to improve upon existing deep inference systems. We present an inference algorithm based on learned stationary factor graphs, which learns to implement the sum-product scheme from labeled data, and can be applied to sequences of different lengths. Our experimental results demonstrate the ability of the proposed learned factor graphs to learn from small training sets to carry out accurate inference for sleep stage detection using the Sleep-EDF dataset, as well as for symbol detection in digital communications with unknown channels. [ABSTRACT FROM AUTHOR]

Based on a generative model (GM) and beliefs over hidden states, the free energy principle (FEP) enables an agent to sense and act by minimizing a free energy bound on Bayesian surprise, i.e., the negative logarithm of the marginal likelihood. Inclusion of desired states in the form of prior beliefs in the GM leads to active inference (ActInf). In this work, we aim to reveal connections between ActInf and stochastic optimal control. We reveal that, in contrast to standard cost and constraint-based solutions, ActInf gives rise to a minimization problem that includes both an information-theoretic surprise term and a model-predictive control cost term. We further show under which conditions both methodologies yield the same solution for estimation and control. For a case with linear Gaussian dynamics and a quadratic cost, we illustrate the performance of ActInf under varying system parameters and compare to classical solutions for estimation and control. [ABSTRACT FROM AUTHOR]

It has been shown that direct target localization in distributed multiple input multiple output (MIMO) radar can outperform indirect localization significantly, but conventional direct localization methods suffer from both high computational complexity and high communication cost. In this work, we address the issues by designing an efficient factor graph based message passing approach to direct localization, which greatly reduces the computational complexity and communication cost. First, a factor graph representation for the problem of direct localization is developed, which, however, involves difficult local functions. Inspired by expectation propagation (EP), we design an iterative method to solve the problem, where both EP and belief propagation (BP) are used to make message passing in the factor graph tractable, leading to a low complexity message passing iterative method. We show that the message passing based method are very suitable for decentralized processing and can be employed in distributed radars with different configurations. Extensive comparisons with state-of-the-art indirect and direct methods are provided, which show that the proposed method can achieve similar performance to the exhaustive search-based direct localization methods while with much lower computational complexity and communication cost, and it outperforms significantly indirect localization methods at low signal to noise ratios. [ABSTRACT FROM AUTHOR]

The state estimation algorithm estimates the values of the state variables based on the measurement model described as the system of equations. Prior to applying the state estimation algorithm, the existence and uniqueness of the solution of the underlying system of equations is determined through the observability analysis. If a unique solution does not exist, the observability analysis defines observable islands and further defines an additional set of equations (measurements) needed to determine a unique solution. For the first time, we utilise factor graphs and Gaussian belief propagation algorithm to define a novel observability analysis approach. The observable islands and placement of measurements to restore observability are identified by following the evolution of variances across the iterations of the Gaussian belief propagation algorithm over the factor graph. Due to sparsity of the underlying power network, the resulting method has the linear computational complexity (assuming a constant number of iterations) making it particularly suitable for solving large-scale systems. The method can be flexibly matched to distributed computational resources, allowing for determination of observable islands and observability restoration in a distributed fashion. Finally, we discuss performances of the proposed observability analysis using power systems whose size ranges between 1354 and 70 000 buses. [ABSTRACT FROM AUTHOR]

This paper addresses the cooperative localization problem for a multiagent system in the framework of belief propagation. In particular, we consider the RoboCup 3D Soccer Simulation scenario, in which the networked agents are able to obtain simulated measurements of the distance and bearing to both known landmarks and teammates as well as the direction of arrival (DOA) of messages received from allies around the field. There are, however, severe communication restrictions between the agents, which limit the size and periodicity of the information that can be exchanged between them. We factorize the joint probability density function of the state of the robots conditioned on all measurements in the network in order to derive the corresponding factor graph representation of the cooperative localization problem. Then we apply the sum-product-algorithm (SPA) and introduce suitable implementations thereof using hybrid Gaussian-Mixture Model (GMM) / Sequential Monte Carlo (SMC) representations of the individual messages that are passed at each network location. Simulated results show that the cooperative estimates for position and orientation converge faster and present smaller errors when compared to the non-cooperative estimates in situations where agents do not observe landmarks for a long period.

We study the behavior of the belief-propagation (BP) algorithm affected by erroneous data exchange in a wireless sensor network (WSN). The WSN conducts a distributed multidimensional hypothesis test over binary random variables. The joint statistical behavior of the sensor observations is modeled by a Markov random field whose parameters are used to build the BP messages exchanged between the sensing nodes. Through linearization of the BP message-update rule, we analyze the behavior of the resulting erroneous decision variables and derive closed-form relationships that describe the impact of stochastic errors on the performance of the BP algorithm. We then develop a decentralized distributed optimization framework to enhance the system performance by mitigating the impact of errors via a distributed linear data-fusion scheme. Finally, we compare the results of the proposed analysis with the existing works and visualize, via computer simulations, the performance gain obtained by the proposed optimization. [ABSTRACT FROM AUTHOR]

We consider the problem of localizing a manned, semiautonomous, or autonomous vehicle in the environment using information coming from the vehicle’s sensors, a problem known as navigation or simultaneous localization and mapping (SLAM) depending on the context. To infer knowledge from sensors’ measurements, while drawing on a priori knowledge about the vehicle’s dynamics, modern approaches solve an optimization problem to compute the most likely trajectory given all past observations, an approach known as smoothing. Improving smoothing solvers is an active field of research in the SLAM community. Most work is focused on reducing computation load by inverting the involved linear system while preserving its sparsity. This article raises an issue that, to the best of our knowledge, has not been addressed yet: standard smoothing solvers require explicitly using the inverse of sensor noise covariance matrices. This means the parameters that reflect the noise magnitude must be sufficiently large for the smoother to properly function. When matrices are close to singular, which is the case when using high-precision modern inertial measurement units (IMUs), numerical issues necessarily arise, especially with 32-bit implementation demanded by most industrial aerospace applications. We discuss these issues and propose a solution that builds upon the Kalman filter to improve smoothing algorithms. We then leverage the results to devise a localization algorithm based on the fusion of IMU and vision sensors. Successful real experiments using an actual car equipped with a tactical grade high-performance IMU and a LiDAR illustrate the relevance of the approach to the field of autonomous vehicles. [ABSTRACT FROM AUTHOR]

This paper presents a mesoscopic traffic flow model that explicitly describes the spatio-temporal evolution of the probability distributions of vehicle trajectories. The dynamics are represented by a sequence of factor graphs, which enable learning of traffic dynamics from limited Lagrangian measurements using an efficient message passing technique. The approach ensures that estimated speeds and traffic densities are non-negative with probability one. The estimation technique is tested using vehicle trajectory datasets generated using an independent microscopic traffic simulator and is shown to efficiently reproduce traffic conditions with probe vehicle penetration levels as little as 10%. The proposed algorithm is also compared with state-of-the-art traffic state estimation techniques developed for the same purpose and it is shown that the proposed approach can outperform the state-of-the-art techniques in terms reconstruction accuracy.

In this paper, we disclose the statistical behavior of the max-product algorithm configured to solve a maximum a posteriori estimation problem in a network of distributed agents. Specifically, we first build a distributed hypothesis test conducted by a max-product iteration over a binary-valued pairwise Markov random field and show that the decision variables obtained are linear combinations of the local log-likelihood ratios observed in the network. Then, we use these linear combinations to formulate the system performance in terms of the false-alarm and detection probabilities. Our findings indicate that, in the hypothesis test concerned, the optimal performance of the max-product algorithm is obtained by an optimal linear data-fusion scheme and the behavior of the max-product algorithm is very similar to the behavior of the sum-product algorithm. Consequently, we demonstrate that the optimal performance of the max-product iteration is closely achieved via a linear version of the sum-product algorithm, which is optimized based on statistics received at each node from its one-hop neighbors. Finally, we verify our observations via computer simulations. [ABSTRACT FROM AUTHOR]

We introduce in this article a distributed factor-graph-based algorithm for anchorless cooperative aircraft localization in a GNSS-denied scenario without fixed infrastructure. The agents use terrain-aided navigation (TAN) to perform local position estimation and exchange messages to improve their position beliefs. Internode communication cost is reduced using a hybrid Gaussian mixture model / sequential Monte Carlo (GMM/SMC) approach. Simulation results show that, even in a partially connected network where only a small part of the agents perform TAN, cooperation yields better results than all aircraft performing TAN independently. [ABSTRACT FROM AUTHOR]

In prior work, we have shown how the basic concepts and terms of quantum mechanics relate to factorizations and marginals of complex-valued quantum mass functions, which are generalizations of joint probability mass functions. In this paper, using quantum mass functions, we discuss the realization of measurements in terms of unitary interactions and marginalizations. It follows that classical measurement results strictly belong to local models, i.e., marginals of more detailed models. Classical variables that are created by marginalization do not exist in the unmarginalized model, and different marginalizations may yield incompatible classical variables. These observations are illustrated by the Frauchiger–Renner paradox, which is analyzed (and resolved) in terms of quantum mass functions. Throughout, the paper uses factor graphs to represent quantum systems/models with multiple measurements at different points in time. [ABSTRACT FROM AUTHOR]

We introduce a new graphical framework for designing quantum error correction codes based on classical principles. A key feature of this graphical language, over previous approaches, is that it is closely related to that of factor graphs or graphical models in classical information theory and machine learning. It enables us to formulate the description of the recently-introduced ‘coherent parity check’ quantum error correction codes entirely within the language of classical information theory. This makes our construction accessible without requiring background in quantum error correction or even quantum mechanics in general. More importantly, this allows for a collaborative interplay where one can design new quantum error correction codes derived from classical codes. [ABSTRACT FROM AUTHOR]

We consider the estimation of correlated Gaussian samples in (correlated) impulsive noise, through message-passing algorithms. The factor graph includes cycles and, due to the mixture of Gaussian (samples and noise) and Bernoulli variables (the impulsive noise switches), the complexity of messages increases exponentially. We first analyze a simple but suboptimal solution, called Parallel Iterative Scheduling. Then we implement both Expectation Propagation — for which numerical stability must be addressed — and a simple variation thereof (called Transparent Propagation) that is inherently stable and simplifies the overall computation. Both algorithms reach a performance close to ideal, practically coinciding with the lower bound on the mean square estimation error. [ABSTRACT FROM AUTHOR]

Factor graphs are important models for succinctly representing probability distributions in machine learning, coding theory, and statistical physics. Several computational problems, such as computing marginals and partition functions, arise naturally when working with factor graphs. Belief propagation is a widely deployed iterative method for solving these problems. However, despite its significant empirical success, several questions regarding the correctness and efficiency of belief propagation remain open. The Bethe approximation is an optimization-based method for approximating the partition functions. While it is known that the stationary points of the Bethe approximation coincide with the fixed points of belief propagation, in general, the relation between the Bethe approximation and the partition function is not well understood. It has been observed that for a few classes of factor graphs, the Bethe approximation gives a lower bound to the partition function, which distinguishes them from the general case, where neither a lower bound nor an upper bound holds universally. This has been rigorously proved for permanents and for attractive graphical models. Here, we consider bipartite factor graphs over binary alphabet and show that if the local constraints satisfy a certain analytic property, the Bethe approximation is a lower bound to the partition function, generalizing an analogous inequality between the permanent and the Bethe permanent of a matrix with non-negative entries. We arrive at this result by viewing the factor graphs through the lens of polynomials, which allows us to reformulate the Bethe approximation as an optimization problem involving polynomials. The sufficient condition for our lower bound property to hold is inspired by the recent developments in the theory of real stable polynomials. We believe that this way of viewing factor graphs and its connection to real stability might lead to a better understanding of belief propagation and factor graphs in general. [ABSTRACT FROM AUTHOR]

We address the challenge of detecting an arbitrary-shaped underwater acoustic signal. Instead of setting a detection threshold, which due to noise transients may result in a high false alarm rate (FAR), our method classifies each measured sample as either “noise” or “signal.” Utilizing a priori knowledge of only the minimal duration of the signal, the decision is made using loopy belief propagation over a factor graph. Numerical simulations and sea experimental results show that our scheme achieves a favorable tradeoff between the Recall and FAR, and noise robustness, which far exceeds that of benchmark schemes. [ABSTRACT FROM AUTHOR]

We present a novel distributed Gauss–Newton method for the non-linear state estimation (SE) model based on a probabilistic inference method called belief propagation (BP). The main novelty of our work comes from applying BP sequentially over a sequence of linear approximations of the SE model, akin to what is done by the Gauss–Newton method. The resulting iterative Gauss–Newton belief propagation (GN-BP) algorithm can be interpreted as a distributed Gauss–Newton method with the same accuracy as the centralized SE, however, introducing a number of advantages of the BP framework. The paper provides extensive numerical study of the GN-BP algorithm, provides details on its convergence behavior, and gives a number of useful insights for its implementation. [ABSTRACT FROM AUTHOR]

Algebraic topology studies topological spaces with the help of tools from abstract algebra. The main focus of this paper is to show that many concepts from algebraic topology can be conveniently expressed in terms of (normal) factor graphs. As an application, we give an alternative proof of a classical duality result of Kramers and Wannier, which expresses the partition function of the 2-D Ising model at a low temperature in terms of the partition function of the 2-D Ising model at a high temperature. Moreover, we discuss analogous results for the 3-D Ising model and the Potts model. [ABSTRACT FROM AUTHOR]

In many practical filter design problems, the exact statistical information of the underlying random processes is not available. One robust filtering approach in these situations is to design an intrinsically Bayesian robust filter that provides optimal solution relative to the prior distribution governing the uncertainty class of all possible joint random process models. In this context, the intrinsically Bayesian robust Kalman filter has been recently introduced for the case that the second-order statistics of the observation and process noise in the state-space model are unknown. However, such a filter does not utilize the additional information embedded in the data being observed. In this paper, we derive the optimal Bayesian Kalman filter, which is optimal over posterior distribution obtained from incorporating data into the prior distribution. This filter has the same recursive structure as that of the classical Kalman filter, except that it is designed relative to the posterior effective noise statistics, which are found by employing the method of factor graphs through formulating the problem of computing the likelihood function as a message passing algorithm. [ABSTRACT FROM AUTHOR]

A factor-graph representation of quantum-mechanical probabilities (involving any number of measurements) is proposed. Unlike standard statistical models, the proposed representation uses auxiliary variables (state variables) that are not random variables. All joint probability distributions are marginals of some complex-valued function $q$ , and it is demonstrated how the basic concepts of quantum mechanics relate to factorizations and marginals of $q$ . [ABSTRACT FROM AUTHOR]

Simultaneous localization and mapping (SLAM) consists in the concurrent construction of a model of the environment (the map), and the estimation of the state of the robot moving within it. The SLAM community has made astonishing progress over the last 30 years, enabling large-scale real-world applications and witnessing a steady transition of this technology to industry. We survey the current state of SLAM and consider future directions. We start by presenting what is now the de-facto standard formulation for SLAM. We then review related work, covering a broad set of topics including robustness and scalability in long-term mapping, metric and semantic representations for mapping, theoretical performance guarantees, active SLAM and exploration, and other new frontiers. This paper simultaneously serves as a position paper and tutorial to those who are users of SLAM. By looking at the published research with a critical eye, we delineate open challenges and new research issues, that still deserve careful scientific investigation. The paper also contains the authors’ take on two questions that often animate discussions during robotics conferences: Do robots need SLAM? and Is SLAM solved? [ABSTRACT FROM AUTHOR]

Stochastic digital backpropagation (SDBP) is an extension of digital backpropagation (DBP) and is based on the maximum a posteriori principle. SDBP takes into account noise from the optical amplifiers in addition to handling deterministic linear and nonlinear impairments. The decisions in SDBP are taken on a symbol-by-symbol (SBS) basis, ignoring any residual memory, which may be present due to nonoptimal processing in SDBP. In this paper, we extend SDBP to account for memory between symbols. In particular, two different methods are proposed: a Viterbi algorithm (VA) and a decision directed approach. Symbol error rate (SER) for memory-based SDBP is significantly lower than the previously proposed SBS-SDBP. For inline dispersion-managed links, the VA-SDBP has up to 10 and 14 times lower SER than DBP for QPSK and 16-QAM, respectively. [ABSTRACT FROM PUBLISHER]

Message-passing algorithms based on belief-propagation (BP) are successfully used in many applications, including decoding error correcting codes and solving constraint satisfaction and inference problems. The BP-based algorithms operate over graph representations, called factor graphs, that are used to model the input. Although in many cases, the BP-based algorithms exhibit impressive empirical results, not much has been proved when the factor graphs have cycles. This paper deals with packing and covering integer programs in which the constraint matrix is zero-one, the constraint vector is integral, and the variables are subject to box constraints. We study the performance of the min-sum algorithm when applied to the corresponding factor graph models of packing and covering linear programmings (LPs). We compare the solutions computed by the min-sum algorithm for packing and covering problems to the optimal solutions of the corresponding LP relaxations. In particular, we prove that if the LP has an optimal fractional solution, then for each fractional component, the min-sum algorithm either computes multiple solutions or the solution oscillates below and above the fraction. This implies that the min-sum algorithm computes the optimal integral solution only if the LP has a unique optimal solution that is integral. The converse is not true in general. For a special case of packing and covering problems, we prove that if the LP has a unique optimal solution that is integral and on the boundary of the box constraints, then the min-sum algorithm computes the optimal solution in pseudopolynomial time. Our results unify and extend recent results for the maximum weight matching problem and for the maximum weight independent set problem. [ABSTRACT FROM PUBLISHER]

We propose a distributed and a dynamic algorithm for a power system state estimation. We model the dependencies among the state vectors of neighboring areas and among the state vectors at different times using a factor graph. We then derive message update rules and use these rules to implement a sum-product message passing algorithm on the graph. In message passing, neighboring areas exchange messages which represent their beliefs about the unknown state vectors based on all the related measurements. These beliefs are then used to compute the posterior distribution of the power system state. In our paper, we represent the messages using a particle based approximation. Such a particle-based representation provides a simple and a computationally feasible method to update the messages in each iteration. Further, it allows us to model the nonlinearities present in the power system, and hence leads to a better performance accuracy compared with the traditional methods that use linear models. We show the accuracy of the proposed method via numerical simulations using the IEEE 14 and 118 bus systems as examples. [ABSTRACT FROM PUBLISHER]

Feldman et al. [11] asked whether the performance of the linear programming (LP) decoder can be improved by adding redundant parity checks to tighten the LP relaxation. We prove in this paper that for low-density parity-check codes, even if we include all redundant parity checks, asymptotically there is no gain in the LP decoder threshold on the binary symmetric channel under certain conditions on the base Tanner graph. First, we show that if the Tanner graph has bounded check-degree and satisfies a condition which we call asymptotic strength, then including high degree redundant parity checks in the LP does not significantly improve the threshold of the LP decoder in the following sense. For each constant $\delta >0$ , there is a constant $k>0$ such that the threshold of the LP decoder containing all redundant checks of degree at most $k$ improves by at most $\delta $ upon adding to the LP all redundant checks of degree larger than $k$ . We conclude that if the graph satisfies an additional condition which we call rigidity, then including all redundant checks does not improve the threshold of the base LP. We call the graph asymptotically strong if the LP decoder corrects a constant fraction of errors even if the log-likelihood-ratios of the correct variables are arbitrarily small. By building on a construction due Feldman et al. [9] and its recent improvement by Viderman [24], we show that asymptotic strength follows from sufficiently large variable-to-check expansion. We also give a geometric interpretation of asymptotic strength in terms pseudocodewords. We call the graph rigid if the minimum weight of a sum of check nodes involving a cycle tends to infinity as the block length tends to infinity. Under the assumptions that the graph girth is logarithmic and the minimum check degree is at least 3, rigidity is equivalent to the nondegeneracy property that adding at least logarithmically many checks does not give a constant weight check. We argue that nondegeneracy is a typical property of random check-regular Tanner graphs. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel detector for single-channel long-haul coherent optical communications, termed stochastic digital backpropagation (SDBP), which takes into account noise from the optical amplifiers in addition to handling deterministic linear and nonlinear impairments. We discuss the design approach behind this detector, which is based on the maximum a posteriori (MAP) principle. As closed-form expressions of the MAP detector are not tractable for coherent optical transmission, we employ the framework of Bayesian graphical models, which allows a numerical evaluation of the proposed detector. Through simulations, we observe that by accounting for nonlinear signal—noise interactions, we achieve a significant improvement in system reach with SDBP over digital backpropagation (DBP) for systems with periodic inline optical dispersion compensation. In uncompensated links with high symbol rates, the performance difference in terms of system reach for SDBP over DBP is small. In the absence of noise, the proposed detector is equivalent to the well-known DBP detector. [ABSTRACT FROM PUBLISHER]

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora , Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e.g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP decoding fails to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph. [ABSTRACT FROM PUBLISHER]

In this paper we provide necessary and sufficient conditions for constituent codes in (multiple) concatenated and graph-based coding schemes to achieve an asymptotically error-free iterative decoding fixed-point if the maximum possible a priori information is available. At least one constituent code in an iterative decoding scheme must satisfy these conditions in order to ensure an asymptotically vanishing bit error probability at the convergence point of the decoder. Our results are proved for arbitrary binary-input symmetric memoryless channels (BISMCs) and thus can be universally applied to many transmission scenarios. Specifically, using a factor graph framework, it is shown that non-inner codes in a serial concatenation or check nodes in generalized LDPC codes achieve perfect extrinsic information if and only if the minimum Hamming distance between codewords is two or greater. For inner codes in a serial concatenation, constituent codes in a parallel concatenation, or variable nodes in doubly-generalized LDPC codes the corresponding encoder condition for acquiring perfect extrinsic information is an infinite codeword weight for a weight-one input sequence. For this case we provide a general proof which holds for all linear encoders and BISMCs. We also show that these results can improve the performance of concatenated coding schemes. [ABSTRACT FROM PUBLISHER]

Clock synchronization has become an indispensable requirement in wireless sensor networks due to its central importance in vital network operations such as data fusion and duty cycling, and has attracted considerable research interest recently. Assuming exponentially distributed random delays in a two-way message exchange mechanism, this work proposes a network-wide clock synchronization algorithm using a factor graph representation of the network. Message passing using the max-product algorithm is adopted to derive the update rules for the proposed iterative procedure. A closed form solution is obtained for each node's belief about its clock offset at each iteration. Simulation results show that the application of the proposed message passing-based network-wide clock synchronization algorithm provides convergent estimates for both regular cycle-free and random topologies. Moreover, the mean square error (MSE) performance of the proposed algorithm is also compared with the Cramer-Rao bound (CRB) for small example networks, which further highlights the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The problem of designing good space–time block codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well-known technique of decoding STBCs as conditional ML (CML) decoding . In this paper, we introduce a new framework to construct ML decoders for STBCs based on the generalized distributive law (GDL) and the factor-graph-based sum–product algorithm. We say that an STBC is fast GDL decodable if the order of GDL decoding complexity of the code, with respect to the constellation size M, is strictly less than M^\lambda, where \lambda is the number of independent symbols in the STBC. We give sufficient conditions for an STBC to admit fast GDL decoding, and show that both multigroup and conditionally multigroup decodable codes are fast GDL decodable. For any STBC, whether fast GDL decodable or not, we show that the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from cyclic division algebras which is not multigroup or conditionally multigroup decodable, the GDL decoder provides about 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only half as complex as the CML decoder. [ABSTRACT FROM PUBLISHER]

The way of multisensory data integration is a crucial step of any data fusion method. Different physical types of sensors (optic, thermal, acoustic, or radar) with different resolutions, and different types of GIS digital data (elevation, vector map) require a proper method for data integration. Incommensurability of the data may not allow to use conventional statistical methods for fusion and processing of the data. A correct and established way of multisensory data integration is required to deal with such incommensurable data as the employment of an inappropriate methodology may lead to errors in the fusion process. To perform a proper multisensory data fusion several strategies were developed (Bayesian, linear (log linear) opinion pool, neural networks, fuzzy logic approaches). Employment of these approaches is motivated by weighted consensus theory, which lead to fusion processes that are correctly performed for the variety of data properties. [ABSTRACT FROM PUBLISHER]

The paper proposes Monte Carlo algorithms for the computation of the information rate of 2-D source/channel models. The focus of the paper is on binary-input channels with constraints on the allowed input configurations. The problem of numerically computing the information rate, and even the noiseless capacity, of such channels has so far remained largely unsolved. Both problems can be reduced to computing a Monte Carlo estimate of a partition function. The proposed algorithms use tree-based Gibbs sampling and multilayer (multitemperature) importance sampling. The viability of the proposed algorithms is demonstrated by simulation results. [ABSTRACT FROM AUTHOR]

In this paper, a graph-based soft iterative receiver (GSIR) for fast fading channels is investigated. Soft channel estimation as well as soft-output data detection are jointly accomplished via Bayesian inference over a general factor graph. The key feature is a transfer node which enables information flow from one channel node to adjacent channel nodes. The performance characteristics of this receiver is investigated via an EXIT chart analysis and simulation results. Particular emphasis is on a proper channel code design. The algorithm is universally applicable to arbitrary (bijective and non-bijective) modulation formats and can easily be extended to multi-dimensional channel estimation. [ABSTRACT FROM PUBLISHER]

The problem of clock offset estimation in a two-way timing message exchange regime is considered when the likelihood function of the observation time stamps is Gaussian, exponential, or log-normally distributed. A parameterized solution to the maximum likelihood (ML) estimation of clock offset is analytically obtained, which differs from the earlier approaches where the likelihood function is maximized graphically. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using a factor graph representation of the posterior density. Message passing using the max-product algorithm yields an exact expression for the Bayesian inference problem. Several lower bounds on the variance of an estimator are derived for arbitrary exponential family distributed likelihood functions which, while serving as stepping stones to benchmark the performance of the proposed clock offset estimators, can be useful in their own right in classical as well Bayesian parameter estimation theory. To corroborate the theoretical findings, extensive simulation results are discussed for classical as well as Bayesian estimators in various scenarios. It is observed that the performance of the proposed estimators is fairly close to the fundamental limits established by the lower bounds. [ABSTRACT FROM PUBLISHER]

In this paper, we deal with low-complexity near-optimal detection/equalization in large-dimension multiple-input multiple-output inter-symbol interference (MIMO-ISI) channels using message passing on graphical models. A key contribution in the paper is the demonstration that near-optimal performance in MIMO-ISI channels with large dimensions can be achieved at low complexities through simple yet effective simplifications/approximations, although the graphical models that represent MIMO-ISI channels are fully/densely connected (loopy graphs). These include 1) use of Markov random field (MRF)-based graphical model with pairwise interaction, in conjunction with message damping, and 2) use of factor graph (FG)-based graphical model with Gaussian approximation of interference (GAI). The per-symbol complexities are O(K^2nt^2) and O(Knt) for the MRF and the FG with GAI approaches, respectively, where K and nt denote the number of channel uses per frame, and number of transmit antennas, respectively. These low-complexities are quite attractive for large dimensions, i.e., for large Knt. From a performance perspective, these algorithms are even more interesting in large-dimensions since they achieve increasingly closer to optimum detection performance for increasing Knt. Also, we show that these message passing algorithms can be used in an iterative manner with local neighborhood search algorithms to improve the reliability/performance of M-QAM symbol detection. [ABSTRACT FROM PUBLISHER]

It has been recently shown that the expectation-maximization (EM) algorithm may be viewed as message passing in factor graphs, and in particular, for a linear Gaussian system (with unknown coefficients), the EM algorithm may be purely implemented with Gaussian message passing. In this work, with a Gaussian assumption of the data symbols and a Forney-style factor graph representation for single-carrier transmission over frequency selective channels, a Gaussian message passing EM approach for joint channel estimation and detection is developed. The complexity of the proposed approach grows logarithmically with the length of the observation vector, enabling an efficient handling of (quasi-static and time-varying) frequency selective channels with a large number of channel taps. [ABSTRACT FROM PUBLISHER]

A frequency domain state-space approach to the least squares (LS) estimation for finite impulse response (FIR) system identification is proposed by exploiting the Toeplitz structure of the data matrix, leading to two low-complexity FFT (fast Fourier transform)-based unbiased recursive estimators. The proposed recursive estimators are applied to the smoothing estimation of time-varying frequency selective channels in turbo equalization systems, and channel estimation approaches with complexity \cal O(logL) per symbol are developed, where L is the number of channel taps. [ABSTRACT FROM PUBLISHER]