Search

This chapter provides a gentle introduction to some modern topics in high-dimensional statistics, statistical learning, and signal processing for an audience who may not have any previous background in these areas. The pedagogical path of the chapter is to first connect recent advances in these fields to the basic topics of statistics, such as estimation, regression, and bias-variance trade-off, as well as to classical—although non-elementary—developments such as sparse estimation and wavelet denoising. After this theoretical introduction, the chapter presents results from more recent research, including discussions on sparse linear regression, the theory of compressed sensing as well as sparse signal reconstruction, approximate message passing, and also sparse and low-rank matrix factorization problems with applications to hidden clique discovery within large networks.

This chapter revisits the problem of decoding low density parity check (LDPC) codes. The maximum a posteriori probability (MAP) decoding of a bit is described as a statistical inference problem, and belief propagation is applied to its solution. The corresponding message passing procedure is analyzed in details, and the threshold noise level below which this ‘iterative decoding’ achieves perfect decoding is derived. The chapter ends with a general discussion of the relation between message passing and optimal (exact symbol MAP) decoding.

This chapter discusses the use of message passing techniques in a combinatorial optimization problem assignment. Given N ‘agents’ and N ‘jobs’, and the cost matrix E(i,j) for having job i executed by agent j, the problem is to find the lowest cost assignment of jobs to agents. On the algorithmic side, the Min-Sum variant of Belief Propagation is shown to converge to an optimal solution in polynomial time. On the probabilistic side, the large N limit of random instances, when the costs E(i,j) are independent uniformly random variables, is studied analytically. The cost of the optimal assignment is first computed heuristically within the replica symmetric cavity method, giving the celebrated zeta(2) result. This study is confirmed by a rigorous combinatorial argument which provides a proof of the Parisi and Coppersmith–Sorkin conjectures.

In the past twenty-five years, the replica method has evolved into a rather sophisticated tool for attacking theoretical problems as diverse as spin glasses, protein folding, vortices in superconductors, combinatorial optimization, etc. Although it is not be the main tool of this book, it is nevertheless instructive to have some knowledge of replicas: the replica method is a non-trivial construction which is surprisingly powerful. Several of its most important predictions have been confirmed rigorously through alternative approaches. This chapter gives a compact account of the replica method. It describes the close connection between replica symmetry breaking and the Poisson–Dirichlet process, and it emphasizes the role played by ‘overlaps’ between replicas.

Low-density parity-check (LDPC) codes are among the most efficient error correcting codes in use. This chapter introduces an important family of LDPC ensembles, based on random factor graphs, and studies some of their basic properties. It focuses on performances under optimal decoding, when no constraint is imposed on the computational complexity of the decoding procedure. Bounds in their performances are derived through an analysis of the geometric properties of their codebook. In particular, it shows that appropriately chosen LDPC ensembles allow for communication reliably at rates close to Shannon's capacity.

The emerging field that has been described in this book is remarkably coherent, but it also opens up a number of challenges. This chapter provides a synthetic description of such challenges, as well as a survey of recent progress. The ambition is to set an agenda for this new research field. Three research directions are emphasized. Firstly, achieving a better qualitative understanding of 1RSB glass phase. What is a pure state decomposition? What is the relation between emergence of long range correlations and clustering of the probability measure? Secondly, developing methods for the full-RSB phase. Where does such a phase emerge in sparse graphical models? Does the cavity method have a compact formulation? Thirdly, understanding algorithmic implications. There is large evidence that phase transitions affect the performances of algorithms. However, a crisp and general formulation is still missing.

This chapter provides an elementary introduction to some basic concepts in theoretical computer science. It includes basic notions of graph theory and an informal introduction to computational complexity, presenting the basic classes P, NP, and NP-complete. These notions are illustrated by discussions of the minimal spanning tree and satisfiability problems, and by applications from statistical physics (spin glasses and maximum cuts), and from coding theory (decoding complexity).

The mathematical structure highlighted in this chapter by the factor graph representation is the locality of probabilistic dependencies between variables. Locality also emerges in many problems of probabilistic inference, which provides another unifying view of the field. This chapter describes coding theory, statistical physics, and combinatorial optimization as inference problems. It also explores one generic inference method, the use of Monte Carlo Markov chains (MCMC) in order to sample from complex probabilistic models. Many of the difficulties encountered in decoding, in constraint satisfaction problems, or in glassy phases, are connected to a dramatic slowing down of MCMC dynamics, which is explored through simple numerical experiments on some examples.

The three fields that form the subject of this book all deal with large sets of random variables. Not surprisingly, they possess common underlying structures and techniques. This chapter describes some of them, insisting on the mathematical structures. It discusses on one hand large deviations, Sanov's theorem, and asymptotic equipartition. On the other hand, it introduces Markov chains for Monte Carlo computations, and its application to optimization with simulated annealing.

The random energy model is probably the simplest statistical physics model of a disordered system which exhibits a phase transition. This chapter studies its thermodynamic properties and its phase transition, and describes in detail the condensation phenomenon at work in the low temperature phase. The same mathematical structure and techniques appear in a large number of contexts. This is witnessed by the examples from information theory and combinatorial optimization presented in the next two chapters.

Number partitioning is one of the most basic optimization problems. It is very easy to state: ‘Given the values of N assets, is there a fair partition of them into two sets?’ Nevertheless, it is very difficult to solve: it belongs to the NP-complete category, and the known heuristics are often not very good. It is also a problem with practical applications, for instance in multiprocessor scheduling. This chapter focuses on a particularly difficult case: the partitioning of a list of independent uniformly distributed random numbers. It discusses the phase transition occurring when the range of numbers varies, and shows that low cost configurations — the ones with a small unbalance between the two sets — can be seen as independent energy levels. Hence the model behaves analogously to the Random Energy Model.

