Subgaussian Vector Balancing by an Ising Model

Abstract

We show that the guaranties of the Gram-Schmidt Walk Algorithm of Bansal, Dadush, Garg, and Lovett can be achieved by an Ising model. Given vectors $v_1,\dots ,v_n$ of norm less than 1, we give a closed form for a centrally symmetric distribution on a vector $\sigma \in \{\pm 1{\}}^n$ so that the signed sum ${\sum }_j\sigma (j)v_j$ is $1$-subgaussian. We show that the Glauber dynamics for this model mix rapidly provided that the norms of the input vectors are bounded below 1 by an inverse-polynomial. The proofs employ the theory of Lorentzian polynomials, and we use these techniques to show fast mixing bounds for other spin systems.