Analysis of Algorithms on Dense Matrices using Approximate Message Passing

Approximate Message Passing (AMP) is a class of algorithms motivated by statistical physics, that can be applied to a broad family of problems on dense matrices. Remarkably AMP can be analyzed exactly in the large size limit. I will describe the general approach, and illustrate it through applications to specific problems: the hidden clique problem, sparse principal component analysis, non-negative principal component analysis.