![Geometry and Computation in High Dimensions.png](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-05/Geometry%20and%20Computation%20in%20High%20Dimensions.png.jpg?itok=1JtiYLWR)
Abstract
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.