Phase diagram of matrix compressed sensing

Abstract

In the problem of matrix compressed sensing we aim to recover a low-rank matrix from few of its element-wise linear projections. 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 recently introduced P-BiG-AMP algorithm. We show the existence of different types of phase transitions, their implications for the solvability of the problem, and we compare the results of the theoretical analysis to the 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.

arXiv comment23 pages, 8 figures

References in corpus (15)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Message Passing Algorithms for Compressed Sensing
• Quantum state tomography via compressed sensing
• Statistical physics of inference: Thresholds and algorithms
• Bilinear Generalized Approximate Message Passing
• Statistical physics-based reconstruction in compressed sensing
• Adaptive Damping and Mean Removal for the Generalized Approximate Message Passing Algorithm
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Parametric Bilinear Generalized Approximate Message Passing
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Analysis of Regularized LS Reconstruction and Random Matrix Ensembles in Compressed Sensing
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices

Cited by in corpus (6)

• Bilinear Recovery using Adaptive Vector-AMP
• Joint Channel-Estimation/Decoding with Frequency-Selective Channels and Few-Bit ADCs
• A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• Near-optimal matrix recovery from random linear measurements
• Automatic Hyperparameter Tuning in Sparse Matrix Factorization
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens