Source-linked AI summary
Fast Spectral Signing for Vector Balancing
Xiaoyu Li
TL;DR
For unit-norm columns, the paper seeks deterministic signs with bounded coordinate sums. It speeds spectral signing by tracking energy-corrected barriers along one fractional coloring, reducing discrepancy from 8272 to 99 and running time from eO(mn9 + n10) to eO(mn + n4.372).
Problem
The paper addresses deterministic signing for vector balancing and seeks a faster alternative to the earlier spectral-signing algorithm [GFL26a].
Source: §1 · p. 1Method
It rounds one fractional coloring while a Gram-matrix top eigenvalue tracks energy-corrected row barriers.
Source: §1.1 · p. 3Results
Discrepancy falls from 8272 to 99, while running time falls from eO(mn9 + n10) to eO(mn + n4.372).
Source: §1 · p. 2Takeaways & Limitations
Only input reading depends on m; after fewer than n2 rows survive, the remaining run costs O(n^ω+2 log^3 n).
Source: §1 · p. 2Step size is constrained by the top-eigenvalue gap; multiplicity-two examples have separation of only about 128η.
Source: §12 · p. 33
Abstract
from arXiv · showhide
The Koml\'os conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first polynomial-time algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$. Our algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top eigenvalue of a Gram matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of matrix products. Its direction is read off by conditional expectations from a polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the algorithm has polynomial bit complexity.
1 Introduction
The introduction frames vector signing as the Komlós balancing problem and presents a faster deterministic spectral-signing algorithm. It sketches a single-trajectory method that tracks row barriers through a Gram matrix.
1 Introduction
- Discrepancy falls from 8272 to 99, while running time falls from eO(mn9 + n10) to eO(mn + n4.372).The comparison is with the earlier deterministic spectral-signing algorithm [GFL26a].Source: §1 · p. 2
- Only input reading depends on m: fewer than n2 rows survive, and the rest of the run costs O(n^ω+2 log^3 n).Rows with l1 norm at most 1 are discarded because their signed sums are always bounded by 1.Source: §1 · p. 2
1.1 The idea
- Energy-corrected barriers reserve room for each row’s remaining rounding variance, while the top eigenvalue of a Gram matrix tracks all rows together.As coordinates freeze, the barrier reserve is released and the top eigenvalue cannot increase at fixed regularization.Source: §1.1 · p. 3
- A weak quadratic charge limits warm rows, while a polynomial soft projector and conditional expectations produce long, flat directions for rounding.Only O(n log^2 n) warm rows need explicit evaluation; a motion clock delays checks of distant rows until they could approach a barrier.Source: §1.1 · pp. 3–4
- Affine row representations let the algorithm repair small constraint residuals through offsets, with one defect identity accounting for changes of representation.Rescaled flat directions and a growing regularizer also reduce the update count relative to [GFL26a].Source: §1.1 · pp. 3–4
1.2 Related work
- Partial coloring colors a constant fraction per round, while this paper’s theorem concerns the final signed sum rather than ordered partial sums [KL26].The paper also situates its spectral barrier matrix among prior spectral methods for discrepancy and sparsification.Source: §1.2 · p. 4
2 Preliminaries
The preliminaries fix a real-RAM model and reduce the relevant row count, then establish spectral tools for analyzing a regularized matrix's top eigenpair. Two counting lemmas later support the argument about negative directions.
2.1 Notation and model
- Rows with l1 norm at most 1 have discrepancy at most 1 for every signing, and fewer than n^2 remaining rows need be considered.They are found in O(mn) operations; small n or no remaining rows permits an immediate signing.Source: §2.1 · p. 5
2.2 The top eigenpair of a regularized matrix
- Adding η11^T to a symmetric positive semidefinite entrywise nonnegative matrix makes its top eigenvalue simple, with gap at least η.Its unit top eigenvector can be chosen strictly positive.Source: §2.2 · pp. 5–6
2.3 Two tools for counting negative directions
- The filtered Gram–resolvent bound controls eigenvector motion in the lower spectrum, while diagonal comparison limits positive directions of S − D.When S_jj ≤ ρD_jj, S − D has fewer than ρs positive eigenvalues.Source: §2.3 · p. 6
3 Affine rows, barriers, and the potential
The section defines changing affine representations for row sums and combines energy-corrected barriers into a spectral potential. Its deterministic procedure moves a fractional coloring toward signs while tracking and repairing those representations.
3.1 Affine rows
- Each row is tracked by an affine function whose value matches its tracked sum; deleting a coefficient or changing an offset replaces the representation while preserving that sum at the change point.Frozen coordinates leave the active set and their coefficients are folded into offsets.Source: §3.1 · p. 7
3.2 Classes, deletion, and scales
- Rows are classified as large, medium, or completed by retained mass; cleanup spreads medium rows, and their nonincreasing scales avoid square roots while keeping barriers monotone.The scale search uses O(log s) comparisons.Source: §3.2 · p. 8
3.3 Barriers, the spectral matrix, and the potential
- The regularized Gram matrix M tracks barrier weights, while the potential combines its top eigenvalue with coordinate energy and a weak quadratic charge on tracked row sums.Admissibility requires medium barriers to remain nonpositive and the top eigenvalue to stay below 2.Source: §3.3 · pp. 8–9
3.4 Changes of representation
- A single defect identity accounts for deletions and offset changes, so the analysis can evaluate their cumulative effect at the final signing without storing the history.Deleting a coefficient contributes its later discrepancy between the evaluation point and the change point; a frozen coordinate's defect vanishes afterward.Source: §3.4 · p. 10
3.5 The algorithm
- The algorithm deterministically advances from an anchor through full or short steps, repairs protected offsets, rounds, and cleans up before returning signs with discrepancy below 99.Fixed rules govern deletion, conditional choices, boundary choices, and heap ties.Source: §3.5 · p. 11
4 Many directions of stable negative curvature
The analysis finds many directions in which the potential curves downward despite constraints from near-barrier rows and top-eigenvector motion. Spread rows and a small-trace charge preserve a substantial set of such directions.
4.2 The dimension count
- The dimension count shows that, after constraints and eigenvector motion are accounted for, a subspace of dimension greater than μs has curvature at most −2η.Spread rows keep the Gram matrix trace small relative to its top eigenvalue, limiting eigenvalues near the top.Source: §4 · p. 11, §4.2 · pp. 12–13
4.1 Barrier derivatives
- A barrier gradient is dominated coordinatewise by the curvature supplied by the energy term.This relation supports the search for directions of stable negative curvature.Source: §4.1 · p. 12
4.3 The charge
- Adding the quadratic charge still leaves a subspace of dimension greater than s/64 with the required curvature when 4λ ≤ η/128.The charge's curvature is confined to a few directions because its trace is small.Source: §4.3 · pp. 13–14
5 Warm and cold rows
The section screens rows whose barrier weights are negligible, while ensuring that rows near a barrier remain explicitly tracked. A weak charge also bounds the aggregate quantity used to count warm rows.
5 Warm and cold rows
- Screening leaves coefficients and offsets unchanged: certificates only permit numerical routines to replace tiny weights by zero.The analysis continues to use the full matrix.Source: §5 · p. 14
- Every nearly tight pair belongs to a warm row; cold rows carry certificates implying their score is at most H0.Hysteresis demotes warm rows only below H0 − 2 and promotes checked cold rows only above H0 − 1.Source: §5 · p. 14
- The charge bounds the sum of the counted quantities by 2048n, and warm rows meet a threshold in tracked sum or scale.The charge is used for the running-time lemma, not for the existence of good directions or step progress.Source: §5 · p. 14
6 Soft projectors and flat directions
The section replaces an unknown subspace of negative curvature with a polynomial soft projector, then uses conditional expectations to find long, flat directions. Penalizing rather than projecting constraints yields directions with small residuals, which the signing interface can repair.
6 Soft projectors and flat directions
- A polynomial soft projector and conditional expectations produce a long direction with negative curvature and small inner products against specified forms.The projector has large trace and long vectors in its range are negatively curved; the resulting direction is also flat against the listed forms.Source: §6 · p. 15
6.1 Soft projectors
- A soft projector need not be idempotent or have a negative range; its defining conditions make long outputs of the form Πξ negatively curved.A lower bound on output length supplies the curvature guarantee.Source: §6.1 · p. 15
6.2 Long flat vectors by conditional expectations
- Conditional expectations deterministically choose signs so Πξ is long while controlling its inner products with the listed forms.The construction uses moments through degree 2r and returns a normalized direction with norm between 1/2 and 1.Source: §6.2 · pp. 15–16
6.3 A polynomial soft projector
- A polynomial approximation to a spectral filter yields a rational soft projector when S is rational.It retains large eigenvalues on strongly negative directions while suppressing the rest; the iteration uses a fixed number of matrix products per step.Source: §6.3 · pp. 16–17
6.4 Penalties instead of kernels
- Adding κC⊤C penalizes constraint violations instead of projecting onto ker C, while preserving negative curvature on a subspace already in ker C.When rc = O(s), the construction costs O(s^ωJf + Ns^ω−1 + Nsr2) operations and does not depend on the smallest nonzero singular value of C.Source: §6.4 · pp. 17–18
6.5 The signing interface
- The signing interface applies the constrained-direction result to the approximate Hessian and returns a direction whose small constraint residual can be repaired.Its flatness scale ensures warm barriers move at bounded speed during the step.Source: §6.5 · p. 18
7 One repaired move
A move first repairs the direction’s small constraint residual through protected offsets, then compares repaired candidates using a reference curve for the potential. Local progress bounds show that full steps decrease the potential and short steps remain controlled.
7.1 Offset repair
- Offset repair keeps tracked large-row sums at zero and protected medium barriers at most zero despite a direction that is only nearly tangent.The repair changes offsets on protected rows; its effect on the spectral potential is bounded when the unrepaired candidate has L < 4 and ψ ≤ 1/4.Source: §7 · p. 19, §7.1 · p. 19
7.2 The reference curve
- The frozen-offset reference curve is an analysis device, not an evaluated algorithm state, and its potential has a bounded fourth derivative.The fourth derivative is at most C4/η in rescaled time; in physical parameter t it is at most C4ζ4/η.Source: §7.2 · pp. 20–21
7.3 Full and short steps
- The step rule compares repaired candidates at ±τ for a full step, but a short step freezes the first minimizing coordinate.Endpoint evaluations use the warm list at the anchor; cold offsets are not repaired because cold rows are controlled over the small motion.Source: §7.3 · p. 22
- Full repaired steps lower the potential by at least ∆ζ − er(ζ), while short repaired steps raise it by at most the stated error bound.Both endpoints satisfy row admissibility, and cleanup can only improve these bounds.Source: §7.3 · pp. 22–23
8 The whole trajectory
The global analysis rounds after each move and increases the regularizer as the active dimension shrinks, keeping the potential within a fixed budget. This budget yields a finite run with fewer than 278rnn2 + n updates, with the first epoch dominating the work.
8.1 Rounding to a grid
- Rounding coordinates away from zero preserves the cube and row inequalities while raising the potential by at most the stated bound.Rebasing large and warm rows keeps their tracked sums or barriers controlled; cold rows remain far below zero after rounding.Source: §8.1 · pp. 23–24
8.2 Epochs
- The regularizer doubles as the active dimension falls, balancing summable potential increases against decreasing epoch update counts.The epoch choice uses ηj ≍ 4^(j/2)/n; the update counts decrease geometrically across epochs.Source: §8.2 · p. 24
8.3 The global budget
- The potential stays below 1/16 after committed moves, rounding, cleanup, and epoch switches.The global budget accounts for resets, short steps, repairs, rounding, and full-step decreases; the bound keeps each next anchor in the region needed for local analysis.Source: §8.3 · p. 25
- Fewer than 278rnn2 + n updates suffice for termination, with epoch j using fewer than 277rnn2 2^-j full steps.The total cost is governed by the active-dimension volume rather than update count, and the first epoch dominates.Source: §8.3 · p. 25
9 Sleeping rows and sufficient statistics
The section avoids repeated work on distant rows with a motion clock and maintains sufficient statistics for the all-row charge. Together these techniques bound cold-row inspection costs and let charge-dependent computations avoid scanning every row.
9.1 A motion clock
- A motion clock bounds when a cold row can next approach its barrier, allowing rows to remain uninspected until their expiry times.After a check, slack certifies the row’s safety for a period; rows that become warm receive fresh certificates after any later cold period.Source: §9.1 · p. 26
- Due row inspections and their queue operations have a bounded total cost over the run.The row-evaluation cost is O(m0 log n + √m0 n^(5/2) log n).Source: §9.1 · pp. 26–27
9.2 The charge through two statistics
- The all-row charge is maintained through two statistics, so charge-dependent quantities the algorithm evaluates cost O(s2) rather than O(m0s).The identity E = x⊤VQxV + 2f⊤xV + c⊤c is used in the analysis, not maintained directly.Source: §9.2 · p. 27
- Initializing the charge statistics and processing support changes, masses, scales, classes, and event-forced checks costs O(m0n2) over the run.Each retained coefficient is deleted at most once, and moves that change no support require no global scan.Source: §9.2 · p. 28
10 Computing the spectral quantities
The section computes the numerical quantities needed by each update using matrix products, positive definite inversion, and scalar arithmetic. It replaces exact spectral objects with polynomial-time approximations while controlling their errors.
10 Computing the spectral quantities
- The computation covers the gradient, search form, and spectral scalar at both step endpoints using products, one positive definite inversion, and scalar arithmetic.The numerical interface states that its loops take O(log n) scalar or matrix iterations.Source: §10 · p. 28, §10.3 · p. 30
10.1 Two matrix primitives
- Positive definite inversion and batched products provide the matrix primitives used to compute update quantities.An order-s matrix can be inverted in O(s^ω) field operations, and the stated batched products cost O(qs^(ω−1) + s^ω).Source: §10.1 · p. 28
10.2 The derivative blocks
- The derivative blocks use warm-pair data and approximate weights to compute the gradient and related forms efficiently.Weights are approximated by clipped Taylor polynomials, while the polynomial itself is not differentiated; projective powering approximates the top-eigenvector projector.Source: §10.2 · p. 29
10.3 Projective resolvents
- Projective resolvents compute the gradient, search form, and spectral scalar from a vector without requiring its normalization.With exact weights and an exact eigenvector, these quantities match the analytic expressions; the numerical interface bounds their errors using approximate weights and a projector.Source: §10.3 · p. 30
11 Proof of the main theorem
The proof establishes the operation count, final-signing bound, and rational-input bit complexity. The argument also shows that the algorithm is deterministic.
11.1 Running time
- O(mn + n^(ω+2) log^3 n + n^4 log^5 n + m0 n^2 + √m0 n^3 log n) bounds the whole run’s work.The bound combines the input scan and update costs with terms depending on the number m0 of surviving rows.Source: §11.1 · p. 31
11.2 The final signing
- When fewer than 64 coordinates remain, rounding each to its nearest sign yields the final signing bound.The proof bounds completed rows through their tracked sums and defects; still-large rows and harmless rows receive separate bounds.Source: §11.2 · p. 32
11.3 Rational input
- For rational input of encoding length Lin, the algorithm has polynomial bit complexity in m, n, and Lin.The proof uses rational arithmetic and fraction-free elimination, and bounds the lengths of persistent state and per-update computations.Source: §11.3 · p. 32
- Every choice uses comparisons with fixed tie rules, making the algorithm deterministic.The proof combines the initialization, feasible directions, potential decrease, termination, discrepancy, operation-count, and rational-bit-complexity results.Source: §11.3 · p. 33
12 Discussion
The discussion identifies devices that may apply beyond discrepancy, explains the running-time and constant bottlenecks, and states open algorithmic problems. It also points to complex discrepancy as a direction for future work.
12 Discussion
- A soft projector with conditional expectations and affine-representation bookkeeping are proposed as devices applicable beyond discrepancy.The first substitutes a matrix polynomial for a subspace in finding a long, flat vector; the second uses offset repairs to restore feasibility while tracking their defects.Source: §12 · p. 33
- The update count is O(n^2 log n), while update cost depends on matrix products and the gap between the two largest eigenvalues.The regularizer guarantees a gap of η, but ηs must remain small because the regularizer contributes up to ηs to the spectral quantity.Source: §12 · p. 33
- The 98.99 bound splits nearly evenly between barrier height 52.6 and deletion cost about 46.4.The discussion relates these terms to the barrier-entry threshold and spread requirement, and contrasts them with the retained-mass threshold 256 and barrier height 8192 in [GFL26a].Source: §12 · p. 33
- An open problem is a faster deterministic Komlós algorithm, with O(mn + n^(ω+2−c)) operations for some constant c > 0 or o(n^2) updates.The proposed direction is a potential controlling averages of W over every active-coordinate set while remaining smooth at a coarser scale than η.Source: §12 · p. 34
- The discussion also asks for a polynomial-time algorithm with discrepancy at most 36 or 3√(2π), and proposes efficient Banaszczyk-type induction as one route.It separately poses finding a complex-discrepancy algorithm with eO(n) updates.Source: §12 · p. 34
A The fourth derivative
This appendix bounds the fourth derivative needed in Proposition 7.5, with derivatives taken in rescaled time while retained data remain fixed. The bounds control the integrated Taylor remainder, including across crossings of L = 1.
A The fourth derivative
- The appendix derives weighted bounds on eigenvalue and eigenvector derivatives to keep the final estimate of order η^-1 rather than η^-3.These bounds feed the fourth-derivative estimate used in the potential analysis.Source: A The fourth derivative · p. 34
A.1 Third and fourth derivatives of the eigenvalue
- Differentiating the simple top eigenvalue yields a fourth-derivative expression involving M and derivatives of its eigenvector.The derivation uses the projected equation and bounds the resulting terms using y = ∥v′∥ and y2 = ∥v′′∥.Source: §A.1 · p. 34
A.2 The chain rule
- Applying the chain rule to (L − 1)_+^4 bounds its fourth derivative by a constant below 229/η.Where L < 1 the spectral fourth derivative vanishes; the locally Lipschitz third derivative lets the bound control the integrated Taylor remainder across L = 1.Source: §A.2 · p. 35
B The numerical error budget
Appendix B proves the approximation error bounds used in Proposition 10.5, which concern analytic quantities rather than derivatives of a numerical program. It tracks errors in approximate weights, eigenlines, derivative blocks, and outputs, then checks the constants in rational arithmetic.
B The numerical error budget
- Each approximate weight has absolute error at most ρ, cold weights are approximated by zero, and the computed eigenline projector has error at most ρ; the final choice is ρ=ρ∗.Source: B The numerical error budget · p. 35
B.1 Matrix, eigenline, and resolvent
- The approximate resolvent matrix remains positive definite because its perturbation is at most η/2 while the exact matrix satisfies H ⪰ ηI.Source: §B.1 · p. 36
B.2 Derivative blocks
- Approximate derivative blocks satisfy the same bounds up to a factor of two, with additional perturbation allowances for D∗ and ℓ.The passage states that the D∗ bound gains a factor of four and that the ℓ bound also includes eigenvector perturbation.Source: §B.2 · pp. 36–37
B.3 The outputs
- The charge contributes the same exact vector and matrix to true and computed outputs, so it adds no output error.In endpoint comparisons, the charge enters through the exact contrast of Lemma 7.6.Source: §B.3 · p. 37
- The appendix chooses ρ=ρ∗ small enough to satisfy the stated inverse and eigenline conditions.Source: §B.3 · p. 37
C Rational checks
- Rational checks verify displayed identities exactly and test the n-dependent inequalities for n=26,…,240; the global budget is shown to yield a bound below 99.Source: C Rational checks · p. 38