2016/06/27 by Christophe Schülke, Philip Schniter, Lenka Zdeborová · 1 citation
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Algorithm #Applied mathematics #Blind Source Separation Techniques #Combinatorics #Compressed sensing #Computer science #Factorization #Mathematics #Matrix (chemical analysis) #Microwave Imaging and Scattering Analysis #Parametric statistics #Physics #Random matrix #Rank (graph theory) #Replica #Sparse and Compressive Sensing Techniques #Sparse matrix #Statistics #cond-mat.dis-nn #cs.IT #math.IT
paper · pdf · doi:10.1103/physreve.94.062136
published as Phys. Rev. E 94, 062136 (2016) · 23 pages, 8 figures
arxiv created 2016/06/27 · openalex publication_date 2016/12/27 · arxiv updated 2017/01/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In the problem of matrix compressed sensing, we aim to recover a low-rank matrix from a few noisy linear measurements. In this contribution, we analyze the asymptotic performance of a Bayes-optimal inference procedure for a model where the matrix to be recovered is a product of random matrices. The results that we obtain using the replica method describe the state evolution of the Parametric Bilinear Generalized Approximate Message Passing (P-BiG-AMP) algorithm, recently introduced in J. T. Parker and P. Schniter [IEEE J. Select. Top. Signal Process. 10, 795 (2016)1932-455310.1109/JSTSP.2016.2539123]. We show the existence of two different types of phase transition and their implications for the solvability of the problem, and we compare the results of our theoretical analysis to the numerical performance reached by P-BiG-AMP. Remarkably, the asymptotic replica equations for matrix compressed sensing are the same as those for a related but formally different problem of matrix factorization.