Derandomizing Matrix Concentration Inequalities from Free Probability
By: Robert Wang, Lap Chi Lau, Hong Zhou
Recently, sharp matrix concentration inequalities~\cite{BBvH23,BvH24} were developed using the theory of free probability. In this work, we design polynomial time deterministic algorithms to construct outcomes that satisfy the guarantees of these inequalities. As direct consequences, we obtain polynomial time deterministic algorithms for the matrix Spencer problem~\cite{BJM23} and for constructing near-Ramanujan graphs. Our proofs show that the concepts and techniques in free probability are useful not only for mathematical analyses but also for efficient computations.
Similar Papers
Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
Probability
Makes math tools better for understanding data.
Matrix concentration inequalities for dependent binary random variables
Probability
Helps computers understand random data better.
Matrix Rosenthal and Concentration Inequalities for Markov Chains with Applications in Statistical Learning
Probability
Improves computer learning with tricky data.