Abstract: I will present fast practical algorithms for approximate semidefinite programming (SDP) based on regularization by the von Neumann entropy. These approaches are based on a dual formulation of the regularized problem, and dual updates are computed using randomized trace estimators. Since the primal variable is only represented implicitly and we deliberately want to avoid assumptions of low-rankness, some care is required to recover problem-specific desiderata from the dual solution. I will show how the full pipeline yields fast algorithms for the Max-Cut problem, spectral embedding, and the full/partial permutation synchronization problems.
Prof. Michael Lindsey - Bio
Prof. Michael Lindsey
Michael Lindsey is an assistant professor in the math department at UC Berkeley and a faculty scientist at LBNL. He received his PhD in applied math from UC Berkeley in 2019. Afterward he was an NSF Postdoc at the Courant Institute from 2019-2022. He joined the faculty at UC Berkeley in 2022 and joined LBNL as a faculty scientist in 2023. Lindsey is a recipient of the 2022 John Todd Award in numerical analysis and a 2024 Sloan Research Fellowship. Lindsey works on computational methods driven by numerical linear algebra, optimization, and randomization, with a special focus on high-dimensional scientific computing problems arising from physics, chemistry, and applied probability.