Error-correcting codes on a Bethe-like lattice

We analyse Gallager codes by employing a simple mean-field approximation that distorts the model geometry and preserves important interactions between sites. The method naturally recovers the probability propagation decoding algorithm as a minimization of a proper free-energy. We find a thermodynamical phase transition that coincides with information theoretical upper-bounds and explain the practical code performance in terms of the free-energy landscape.

Finite-connectivity spin-glass phase diagrams and low-density parity check codes

We obtain phase diagrams of regular and irregular finite-connectivity spin glasses. Contact is first established between properties of the phase diagram and the performance of low-density parity check (LDPC) codes within the replica symmetric (RS) ansatz. We then study the location of the dynamical and critical transition points of these systems within the one step replica symmetry breaking theory (RSB), extending similar calculations that have been performed in the past for the Bethe spin-glass problem. We observe that the location of the dynamical transition line does change within the RSB theory, in comparison with the results obtained in the RS case. For LDPC decoding of messages transmitted over the binary erasure channel we find, at zero temperature and rate R=14, an RS critical transition point at pc 0.67 while the critical RSB transition point is located at pc 0.7450±0.0050, to be compared with the corresponding Shannon bound 1-R. For the binary symmetric channel we show that the low temperature reentrant behavior of the dynamical transition line, observed within the RS ansatz, changes its location when the RSB ansatz is employed; the dynamical transition point occurs at higher values of the channel noise. Possible practical implications to improve the performance of the state-of-the-art error correcting codes are discussed. © 2006 The American Physical Society.

Resource allocation in sparse graphs

Resource allocation in sparsely connected networks, a representative problem of systems with real variables, is studied using the replica and Bethe approximation methods. An efficient distributed algorithm is devised on the basis of insights gained from the analysis and is examined using numerical simulations,showing excellent performance and full agreement with the theoretical results. The physical properties of the resource allocation model are discussed.

Typical behavior of relays in communication channels

The typical behavior of the relay-without-delay channel under low-density parity-check coding and its multiple-unit generalization, termed the relay array, is studied using methods of statistical mechanics. A demodulate-and- forward strategy is analytically solved using the replica symmetric ansatz which is exact in the system studied at Nishimori's temperature. In particular, the typical level of improvement in communication performance by relaying messages is shown in the case of a small and a large number of relay units. © 2007 The American Physical Society.

Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach

Using methods of statistical physics, we study the average number and kernel size of general sparse random matrices over GF(q), with a given connectivity profile, in the thermodynamical limit of large matrices. We introduce a mapping of GF(q) matrices onto spin systems using the representation of the cyclic group of order q as the q-th complex roots of unity. This representation facilitates the derivation of the average kernel size of random matrices using the replica approach, under the replica symmetric ansatz, resulting in saddle point equations for general connectivity distributions. Numerical solutions are then obtained for particular cases by population dynamics. Similar techniques also allow us to obtain an expression for the exact and average number of random matrices for any general connectivity profile. We present numerical results for particular distributions.

Equilibrium properties of disordered spin models with two-scale interactions

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 Erdös- Rényi 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 replica symmetric variational approximations, where perturbative approaches fail at lower temperature. Results demonstrate re-entrant 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 subgraph, with regular connectivity a discontinuous transition from the paramagnetic to ferromagnetic phases is apparent.

Inference and optimization of real edges on sparse graphs:A statistical physics perspective

Inference and optimization of real-value edge variables in sparse graphs are studied using the Bethe approximation and replica method of statistical physics. Equilibrium states of general energy functions involving a large set of real edge variables that interact at the network nodes are obtained in various cases. When applied to the representative problem of network resource allocation, efficient distributed algorithms are also devised. Scaling properties with respect to the network connectivity and the resource availability are found, and links to probabilistic Bayesian approximation methods are established. Different cost measures are considered and algorithmic solutions in the various cases are devised and examined numerically. Simulation results are in full agreement with the theory. © 2007 The American Physical Society.

Inference by replication in densely connected systems

An efficient Bayesian inference method for problems that can be mapped onto dense graphs is presented. The approach is based on message passing where messages are averaged over a large number of replicated variable systems exposed to the same evidential nodes. An assumption about the symmetry of the solutions is required for carrying out the averages; here we extend the previous derivation based on a replica-symmetric- (RS)-like structure to include a more complex one-step replica-symmetry-breaking-like (1RSB-like) ansatz. To demonstrate the potential of the approach it is employed for studying critical properties of the Ising linear perceptron and for multiuser detection in code division multiple access (CDMA) under different noise models. Results obtained under the RS assumption in the noncritical regime give rise to a highly efficient signal detection algorithm in the context of CDMA; while in the critical regime one observes a first-order transition line that ends in a continuous phase transition point. Finite size effects are also observed. While the 1RSB ansatz is not required for the original problems, it was applied to the CDMA signal detection problem with a more complex noise model that exhibits RSB behavior, resulting in an improvement in performance. © 2007 The American Physical Society.

