Matrix sign selection improves discrepancy bounds for specific low-rank problems
A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees
Data Structures and Algorithms
Summary
The paper studies a mathematical problem where you try to assign plus or minus signs to certain matrices to keep their combined size small. The authors extend earlier work to matrices that could be of higher rank but are still well-controlled, proving new bounds on how well this can be done. They provide both a proof that such assignments exist and an efficient way to find them without random methods. This helps with problems like selecting sparse yet effective spanning trees in networks and coloring problems in graphs.
What this means in practice
- •For network engineers: Select spanning trees with guaranteed spectral thinness to manage network robustness across multiple weighted scenarios.
- •For graph algorithm developers: Deterministically construct low-discrepancy fractional colorings on sparse incident graphs without relying on probabilistic local lemma techniques.
Authors
Tarun Kathuria
Abstract
Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_iA_i=I$ and $\|A_i\|\le\varepsilon$. We prove that the original matrices admit signs with discrepancy $O(\sqrt\varepsilon\log(2r))$, independently of their dimension and number which is a significantly stronger result than what was known existentially. We give a deterministic algorithm with polynomial real-arithmetic work, and a separate existence proof requiring no computational assumptions. This extends our companion paper on rank-one Kadison--Singer discrepancy. A concave matrix power interpolates between the trace source, which pays a factor $r$, and the sandwich source, whose density response is harder to control. We prove that source concavity controls this additional response in the same inverse-Sylvester metric as the optimized spectral potential. As an application, a single spanning tree can be chosen simultaneously $O(\varepsilon\log^2(2s))$-spectrally thin for $s$ positive edge weightings of a common graph, provided every edge has leverage at most $\varepsilon$ in every weighting. The reduction preserves one common selection decision per edge. For incidence matrices with at most $t$ ones in every row and column, the diagonal specialization gives a deterministic walk on fractional colorings with discrepancy $O(\sqrt t\log(2t))$. The local-walk mechanism gives both existence and an efficient construction without using the Lovász local lemma. A Lean formalization of our existence proof has been completed and will be released shortly.