Skip to content
Preprint

A Walk From Free Probability to Matrix Discrepancy III: Higher Rank Kadison-Singer and Spectrally Thin Trees

Sep 2026 · 0 citations · 23 references
Computer Science

Abstract

Let $A_1,\ldots,A_N$ be positive semidefinite matrices of rank at most $r$, with $\sum_i A_i=I$ and $\norm{A_i}\le\varepsilon$. We prove that one sign can be assigned to each original matrix with discrepancy $O(\sqrt{\varepsilon\log(2r)})$, independently of their dimension and number, which is known to be optimal upto constants. We give a separate existence proof and a deterministic algorithm with polynomial work in a real-arithmetic model with semidefinite-value and exact spectral primitives. Separate Lean formalizations verify the existence proof and the algorithm in this arithmetic model. The proof extends the variational approach to discrepancy developed in the companion papers, motivated by operator-valued free interpolation, Lehner's formula, and spectral Tsallis regularization. A concave matrix power interpolates between a trace source and a sandwich source. Its concavity controls the response of the optimizing density. The walk maintains independent source reserves and a second matrix recording reserve expenditure. This matrix certifies contraction of the unfinished input mass between epochs; within an epoch, preparation and a negative-curvature step control the spectral potential while the coefficients advance toward signs. As applications, one spanning tree can be chosen simultaneously $O(\varepsilon\log(2s))$-spectrally thin for $s$ positive weightings of a common graph whose edge leverages are at most $\varepsilon$. The diagonal specialization gives discrepancy $O(\sqrt{L\log(2k)})$ for matrices with row sums at most $L$ and at most $k$ nonzero entries per column, through a walk of fractional colorings.

View source

Similar papers

Preprint Sep 2026

A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture

\cite{mss2015} proved Weaver's discrepancy result existentially, resolving the Kadison--Singer conjecture . Finding such signs efficiently for general inputs remained an open algorithmic question. In the real-arithmetic model, we give a deterministic algorithm running in polynomial time with discrepancy at most $35\sqr...

Tarun Kathuria · 2 citations
Preprint Sep 2026

Sharpness and Rigidity of the Two-Factor Recht-Re Lower Bound

Products of positive semidefinite matrices arise when successive steps of a randomized optimization method use different data points. Their average can have a negative eigenvalue even though every individual matrix is positive semidefinite. Lai and Lim proved at ICML 2020 that $\sum_{i\ne j}A_iA_j\succeq-\frac{1}{4}n(n...

Jin-Ze Zhao · 0 citations
Preprint Sep 2026

A Walk From Free Probability to Matrix Discrepancy I: Matrix Spencer

The potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element and combines Lehner's variational formula for the free edge with spectral Tsallis regularization, putting the discrepancy and remaining covariance in a single smooth optimization prob...

Tarun Kathuria · 2 citations
Preprint Aug 2026

An independent proof of the even-dimensional S-matrix inequality

Harwit and Sloane conjectured that every nonsingular entrywise-nonnegative matrix $A\in\mathbb R^{n\times n}$ satisfies $\|A^{-1}\|_F\ge 2n(n+1)^{-1}\|A\|_{\max}^{-1}$, with equality precisely for positive multiples of $S$-matrices. Zhang has given a complete proof of this conjecture by a centered pseudoinverse and spe...

Yin-Jie Li · 0 citations
Preprint Sep 2026

Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time

We prove two main algorithmic results in spectral discrepancy. First, we give a deterministic polynomial-time rounding theorem for rational positive semidefinite matrices of arbitrary rank. The algorithm starts from any rational fractional signing and assigns one sign per original matrix. Its discrepancy is less than $...

A. Jadbabaie, A. Saberi, Suvrit Sra · 1 citation
Preprint Sep 2026

Sharp spectral norm concentration of sparse random tensors

We prove a sharp concentration inequality for the spectral norm of sparse random tensors with independent Bernoulli entries. Let $T$ be an order-$k$ tensor of dimension $n\times\cdots\times n$ with independent Bernoulli$(p)$ entries, where $k$ is fixed. For any $c,r>0$, we show that $\|T-\mathbb E T\|\le C_{k,r,c}\sqrt...

Zhixin Zhou, Yizhe Zhu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.