202 citations · 1.3k across the 61 of their papers we have counts for
6 papers · 1 filter
Average-Case Integrality Gap for Non-Negative Principal Component Analysis
Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
Montanari and Richard (2015) asked whether a natural semidefinite programming (SDP) relaxation can effectively optimize over $\|\mathbf{x}\…
Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky +2
We study the problem of efficiently refuting the k-colorability of a graph, or equivalently certifying a lower bound on its chromatic number. We give formal evidence of average-cas…
Likelihood Maximization and Moment Matching in Low SNR Gaussian Mixture Models
Anya Katsevich, Afonso Bandeira
We derive an asymptotic expansion for the log likelihood of Gaussian mixture models (GMMs) with equal covariance matrices in the low signal-to-noise regime. The expansion reveals a…
The Spectral Norm of Random Lifts of Matrices
Afonso S. Bandeira, Yunzi Ding
We study the spectral norm of random lifts of matrices. Given an symmetric matrix , and a centered distribution on symmetric matrices with…
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein +1
In compressed sensing, the restricted isometry property (RIP) on sensing matrices (where ) guarantees efficient reconstruction of sparse vectors. A matrix has t…
Computationally efficient sparse clustering
Matthias Löffler, Alexander S. Wein, Afonso S. Bandeira
We study statistical and computational limits of clustering when the means of the centres are sparse and their dimension is possibly much larger than the sample size. Our theoretic…