stochastic processes

MMSE of probabilistic low-rank matrix estimation: Universality with respect to the output channel

This paper considers probabilistic estimation of a low-rank matrix from non-linear element-wise measurements of its elements. We derive the corresponding approximate message passing (AMP) algorithm and its state evolution. Relying on non-rigorous but …

Spectral detection on sparse hypergraphs

We consider the problem of the assignment of nodes into communities from a set of hyperedges, where every hyperedge is a noisy observation of the community assignment of the adjacent nodes. We focus in particular on the sparse regime where the number …

Spectral detection in the censored block model

We consider the problem of partially recovering hidden binary variables from the observation of (few) censored edge weights, a problem with applications in community detection, correlation clustering and synchronization. We describe two spectral …

Constraint optimisation and landscapes

We describe an effective landscape introduced in [1] for the analysis of Constraint Satisfaction problems, such as Sphere Packing, K-SAT and Graph Coloring. This geometric construction reexpresses such problems in the more familiar terms of …