Statistical physics of error-correcting codes

In this thesis we use statistical physics techniques to study the typical performance of four families of error-correcting codes based on very sparse linear transformations: Sourlas codes, Gallager codes, MacKay-Neal codes and Kanter-Saad codes. We map the decoding problem onto an Ising spin system with many-spins interactions. We then employ the replica method to calculate averages over the quenched disorder represented by the code constructions, the arbitrary messages and the random noise vectors. We find, as the noise level increases, a phase transition between successful decoding and failure phases. This phase transition coincides with upper bounds derived in the information theory literature in most of the cases. We connect the practical decoding algorithm known as probability propagation with the task of finding local minima of the related Bethe free-energy. We show that the practical decoding thresholds correspond to noise levels where suboptimal minima of the free-energy emerge. Simulations of practical decoding scenarios using probability propagation agree with theoretical predictions of the replica symmetric theory. The typical performance predicted by the thermodynamic phase transitions is shown to be attainable in computation times that grow exponentially with the system size. We use the insights obtained to design a method to calculate the performance and optimise parameters of the high performance codes proposed by Kanter and Saad.

Intercultural transfer and artistic innovation:German musicians in Victorian Britain

Throughout the nineteenth century, German classical music production was an aesthetic point of reference for British concert audiences. As a consequence, a sizeable number of German musicians were to be found in Britain as performers, conductors, teachers, musicologists and managers. They acted as agents of intercultural transfer, disseminating performance and organisational practices which had a transformative effect on British musical life. This article moves away from a focus on high-profile visiting artists such as Mendelssohn Bartholdy or Wagner and argues that the extent to which transfer took place can be better assessed by concentrating on the cohort of those artists who remained permanently. Some of these are all but forgotten today, but were household names in Victorian Britain. The case studies have been selected for the range of genres they represent and include Joseph Mainzer (choral singing), Carl Rosa (opera), August Manns, Carl Hallé and Julius Seligmann (orchestral music), and Friedrich Niecks (musicology). On a theoretical level, the concept of ‘intercultural transfer’ is applied in order to determine aspects such as diffusion, adaptation or sustainability of artistic elements within the new cultural context. The approach confirms that ‘national’ cultures do not develop indigenously but always through cross-national interaction. Während des neunzehnten Jahrhunderts war die klassische Musikszene Deutschlands ästhetischer Bezugpunkt für das britische Konzertpublikum. Dies hatte zur Folge, dass vermehrt Deutsche als Musiker, Dirigenten, Lehrer, Musikwissenschaftler und Manager in Großbritannien tätig wurden. Sie fungierten als Vermittler interkulturellen Transfers, indem sie aufführungs- und organisationstechnische Praktiken verbreiteten und damit zu einer Transformation des britischen Musiklebens beitrugen. Vorliegender Artikel konzentriert sich weniger auf bekannte Künstler mit kurzfristigen Engagements (z. B. Mendelssohn Bartholdy, Wagner), und argumentiert vielmehr, dass sich das Ausmaß des Transfers besser über solche Musiker feststellen lässt, die sich längerfristig ansiedelten. Einige davon waren allgemein bekannte Persönlichkeiten im Königreich, sind heute aber vergessen. Die Auswahl der Fallstudien gibt einen Überblick über verschiedene Gattungen und beinhaltet Joseph Mainzer (Chorgesang), Carl Rosa (Oper), August Manns, Carl Hallé und Julius Seligmann (Orchestermusik), sowie Friedrich Niecks (Musikwissenschaft). Auf der Theorieebene wird das Konzept des ‘interkulturellen Transfers’ herangezogen, um Aspekte wie Diffusion, Anpassung oder Nachhaltigkeit künstlerischer Elemente im neuen kulturellen Kontext zu beleuchten. Der Ansatz bestätigt, dass sich ‘nationale’ Kulturen nicht indigen entwickeln sondern immer im Austausch mit anderen Kulturen

Network optimisation - A statistical physics perspective

Inference and optimisation of real-value edge variables in sparse graphs are studied using the tree based Bethe approximation optimisation algorithms. Equilibrium states of general energy functions involving a large set of real edge-variables that interact at the network nodes are obtained for networks in various cases. These include different cost functions, connectivity values, constraints on the edge bandwidth and the case of multiclass optimisation.