Probabilistic systems involving a large number of simple variables with mutual dependencies appear recurrently in several fields of science. It is often the case that such dependencies can be factorized in a non-trivial way, and distinct variables interact only ‘locally’. This important structural property plays a crucial role. It is described here in a graphical language — the one of factor graphs. Ensembles of probability distributions naturally map to ensemble of random graphs, or hypergraphs. Several basic properties of these ensembles are discussed, from the appearance of a giant component to the motifs appearing in their local structure. The graph description is a necessary background for the understanding of message passing algorithms.

This chapter studies two problems of statistical physics: the ferromagnet and the spin glass, on large random graphs with fixed degree profile. It describes the use of the replica symmetric cavity method in this context, and studies its stability. The analysis relies on physicists methods, without any attempt at being rigorous. It provides a complete solution of the ferromagnetic problem at all temperatures. In the spin glass case, the replica symmetric solution is asymptotically correct in the high temperature ‘paramagnetic’ phase, but it turns out to be wrong in the spin glass phase. The phase transition temperature can be computed exactly.

This chapter studies the simplest error correcting code ensemble, introduced by Shannon, in which codewords are independent random points on the hypercube. This code achieves optimal error correcting performances, and offers a constructive proof of the ‘direct’ part of the channel coding theorem: it is possible to communicate with vanishing error probability as long as the communication rate is smaller than the channel capacity. It is also very closely related to the Random Energy Model.

This chapter introduces some of the basic concepts of information theory, as well as the definitions and notations of probability theory that are used throughout the book. It defines the fundamental notions of entropy, relative entropy, and mutual information. It also presents the main questions of information theory: data compression and data transmission. Finally, it offers a brief introduction to error correcting codes and Shannon's theory.

In the limit of large block-length, iteratively decoded low density parity check (LDPC) codes exhibit two phase transitions. At low noise, the bit error rate under belief propagation decoding vanishes. In a second regime belief propagation decoding fails but maximum a posteriori probability (MAP) decoding succeeds. Finally above a second noise threshold decoding is impossible even with unbounded computational power. This chapter develops a common approach to these two transitions, through the study of ‘metastable’ configurations of the bits that are not codewords. It identifies the belief propagation phase transition with the onset of a dynamical glass phase, detected through the one step replica symmetry breaking approach. This is a structural phenomenon that spoils the performance of a large variety of decoders, from general iterative message passing schemes to simulated annealing.

Solving a system of linear equations over a finite field is arguably one of the most fundamental operations in mathematics. This chapter considers a specific ensemble of random linear systems over Boolean variables, named XORSAT, and discusses the structure of its set of solutions. In large instances, the affine subspace of solutions can exhibit a remarkably rich geometrical structure. When the ratio of equations to variables is increased, the system first gets into an intermediate phase where solutions cluster in many well separated regions of the hypercube. Then it encounters a second phase transition and gets into an ‘UNSAT’ phase where the probability of existence of a solution vanishes. The study uses belief propagation equations, and a combinatorial analysis of the 2-core in the associated factor graph.

This chapter introduces the basic concepts of statistical physics. The restrictive point of view adopted here keeps to classical (non-quantum) statistical physics and treats it as a branch of probability theory. The mechanism of phase transitions is described in the context of magnetic systems: ferromagnets and spin glasses.

This chapter discusses a general method for approximating marginals of large graphical models. This powerful technique has been discovered independently in various fields: statistical physics (under the name ‘Bethe Peierls approximation’), coding theory (‘sum-product’ and ‘min-sum’ algorithms), and artificial intelligence (‘belief propagation’). It is based on an exchange of messages between variables and factors, along the edges of the factor graph. These messages are interpreted as probability distributions for the variable in a graph where a cavity has been dug. The chapter also discusses the statistical analysis of these messages in large random graphical models: density evolution and the replica symmetric cavity method.

This chapter studies an ensemble of random satisfiability problems, ‘random K-satisfiability’ (K-SAT). Applying the 1RSB cavity method, it first derives the phase diagram in the limit of large N, in particular the location of the SAT-UNSAT threshold. Within the SAT phase, the chapter focuses on the intermediate clustered phase close, and computes the number of clusters to leading exponential order in N. The application of survey propagation to this problem is then described. Combined with a simple decimation procedure, the chapter provides an efficient method for finding satisfiable assignments in the clustered phase. The whole chapter is based on heuristic arguments. There is not yet any rigorous proof of the results presented, neither concerning the phase diagram, nor the convergence properties of message passing algorithms and their use in decimation procedures.

This chapter describes random magnetic systems, ‘spin glasses’, by special random ensembles of factor graphs. It also studies the glass phase, characterized by a freezing of the spins, in the framework of equilibrium statistical physics. It describes the two types of spin glass phase transitions that have been encountered in mean field models, and introduces the relevant order parameters to describe them based on the notion of overlap. Special attention is given to the concept of frustration — a basic ingredient of spin glasses — which is discussed in conjunction with gauge transformations.

Because of Cook's theorem, satisfiability lies at the heart of computational complexity theory. This chapter presents some selected research directions, focusing on ensembles of random satisfiability instances. When the density of constraints is increased, a phase transition between a SAT and an UNSAT phase take place. Properly tuned ensembles with a density close to the transition point provide a generator of particularly hard instances. The nature of this transition is discussed, and bounds on the critical density are obtained. On the algorithmic side, the discussion focuses on exhaustive search algorithms based on tree-search, and on random walk procedures.