arXiv preprint ·
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices $H_1,\dots,H_N$ of rank at most one, finds signs $s\in\{\pm1\}^N$ with $\|\sum_i s_i H_i\|\le 13\|\sum_i H_i^2\|^{1/2}$. As a corollary, for vectors $v_i$ with $\sum_i v_iv_i^*=I$ and $\|v_i\|^2\leδ$, the signs yield a partition $[N] = S_1 \cup S_2$ such that each part satisfies $\|\sum_{i \in S_j} v_i v_i^* - \frac{I}{2}\| \leq \frac{13}{2}\sqrtδ$ for $j = 1,2$. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic $\mathsf{KS}_2$ formulation, with a universal constant.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
Toscani-Fourier Distance on Probability Measures: Wasserstein Control, Topological Equivalence on Model Classes, and Duality
Resolution-Independent Analysis of Encoder--Decoder Operator Learning via Limiting Kernels
Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.