Source-linked AI summary
Rank-One Matrix Discrepancy and Algorithmic Kadison--Singer
Ekene Ezeunala, Haotian Jiang
TL;DR
The paper addresses the algorithmic KS2 partition problem and gives a deterministic polynomial-time algorithm for rank-one matrix discrepancy. The resulting algorithm solves KS2(13/2), while the paper notes that the constant is not optimized and a stronger existence bound is known.
Problem
Weaver’s KS2 formulation asks for a two-part partition of vectors summing to the identity, with each vector’s squared norm at most δ, so each part approximates half the identity within an error depending only on δ.
Source: §1 · p. 2Method
The paper normalizes to PSD rank-one matrices and moves a fractional signing to a vertex using a potential that combines a matrix term and coordinate budgets.
Source: §1 · p. 2Results
The deterministic polynomial-time algorithm solves KS2(13/2), though the constant is not optimized and gives a stronger existence bound.
Source: §1 · p. 2Takeaways & Limitations
The paper provides a deterministic polynomial-time algorithm for the Kadison–Singer problem in Weaver’s equivalent KS2 formulation with a universal constant.
Source: §1 · p. 2The parameter λ is taken rational; if its nominal value is not rational, it is replaced by a rational in [√ν/(200N), √ν/(100N)].
Source: §3.1 · p. 5
Abstract
from arXiv · showhide
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\delta$, 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\delta$ 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.
1 Introduction
The paper gives a deterministic polynomial-time algorithm for rank-one matrix discrepancy and applies it to Weaver’s KS2 partition problem. Its approach guides a fractional signing with a potential that decreases until all signs are fixed.
1 Introduction
- The Kadison–Singer problem in Weaver’s equivalent KS2 formulation asks for a two-part partition whose parts each approximate half of the identity within an error depending only on δ.For vectors with sum of outer products equal to the identity and squared norms at most δ, the partition is formed from the positive- and negative-sign classes.Source: §1 · p. 2
- The algorithm deterministically solves KS2(13/2) in polynomial time, although its constant is not optimized and gives a stronger existence bound.A stronger constant-4 bound for Theorem 1.1 was proved in [KLS20], but that proof does not yield an efficient algorithm.Source: §1 · p. 2
- The algorithm normalizes the input to PSD rank-one matrices and moves a fractional signing from zero to a vertex while controlling its matrix sum with a potential.The potential starts at a value bounded in terms of the square root of the sum of the matrices.Source: §1 · pp. 2–3
- The potential combines an SDP-based matrix term with coordinate budgets ψ_i(x)=(1−x_i^2)^(1/3), which vanish when coordinates are fixed at ±1.Reservoir terms hold PSD slots along each matrix direction and release them as the corresponding coordinate moves.Source: §1 · pp. 2–3
- At each step, either a sufficiently heavy reservoir permits fixing a coordinate while reducing the potential, or a coupled local-step analysis provides a decreasing move.The analysis uses rank-one identities and Bansal’s covariance lemma; the algorithm compares endpoint, gradient, and minimum-Hessian-eigenvalue moves.Source: §1 · p. 3
2 Preliminaries
The preliminaries set matrix-norm conventions, describe computational tools, and state a covariance lemma used later. They also introduce a normalization of the input matrices.
2 Preliminaries
- The paper treats Hermitian matrices as a real vector space, uses operator or Euclidean norm for ∥·∥, Frobenius norm for ∥·∥_F, and trace inner product ⟨U,V⟩=Tr(UV).Source: §2 · p. 3
- The implementation uses matrix convexity of inversion and Schur-complement equivalence, and the required quantities can be computed from the input matrices.Source: §2 · p. 3
- The covariance lemma is identified as a form of [Ban24, Theorem 2.5].Source: §2 · p. 3
- The paper states a covariance lemma: for L⊆R^m of dimension ℓ and κ>1, there is U⪰0 with range(U)⊆L, U_ii≤1, U⪯κ diag(U), and Tr(U)≥ℓ−m/κ.Source: §2 · p. 3
- The input matrices may be assumed nonzero and are renormalized to PSD matrices A_i.Source: §2 · p. 3
3 Proof of Main Result
The proof rounds a fractional coloring to a vertex by decreasing a combined matrix-and-coordinate potential. Its key lemmas certify progress at every nonterminal state, yielding a polynomial-time rounding algorithm with final discrepancy O(√ν).
3.1 Potential Function and Key Lemmas
- A weighted matrix-and-coordinate potential trades changes in S(x) against removed unfinished-coordinate contributions, and its coordinate term is zero at vertices.The matrix constraints bound the positive and negative eigenvalues of S(x).Source: §3.1 · pp. 4–5
- The key lemmas bound S(x) through the matrix potential and certify descent either by endpoint freezing or through a random-step drift and covariance condition.The random-step alternative supplies an existence certificate; the algorithm instead finds a deterministic descent move.Source: §3.1 · p. 5
3.2 Proof of Theorem 1.1
- At each iteration, endpoint, Hessian, and gradient-coordinate moves are tested, and a nonterminal state admits a move decreasing Ψ by at least 1/poly(N).The guaranteed decrease bounds the number of iterations by a polynomial in N.Source: §3.2 · p. 6
- The algorithm reaches a vertex with ∥S(x_f)∥ = O(√ν) in polynomially many polynomial-time iterations.Each iteration can be implemented using semidefinite programming and eigenvalue computation.Source: §3 · p. 4, §3.2 · p. 7
4 Proof of the Key Lemmas
This section proves the key lemmas on the matrix-potential minimizer and ways to decrease the potential. It establishes uniqueness and smoothness on open faces, and proves Lemma 3.2 by constructing a covariance-controlled random direction whose curvature bounds and drift yield a certificate of local decrease in expected potential.
4.1 Proof of Lemma 3.1
- The matrix-potential optimization has a unique minimizer, and its minimizer and value vary smoothly within each open cube face with frozen coordinates fixed.Uniqueness follows from strict convexity of the Lagrangian in the matrix variables; smoothness follows from the implicit function theorem.Source: §4.1 · pp. 7, 9, 11
4.2 Proof of Lemma 3.2
- For any nonterminal state, either assigning an active coordinate to an endpoint decreases Ψ by at least λψ_i(x), or a drift μ and covariance Σ give a random step that decreases the potential.The alternative holds with a polynomially bounded C0 independent of the state.Source: §4.2 · pp. 11–12
- If cψ_i b_i ≥ 1 − x_i or cψ_i a_i ≥ 1 + x_i, moving coordinate i to the corresponding endpoint preserves feasibility and decreases Ψ.The move does not increase R and decreases Φ by ψ_i.Source: §4.2 · p. 12
- When no endpoint move applies, the proof constructs a covariance to control R’s positive curvature and a drift to balance its curvature terms and uniformly decrease Φ.The construction uses the optimal dual matrices P and Q and their stationarity identities.Source: §4.2 · p. 12
- Rescaling yields positive coefficients with α_iβ_i = Ω(1) and e_a + e_b = O(1/c), supporting the bounds on the interaction matrices.The interaction matrices satisfy ∥A∥, ∥B∥ = O(N/c).Source: §4.2 · pp. 14–16
- A centered, finitely supported random direction is constructed through rescaled response equations, with interaction bounds used to establish the covariance and movement guarantees.The proof restricts to a subspace of dimension n − O(n/c) and chooses a covariance supported on it before verifying the energy and movement bounds.Source: §4.2 · pp. 15, 17, 18
- A drift cancels the mismatch between the positive and negative weighted sums, and its cost is only an O(1/c)-fraction of the available coordinate curvature.This allows the proof to use the negative second derivatives of Φ to obtain uniform decrease.Source: §4.2 · pp. 19–20
- D[Ψ] = D[R] + λD[Φ] ≤ −Ω(λn/C1), establishing the bounds in Lemma 3.2’s second alternative and enabling a local expected decrease.For sufficiently small θ > 0, the Taylor expansion shows Ψ decreases in expectation.Source: §4.2 · p. 20