Sparse Code Division Multiple Access (CDMA), a variation on the standard CDMA method in which the spreading (signature) matrix contains only a relatively small number of non-zero elements, is presented and analysed using methods of statistical physic
s. The analysis provides results on the performance of maximum likelihood decoding for sparse spreading codes in the large system limit. We present results for both cases of regular and irregular spreading matrices for the binary additive white Gaussian noise channel (BIAWGN) with a comparison to the canonical (dense) random spreading code.
Variational inference is a powerful concept that underlies many iterative approximation algorithms; expectation propagation, mean-field methods and belief propagations were all central themes at the school that can be perceived from this unifying framework. The lectures of Manfred Opper introduce the archetypal example of Expectation Propagation, before establishing the connection with the other approximation methods. Corrections by expansion about the expectation propagation are then explained. Finally some advanced inference topics and applications are explored in the final sections.
Approximating marginals of a graphical model is one of the fundamental problems in the theory of networks. In a recent paper a method was shown to construct a variational free energy such that the linear response estimates, and maximum entropy estimates (for beliefs) are in agreement, with implications for direct and inverse Ising problems[1]. In this paper we demonstrate an extension of that method, incorporating new information from the response matrix, and we recover the adaptive-TAP equations as the first order approximation[2]. The method is flexible with respect to applications of the cluster variational method, special cases of this method include Naive Mean Field (NMF) and Bethe. We demonstrate that the new framework improves estimation of marginals by orders of magnitude over standard implementations in the weak coupling limit. Beyond the weakly coupled regime we show there is an improvement in a model where the NMF and Bethe approximations are known to be poor for reasons of frustration and short loops.
Ground state entropy of the network source location problem is evaluated at both the replica symmetric level and one-step replica symmetry breaking level using the entropic cavity method. The regime that is a focus of this study, is closely related to the vertex cover problem with randomly quenched covered nodes. The resulting entropic message passing inspired decimation and reinforcement algorithms are used to identify the optimal location of sources in single instances of transportation networks. The conventional belief propagation without taking the entropic effect into account is also compared. We find that in the glassy phase the entropic message passing inspired decimation yields a lower ground state energy compared to the belief propagation without taking the entropic effect. Using the extremal optimization algorithm, we study the ground state energy and the fraction of frozen hubs, and extend the algorithm to collect statistics of the entropy. The theoretical results are compared with the extremal optimization results.
This paper develops results for the next nearest neighbour Ising model on random graphs. Besides being an essential ingredient in classic models for frustrated systems, second neighbour interactions interactions arise naturally in several applications such as the colour diversity problem and graphical games. We demonstrate ensembles of random graphs, including regular connectivity graphs, that have a periodic variation of free energy, with either the ratio of nearest to next nearest couplings, or the mean number of nearest neighbours. When the coupling ratio is integer paramagnetic phases can be found at zero temperature. This is shown to be related to the locked or unlocked nature of the interactions. For anti-ferromagnetic couplings, spin glass phases are demonstrated at low temperature. The interaction structure is formulated as a factor graph, the solution on a tree is developed. The replica symmetric and energetic one-step replica symmetry breaking solution is developed using the cavity method. We calculate within these frameworks the phase diagram and demonstrate the existence of dynamical transitions at zero temperature for cases of anti-ferromagnetic coupling on regular and inhomogeneous random graphs.
Typical properties of computing circuits composed of noisy logical gates are studied using the statistical physics methodology. A growth model that gives rise to typical random Boolean functions is mapped onto a layered Ising spin system, which facilitates the study of their ability to represent arbitrary formulae with a given level of error, the tolerable level of gate-noise, and its dependence on the formulae depth and complexity, the gates used and properties of the function inputs. Bounds on their performance, derived in the information theory literature via specific gates, are straightforwardly retrieved, generalized and identified as the corresponding typical-case phase transitions. The framework is employed for deriving results on error-rates, function-depth and sensitivity, and their dependence on the gate-type and noise model used that are difficult to obtain via the traditional methods used in this field.
Compressed sensing of sparse sources can be improved by incorporating prior knowledge of the source. In this paper we demonstrate a method for optimal selection of weights in weighted $L_1$ norm minimization for a noiseless reconstruction model, and show the improvements in compression that can be achieved.
Methods for understanding classical disordered spin systems with interactions conforming to some idealized graphical structure are well developed. The equilibrium properties of the Sherrington-Kirkpatrick model, which has a densely connected structure, have become well understood. Many features generalize to sparse Erdos-Renyi graph structures above the percolation threshold, and to Bethe lattices when appropriate boundary conditions apply. In this paper we consider spin states subject to a combination of sparse strong interactions with weak dense interactions, which we term a composite model. The equilibrium properties are examined through the replica method, with exact analysis of the high temperature paramagnetic, spin glass and ferromagnetic phases by perturbative schemes. We present results of a replica symmetric variational approximations where perturbative approaches fail at lower temperature. Results demonstrate novel reentrant behaviors from spin glass to ferromagnetic phases as temperature is lowered, including transitions from replica symmetry broken to replica symmetric phases. The nature of high temperature transitions is found to be sensitive to the connectivity profile in the sparse sub-graph, with regular connectivity a discontinuous transition from the paramagnetic to ferromagnetic phases is apparent.
Code Division Multiple Access (CDMA) in which the spreading code assignment to users contains a random element has recently become a cornerstone of CDMA research. The random element in the construction is particular attractive as it provides robustness and flexibility in utilising multi-access channels, whilst not making significant sacrifices in terms of transmission power. Random codes are generated from some ensemble, here we consider the possibility of combining two standard paradigms, sparsely and densely spread codes, in a single composite code ensemble. The composite code analysis includes a replica symmetric calculation of performance in the large system limit, and investigation of finite systems through a composite belief propagation algorithm. A variety of codes are examined with a focus on the high multi-access interference regime. In both the large size limit and finite systems we demonstrate scenarios in which the composite code has typical performance exceeding sparse and dense codes at equivalent signal to noise ratio.
