arXiv:2610.18639 · v2

Subgaussian Vector Balancing by an Ising Model

首次提交 2026-10-14 00:09

版本更新 2026-11-05 08:51

雷达观测 2026-11-06 11:06

摘要

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, \ldots, v_n$ of norm less than 1, we give a closed form for a centrally symmetric distribution on a vector $σ\in \{\pm 1 \}^n$ so that the signed sum $\sum_j σ(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.

作者备注：added results for the Sherrington Kirkpatrick model