























Marcus, Spielman, and Srivastava in their seminal work \cite{MSS13} resolved the Kadison-Singer conjecture by proving that for any set of finitely supported independently distributed random vectors $v_1,\dots, v_n$ which have "small" expected squared norm and are in isotropic position (in expectation), there is a positive probability that the sum $\sum v_i v_i^\intercal$ has small spectral norm. Their proof crucially employs real stability of polynomials which is the natural generalization of real-rootedness to multivariate polynomials. Strongly Rayleigh distributions are families of probability distributions whose generating polynomials are real stable \cite{BBL09}. As independent distributions are just special cases of strongly Rayleigh measures, it is a natural question to see if the main theorem of \cite{MSS13} can be extended to families of vectors assigned to the elements of a strongly Rayleigh distribution. In this paper we answer this question affirmatively; we show that for any homogeneous strongly Rayleigh distribution where the marginal probabilities are upper bounded by $ε_1$ and any isotropic set of vectors assigned to the underlying elements whose norms are at most $\sqrt{ε_2}$, there is a set in the support of the distribution such that the spectral norm of the sum of the natural quadratic forms of the vectors assigned to the elements of the set is at most $O(ε_1+ε_2)$. We employ our theorem to provide a sufficient condition for the existence of spectrally thin trees. This, together with a recent work of the authors \cite{AO14}, provides an improved upper bound on the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。