PreprintarXiv licencearXiv
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Abstract
We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices H1,…,HN of rank at most one, finds signs s∈{±1}N with |∑i si Hi|≤ 13|∑i Hi2|1/2. As a corollary, for vectors vi with ∑i vivi*=I and |vi|2≤δ, the signs yield a partition [N] = S1 ∪ S2 such that each part satisfies |∑i ∈ Sj vi vi* − I/2| ≤ 13/2√δ for j = 1,2. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic KS2 formulation, with a universal constant.
Related
- A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
- Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
- Tighter bounds on Komlós discrepancy: existence and algorithmic results
- Fuglede--Kadison Determinants of Shifted Matrix Semicircles
- Free-Probabilistic State Evolution and Random Matrix Discrepancy
BibTeX
@misc{ezeunala2026rankone,
title = {{Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer}},
author = {Ekene Ezeunala and Haotian Jiang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17266},
eprint = {2609.17266},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17266},
}
RIS
TY - UNPB
TI - Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
AU - Ekene Ezeunala
AU - Haotian Jiang
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.17266
UR - https://arxiv.org/abs/2609.17266
AB - We give a deterministic polynomial-time algorithm that, given rational Hermitian matrices H_1,…,H_N of rank at most one, finds signs s∈{±1}^N with |∑_i s_i H_i|≤ 13|∑_i H_i^2|^1/2. As a corollary, for vectors v_i with ∑_i v_iv_i^*=I and |v_i|^2≤δ, the signs yield a partition [N] = S_1 ∪ S_2 such that each part satisfies |∑_i ∈ S_j v_i v_i^* − I/2| ≤ 13/2√δ for j = 1,2. This gives a deterministic polynomial-time algorithm for the Kadison--Singer problem, in Weaver's equivalent discrepancy-theoretic KS_2 formulation, with a universal constant.
ER -