Fall 2020

The Overlap Gap Property in Principal Submatrix Recovery

Friday, Sep. 25, 2020 9:15 am9:40 am PDT

Add to Calendar


Subhabrata Sen, Harvard

Consider an N ×N symmetric Gaussian matrix, with a hidden k×k planted principal submatrix with elevated mean λ/N. We set k = N ρ, and study support recovery for the submatrix using the MLE. Under the double asymptotic regime ρ → 0 following N → ∞, we provide evidence for a computationally hard phase by exhibiting that the likelihood landscape exhibits a version of the Overlap-Gap-Property.

This is based on joint work with David Gamarnik and Aukosh Jagannath.