In this paper we extend our previous work on the stochastic block model, a commonly used generative model for social and biological networks, problem of inferring functional groups or communities from topology network. We use cavity method statistical physics to obtain an asymptotically exact analysis phase diagram. describe in detail properties detectability-undetectability transition easy-hard community detection problem. Our translates naturally into belief propagation algorithm group...

Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these suboptimal, some cases completely failing detect communities even when other such as belief propagation can do so. Here we introduce a new class spectral based on non-backtracking walk directed edges graph. The spectrum this operator is much better-behaved than that adjacency matrix or commonly used matrices, maintaining strong separation...

An instance of a random constraint satisfaction problem defines subset 𝒮 (the set solutions) large product space X N assignments). We consider two prototypical ensembles (random k -satisfiability and q -coloring regular graphs) study the uniform measure with support on S . As number constraints per variable increases, this first decomposes into an exponential pure states (“clusters”) subsequently condensates over largest such states. Above condensation point, mass carried by n follows...

We present an asymptotically exact analysis of the problem detecting communities in sparse random networks generated by stochastic block models. Using cavity method statistical physics and its relationship to belief propagation, we unveil a phase transition from regime where can infer correct group assignments nodes one these groups are undetectable. Our approach yields optimal inference algorithm for modules, including both assortative disassortative functional assessing their significance,...

We consider the problem of coloring vertices a large sparse random graph with given number colors so that no adjacent have same color. Using cavity method, we present detailed and systematic analytical study space proper colorings (solutions). show for fixed as average vertex degree (number constraints) increases, set solutions undergoes several phase transitions similar to those observed in mean field theory glasses. First, at clustering transition, entropically dominant part decomposes...

Compressed sensing is triggering a major evolution in signal acquisition. It consists sampling sparse at low rate and later using computational power for its exact reconstruction, so that only the necessary information measured. Currently used reconstruction techniques are, however, limited to acquisition rates larger than true density of signal. We design new procedure which able reconstruct exactly with number measurements approaches theoretical limit large systems. based on joint use...

Compressed sensing is a signal processing method that acquires data directly in compressed form. This allows one to make less measurements than what was considered necessary record signal, enabling faster or more precise measurement protocols wide range of applications. Using an interdisciplinary approach, we have recently proposed [arXiv:1109.4424] strategy be performed at acquisition rates approaching the theoretical optimal limits. In this paper, give thorough presentation our and...

Many questions of fundamental interest in today's science can be formulated as inference problems: some partial, or noisy, observations are performed over a set variables and the goal is to recover, infer, values based on indirect information contained measurements. For such problems, central scientific are: Under what conditions measurements sufficient for satisfactory possible? What most efficient algorithms this task? A growing body work has shown that often we understand locate these...

Generalized linear models (GLMs) are used in high-dimensional machine learning, statistics, communications, and signal processing. In this paper we analyze GLMs when the data matrix is random, as relevant problems such compressed sensing, error-correcting codes, or benchmark neural networks. We evaluate mutual information (or “free entropy”) from which deduce Bayes-optimal estimation generalization errors. Our analysis applies to limit where both number of samples dimension large their ratio...

Recent ideas based on the properties of assemblies frictionless particles in mechanical equilibrium provide a perspective amorphous systems different from that offered by traditional approach originating liquid theory. The relation, if any, between these two points view, and relevance former to glass phase, has been difficult ascertain. In this Letter, we introduce model for which both theories apply strictly: it exhibits one hand an ideal transition other ``jamming'' features (fragility,...

We discuss an analysis of constraint satisfaction problems, such as sphere packing, K-SAT, and graph coloring, in terms effective energy landscape. Several intriguing geometrical properties the solution space become this light familiar well-studied ones rugged (glassy) landscapes. A benchmark algorithm naturally suggested by construction finds solutions polynomial time up to a point beyond clustering some cases even thermodynamic transitions. This has simple geometric meaning can be...

The generalized approximate message passing (GAMP) algorithm is an efficient method of MAP or approximate-MMSE estimation $x$ observed from a noisy version the transform coefficients $z = Ax$. In fact, for large zero-mean i.i.d sub-Gaussian $A$, GAMP characterized by state evolution whose fixed points, when unique, are optimal. For generic however, may diverge. this paper, we propose adaptive damping and mean-removal strategies that aim to prevent divergence. Numerical results demonstrate...

This paper investigates experimental means of measuring the transmission matrix (TM) a highly scattering medium, with simplest optical setup. Spatial light modulation is performed by digital micromirror device (DMD), allowing high rates and pixel counts but only binary amplitude modulation. On sensor side, without reference beam, CCD camera provides intensity measurements. Within this framework, shows that TM can still be retrieved, through signal processing techniques phase retrieval....

Abstract We examine a class of stochastic deep learning models with tractable method to compute information-theoretic quantities. Our contributions are three-fold: (i) we show how entropies and mutual informations can be derived from heuristic statistical physics methods, under the assumption that weight matrices independent orthogonally-invariant. (ii) extend particular cases in which this result is known rigorously exact by providing proof for two-layers networks Gaussian random weights,...

Approximate message passing is an iterative algorithm for compressed sensing and related applications. A solid theory about the performance convergence of exists measurement matrices having iid entries zero mean. However, it was observed by several authors that more general often encounters problems. In this paper we identify reason non-convergence with non-zero mean in context Bayes optimal inference. Finally demonstrate numerically when update changed from parallel to sequential restored.

Random projections have proven extremely useful in many signal processing and machine learning applications. However, they often require either to store a very large random matrix, or use different, structured matrix reduce the computational memory costs. Here, we overcome this difficulty by proposing an analog, optical device, that performs literally at speed of light without having any memory. This is achieved using physical properties multiple coherent scattering media. We device on...

This article is an extended version of previous work the authors [1,2] on low-rank matrix estimation in presence constraints factors into which factorized.Lowrank factorization one basic methods used data analysis for unsupervised learning relevant features and other types dimensionality reduction.We present a framework to study constrained general prior factors, output channel through observed.We draw paralel with vector-spin glass models -presenting unifying way number problems considered...

Reservoir Computing is a relatively recent computational framework based on large Recurrent Neural Network with fixed weights. Many physical implementations of have been proposed to improve speed and energy efficiency. In this study, we report new advances in Optical using multiple light scattering accelerate the recursive computation reservoir states. Two different spatial modulation technologies, namely, phase or binary amplitude modulations, are compared. Phase promising direction already...

We consider tensor factorizations using a generative model and Bayesian approach. compute rigorously the mutual information, Minimal Mean Square Error (MMSE), unveil information-theoretic phase transitions. In addition, we study performance of Approximate Message Passing (AMP) show that it achieves MMSE for large set parameters, factorization is algorithmically "easy" in much wider region than previously believed. It exists, however, "hard" where AMP fails to reach conjecture no polynomial...

We study generalised linear regression and classification for a synthetically generated dataset encompassing different problems of interest, such as learning with random features, neural networks in the lazy training regime, hidden manifold model. consider high-dimensional regime using replica method from statistical physics, we provide closed-form expression asymptotic generalisation performance these problems, valid both under- over-parametrised regimes broad choice model loss functions....

Teacher-student models provide a framework in which the typical-case performance of high-dimensional supervised learning can be described closed form. The assumptions Gaussian i.i.d. input data underlying canonical teacher-student model may, however, perceived as too restrictive to capture behaviour realistic sets. In this paper, we introduce covariate generalisation where teacher and student act on different spaces, generated with fixed, but generic feature maps. While still solvable form,...

While classical in many theoretical settings - and particular statistical physics-inspired works the assumption of Gaussian i.i.d. input data is often perceived as a strong limitation context statistics machine learning. In this study, we redeem line work case generalized linear classification, a.k.a. perceptron model, with random labels. We argue that there large universality class high-dimensional for which obtain same minimum training loss corresponding covariance. limit vanishing...