PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tarun Kathuria

arXiv:2609.18914v1cs.DS

TL;DR

The Matrix Spencer problem asks whether bounded symmetric matrices admit signs with small operator norm for their signed sum. This paper proves such bounds with a randomized algorithm and analyzes the stability of a regularized variational system. Its rectangular logarithmic exponent is optimal already for diagonal matrices.

  • Problem

    The Matrix Spencer problem asks whether n real symmetric m×m matrices of operator norm at most one admit signs making the signed sum small in operator norm.

    Source: §1 · p. 1

  • Method

    The proof analyzes the response of a regularized density-and-transport system to center and covariance changes, using a cap-to-response estimate.

    Source: §6.2 · p. 16, §7.5 · p. 28

  • Results

    For m≥n≥1, signs achieve discrepancy at most 108√(n(1 + log(2m/n))), with a randomized polynomial-time algorithm in the real-arithmetic model.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The rectangular logarithmic exponent 1/2 is optimal already for diagonal matrices.

    Source: §1 · p. 2

    The runtime bounds count real-arithmetic operations and do not assert a binary-encoding bound.

    Source: §14 · p. 50

Abstract

from arXiv · show

The Matrix Spencer conjecture asks whether any $n$ real symmetric matrices A_1,...,A_n \in \mathbb{R}^{m \times m} of operator norm at most one admit a signing $x\in\{-1,1\}^n$ such that the operator norm of the signed sum is at most O(\sqrt{n \log(2m/n)}) We give a randomized algorithm establishing this bound with polynomial runtime in the real-arithmetic model. We first prove the $O(\sqrt n)$ bound for $m\le n$, resolving the square case, and then obtain the rectangular bound by changing the regularizer. As in earlier algorithmic discrepancy methods \cite{lovettmeka2012,bansalLaddhaVempala2022,pesentivladu2026}, we run a covariance-controlled random walk from the origin of the hypercube, rounding coordinates near its faces and keeping them fixed. Our potential measures a soft spectral edge of the evolving discrepancy matrix perturbed by an operator-valued free semicircular element. Inspired by the free interpolation approach of \cite{bbvh2023}, we combine Lehner's variational formula for the free edge \cite{lehner1999} with spectral Tsallis regularization \cite{allenZhuLiaoOrecchia2015,pesentivladu2026}. This puts the discrepancy and remaining covariance in a single smooth optimization problem. The potential has a finite-dimensional semidefinite formulation. Stability of its optimizer, governed by equations related to the matrix Dyson equation \cite{erdos2019}, lets us find a large subspace in which to move while controlling discrepancy. The square case uses the Tsallis--$1/2$ regularizer; the rectangular case uses a suitable generalized Tsallis power regularizer. Our companion paper \cite{kathuria2026ks} applies these ideas to give an algorithmic proof of Weaver's discrepancy theorem, whose existence proof by [MSS15] resolved the Kadison--Singer conjecture \cite{mss2015}.Lean formalizations of our main discrepancy theorems have been completed and will be released shortly.

1 Introduction

The paper gives a randomized polynomial-time signing algorithm for the Matrix Spencer problem, with a rectangular bound whose logarithmic exponent is optimal for diagonal matrices. Its proof combines a covariance-controlled walk with a variational potential, and also yields the same square and rectangular bounds through projection-based methods.

1 Introduction

  • For m≥n≥1, signs achieve discrepancy at most 108√(n(1 + log(2m/n))).The randomized algorithm returns such a signing or failure with probability at most 2^-b and runs in time polynomial in n, m, and b in the real-arithmetic model.Source: §1 · p. 2
  • The walk reserves covariance to compensate for spectral costs, removing directions that violate a covariance-derivative cap before moving in a constrained subspace.It retains covariance eigenvalues at least 1/2, intersects their subspace with frozen-coordinate and radial constraints, and withdraws a small multiple of the resulting projection.Source: §1 · p. 2
  • The theorem imposes no rank hypothesis, unlike the cited O(√n) matrix bound for inputs of rank at most n/log^3 n.The paper’s computational comparison with algorithms in other computation models is limited to their discrepancy guarantees.Source: §1 · p. 2
  • The rectangular logarithmic exponent 1/2 improves on the prior exponent 2 and is optimal already for diagonal matrices.The cited diagonal lower bound applies for n≤m≤2^(cn) with a sufficiently small absolute constant c; for larger dimensions, the trivial discrepancy bound n is the natural saturation scale.Source: §1 · p. 2
  • The proof also implies that projection SDPs achieve the same square and rectangular bounds up to universal constants.The argument converts a hereditary discrepancy bound into Gaussian-measure bounds for active subfamilies, then applies shifted partial coloring with summable stage costs.Source: §1 · p. 2
  • The potential combines discrepancy and remaining covariance through a smoothed variational formulation of the free spectral edge with spectral density regularization.The optimizer’s response is analyzed by differentiating the stationarity equations, whose operator structure is related to matrix Dyson equation analysis.Source: §1 · pp. 2–3

2 A spectral potential with a covariance reserve

The section builds a spectral potential that evaluates discrepancy together with a selected covariance reserve. Its density and transport formulations explain why the full covariance source map matters and how covariance withdrawal can be matched to movement.

2.1 The state and its two matrix spaces

  • The algorithm pairs a coefficient-space reserve C with a physical-matrix source map; C is selected by the algorithm, not the random point’s covariance.The map’s action on changing spectral tests, rather than only its value at the identity, enters the potential.Source: §2.1 · p. 3, §2.3 · p. 4

2.2 What the density measures

  • The density potential smooths a spectral test of H and measures the remaining source through fidelity; in the square regime, its initial value is O(√n).The transport formulation makes the connection to the free spectral edge visible.Source: §2.2 · p. 4

2.3 Why retain a map rather than a variance matrix?

  • The full source map retains interactions with changing spectral tests that an ordinary variance matrix can miss, even for rank-one inputs.The paper gives covariance states with identical ordinary variance but different reserve terms in the density objective.Source: §2.3 · p. 4, §2.5 · p. 6

2.4 The diagonal example

  • For diagonal inputs, each coordinate receives a shift of twice its remaining standard deviation, while optimized spectral weights readjust and shape the curvature comparison used by the walk.The diagonal calculation relates a cap on the covariance derivative to a bound on the half-Hessian’s scale.Source: §2.4 · p. 5

2.5 A rank-one example: what ordinary variance misses

  • Two covariances for rank-one noncommuting inputs have the same identity variance but different source behavior under the anisotropic test Z = diag(2, 1).This illustrates why retaining only the source map at the identity loses information relevant to the reserve.Source: §2.5 · pp. 5–6

2.6 Matching movement with covariance withdrawal

  • The walk matches a centered increment of covariance h²Q with withdrawal of h²Q; for the free potential, a bound on optimized response replaces the Gaussian heat-equation identity.The same matching principle is used with the power profile in the rectangular regime.Source: §2.6 · p. 6

3 How the potential determines the walk

The walk uses a response estimate for the optimized potential to balance discrepancy movement against covariance withdrawal. Preparation makes the estimate applicable, while legal subspace steps and epoch tests provide progress; the rectangular version changes the regularizer while retaining the walk.

3.1 The local estimate to aim for

  • The target local estimate bounds the optimized potential’s response so center curvature is paid for by covariance withdrawal in a symmetric centered move.Odd terms cancel in the local expansion; the uniform remainder bound applies on states reached by the algorithm.Source: §3.1 · p. 7

3.2 Preparation, legal movement, and progress

  • Preparation reduces covariance along directions with large covariance derivative until the response cap holds, while keeping the coefficient vector fixed.The trace cost is recorded separately from movement and includes discarded small eigenvalues in the numerical implementation.Source: §3.2 · p. 7
  • Movement uses the intersection of the high-covariance subspace with frozen-coordinate and radial constraints, then samples a signed basis direction and freezes near-face coordinates.The radial constraint gives equal radial progress for either sign, and the step size keeps movement inside the cube.Source: §3.2 · p. 7

3.3 Why epochs can be accepted and restarted

  • Accepted epochs keep their endpoints, and a bounded number of accepted epochs halves the live count, yielding the square discrepancy bound; the rectangular regime changes the density power while keeping the walk.For the rectangular case, the power is 1 − 1/p with p on the scale of 1 + log(2m/n), and response and phase budgets change accordingly.Source: §3.3 · p. 8

4 The variational toolkit

The variational toolkit develops fidelity’s transport and semidefinite formulations, then establishes properties of the square-root regularizer and the resulting energy needed later in the paper.

4.1 Square roots and fidelity

  • Fidelity’s transport minimization and semidefinite lift support differentiation and computation, respectively.The density formulation is a finite-dimensional SDP with affine constraints and a linear objective.Source: §4 · p. 9, §4.1 · pp. 10–11
  • The square-root trace is strictly concave on positive semidefinite matrices, including when the matrices are singular.This curvature underlies the uniqueness of the maximizing density.Source: §4.1 · pp. 10–11
  • For positive definite S and M, fidelity’s transport formula has a unique positive definite minimizer characterized by ZMZ = S.Its SDP formula also applies when S or M is singular.Source: §4.1 · pp. 10–11
  • The square-root regularizer makes the maximizing density unique, positive definite, and continuous in the center H and covariance C.Strict concavity gives uniqueness, while the regularizer’s positive order-√ε gain rules out a singular maximizer.Source: §4.1 · pp. 11–12
  • Both E(·, C) and f are convex and 1-Lipschitz in operator norm, and E(H, C) is order preserving in C.At fixed H, replacing the current covariance with identity covariance on ℓ live labels increases energy by at most 2√ℓ.Source: §4.1 · p. 12

5 The transport form of the spectral potential

This section expresses the regularized spectral potential as a transport optimization over positive matrices. The formula also covers singular sources and exposes how covariance changes interact with movement of the center.

5 The transport form of the spectral potential

  • The density and transport form a saddle point that provides equations to differentiate for the optimizer response.The identity is proved even when the source occupies only a proper physical subspace.Source: §5 · pp. 12–13
  • When the potential has a positive definite maximizing density, its value equals an infimum over positive definite transport matrices.For a singular source, the attained formulation uses the source’s physical support while keeping the density full-dimensional.Source: §5 · p. 13
  • Covariance affects the same transport objective whose center derivative controls movement.At a faithful source, the covariance response is measured through the optimizing density and transport in the coefficient direction that moves the center.Source: §5 · p. 13
  • The unregularized expression has an SDP formulation, and the square-root and dyadic-power regularizers admit exact SDP formulations.The general variational identity alone does not establish SDP representability for every regularizer.Source: §5 · p. 14

6 The optimizer response and its stability

This section analyzes the optimizer’s response to changes in the center and covariance, establishing smoothness on fixed covariance supports and expressing local response in balanced coordinates. It develops response budgets and extends comparisons to singular physical sources via compression that retains full density coupling.

6.1 A smooth optimizer on each covariance support

  • The optimizer is unique, positive definite, and smooth in the center and covariance on each fixed coefficient support, even when the physical source is singular.The density remains full-dimensional while the source kernel is fixed on that support.Source: §6.1 · p. 14

6.2 Linearizing the density and transport equations

  • The exact response follows by linearizing the coupled KKT equations for the density, transport, and trace multiplier under center and covariance changes.The self-consistent system is analyzed in parallel with matrix Dyson equation methods, with attention to the response relevant at a regular spectral edge [5, Section 4].Source: §6.2 · p. 16

6.3 Balanced coordinates and the coefficient forces

  • The balanced coefficient forces have a Gram matrix equal to the covariance derivative after factoring the covariance, connecting the algorithm’s covariance cap to the inverse-Hessian response bound.The section identifies the total squared force mass with the fidelity and gives the local unconstrained response as TrHS(ΣA−1).Source: §6.3 · pp. 19–20
  • Balanced coordinates yield a positive self-adjoint Hilbert–Schmidt contraction with a fixed point, while the regularizer supplies a positive curvature term that keeps the full system invertible.The fixed point means the reference curvature alone is insufficient, so the analysis uses the structure of the coefficient forces rather than a spectral-gap bound.Source: §6.3 · pp. 19–20
  • Balanced-coordinate factorization places retained directions in ran C and yields coefficient-force budgets under Tr S ≤ 1 using the contraction-derived covariance cap.The covariance derivative and transport identities support these budgets.Source: §6.3 · p. 21
  • An inverse-domination argument bounds coupled density responses by splitting each force while preserving the shared optimization variable before taking separate suprema.This supports the response bound while retaining density coupling.Source: §6.3 · pp. 21–22

6.4 Singular physical sources

  • For singular physical sources, compression onto their support bounds the original retained response while preserving the full Tsallis density response, including off-block perturbations.Quadratic minimization over perturbations with fixed compression establishes the comparison; the original center and regularizer strength remain unchanged.Source: §6.4 · pp. 22–23
  • The compressed problem retains the original regularizer strength and response budgets, and applies for every retained label count, even below the physical dimension.Compression does not restart the density problem.Source: §6.4 · pp. 22–23

7 Bounding the response of the coefficient forces

The section bounds how the coefficient forces respond to changes in the optimized center, using the forces’ shared Kraus structure rather than a uniform inverse-Hessian bound. A covariance-derivative cap then yields a bound on the full center response.

7 Bounding the response of the coefficient forces

  • The coefficient forces share the source’s Kraus matrices, so their Gram cap and total mass bound their combined response without controlling every matrix direction.The section’s response argument uses the full inverse quadratic form after splitting forces across the low and complementary spectra.Source: §7 · p. 23

7.1 Two frame estimates on real matrix space

  • The real coefficient Gram cap yields frame estimates for left- and right-weighted synthesis maps and a Hilbert–Schmidt bound for a superoperator.The tensor-index rearrangement establishes a Hilbert–Schmidt estimate, not operator-norm invariance under rearrangement.Source: §7.1 · p. 24

7.2 Forces meeting the small spectrum of the balanced density

  • For forces meeting the small spectrum of the balanced density, the square-root regularizer bounds their response without requiring a uniform inverse-Hessian bound.The full Hessian still includes all density directions.Source: §7.2 · p. 25

7.3 A tensor estimate on the complementary spectrum

  • On the complementary spectrum, tensor-map estimates combine an order bound with an independent trace estimate to control the Hilbert–Schmidt norm.The order estimate alone would leave an unwanted dependence on the largest eigenvalue of the density.Source: §7.3 · p. 26

7.4 The contribution from the complementary spectrum

  • The complementary-spectrum inverse-Hessian contribution has an exact physical-trace expression, which the tensor estimate and scalar budgets bound.The proof retains the full operator; only the forcing frame is compressed.Source: §7.4 · p. 28

7.5 The cap-to-response estimate

  • A covariance-derivative cap bounds the full optimized center response; with L=4096 and θ=1, the bound’s coefficient is 770.The spectral cutoff is only an estimating device; the algorithm enforces the covariance-derivative cap, not the cutoff.Source: §7.5 · pp. 28–29

8 From local movement to a full signing

This section turns local covariance-controlled movement into a full signing argument, using large legal movement subspaces, small-step bounds, and phases to control progress and spectral cost. It establishes Algorithm 3’s square-case guarantee for m≤n and describes how phase completion and adaptive retries support the full signing procedure.

8.1 A large subspace on which the covariance is at least one half

  • For a prepared covariance, the high-eigenvalue subspace has dimension at least 2 Tr C − rank C; intersecting legal constraints removes at most codim V dimensions.The movement covariance is half the projection onto the resulting legal subspace.Source: §8.1 · p. 30

8.2 Analytic parameters and routine contracts

  • The trial clock has horizon τ, each phase uses at most K accepted epochs, and each epoch request has at most r trials.These routine contracts are used to separate the progress and acceptance analysis from the numerical precision of the implementation.Source: §8.2 · p. 31

8.3 One small step and its natural time scale

  • Advancing the natural clock by h² makes radial progress pathwise at rate Tr Q, while expected potential drift per clock unit is Tr(Q(J−Γ)) + O(M4h²).The symmetric signed sample cancels the linear and cubic Taylor terms, yielding an expected one-step remainder bounded by M4h⁴/24.Source: §8.3 · p. 32

8.4 Covariance loss and pathwise progress

  • If terminal covariance loss is at most ℓ/64, a trial either freezes at least ℓ/64 new labels or runs for more than τ/2.Before each movement, Tr Q ≥ ℓ/16.Source: §8.4 · p. 33

8.5 The supporting-plane excess

  • Each trial is accepted with probability at least 499/800; an accepted trial and reset together increase the potential by at most 27ℓ.The accepted trial contributes at most 25ℓ and resetting the remaining-label covariance to identity contributes at most 2ℓ.Source: §8.5 · p. 34

8.6 Phases and the square discrepancy bound

  • A phase halves its live-label count within K accepted epochs, or rounds the last fewer than 32 labels and finishes.Its potential increase is at most (27K + 64)ℓ.Source: §8.6 · p. 35
  • Fewer than 128 freeze-ended and 64/τ time-ended epochs can occur in an unfinished phase, so the chosen K exceeds their combined bound.Freeze-ended epochs each fix more than k/128 labels; time-ended epochs each increase squared norm by more than kτ/64, while the restricted squared norm is at most k.Source: §8.6 · p. 35
  • Each completed phase halves the live-coordinate count, and termination leaves zero covariance with every coordinate a sign.The two-sided encoding identity and assumption (8.4) then establish the discrepancy bound pathwise.Source: §8.6 · p. 35
  • Adaptive epoch retries keep the total failure probability at most 2^-b by union-bounding conditional trial-rejection bounds across requests.Each trial’s conditional rejection probability is at most 301/800, and fresh draws on retries give failure probability at most 2^-r per request.Source: §8.6 · p. 35
  • For m≤n, Algorithm 3 guarantees discrepancy at most 108√n with failure probability at most 2^-b.This is the square part of Theorem 1.1.Source: §8.6 · p. 35

9 The rectangular extension: changing the regularizer

For rectangular dimensions, the paper changes the regularizer’s power while retaining the walk’s geometric constraints and progress identity. It analyzes the resulting potential and response equations, with trace interpolation keeping transport and density coupled.

9 The rectangular extension: changing the regularizer

  • For large D/n, a generalized Tsallis power regularizer replaces the square-root choice, trading regularizer cost against an increased response bound.The walk’s geometric constraints, matched covariance withdrawal, and progress identity do not depend on the square-root exponent.Source: §9 · pp. 35–36

9.1 The power potential and its optimizer

  • The power potential has a unique positive-definite optimizing density; it is convex and 1-Lipschitz in H, monotone in C, and has a stated bound at (0, I_n).At q=1/2 and θ=1, it is exactly the square potential.Source: §9 · p. 36, §9.1 · p. 37

9.2 What changes in the response equations

  • The shared balanced response equations retain the transport structure, while the new power enters through the regularizer curvature in the inverse-response formula.The section’s trace interpolation keeps transport and density coupled in the new response analysis.Source: §9 · p. 36, §9.2 · pp. 37–38

10 General Tsallis curvature and correlated interpolation

The section extends the square-root Tsallis response analysis to general powers using curvature comparison and correlated trace interpolation. These bounds control low and high observed forces and yield a faithful-source cap-to-response estimate.

10 General Tsallis curvature and correlated interpolation

  • General Tsallis powers replace the square-root case’s exact inverse-curvature formula with a scalar divided-difference comparison; equality holds at q = 1/2.The comparison is transferred to positive operators because the operators are diagonal in the same matrix-unit basis.Source: §10 · pp. 38–39

10.1 Balanced quantities and an interpolation inequality

  • Correlated trace interpolation bounds physical trace quantities while retaining their common optimizing density through the interpolation.The argument uses weighted scalar Hölder on a balanced density coordinate.Source: §10.1 · pp. 39–40

10.2 The low and high observed forces

  • The force split controls the low corner through a small eigenvalue and the high corner through a tensor estimate, bounding cross terms by diagonal terms.The full curvature inverses act on their full spaces even though only forcing vectors are split.Source: §10.2 · pp. 40–41

10.3 The faithful-source cap-to-response bound

  • Under the stated cap and faithful-source conditions, the general-power cap-to-response estimate also bounds local unconstrained response at faithful subnormalized densities.The theorem’s response argument uses the actual covariance derivative and the full optimized center Hessian.Source: §10.3 · p. 42

11 Reciprocal powers and singular physical sources

The section transfers the faithful-source response estimate to singular physical sources for reciprocal-integer powers. It accounts for density perturbations outside the source support rather than discarding them.

11 Reciprocal powers and singular physical sources

  • A shared kernel in the input matrices can make the physical source singular, while the deterministic center may still couple its support to the complement.Compressing the whole optimization would therefore lose part of the density response.Source: §11 · p. 43
  • For q = 1/p with integer p ≥ 2, the inverse power-regularizer curvature has an exact finite sum formula that supports comparison under compression.The proof minimizes the full regularizer quadratic form over perturbations with a prescribed compression.Source: §11 · pp. 43–44
  • For reciprocal-integer powers, the faithful cap-to-response estimate holds for every coefficient covariance, including singular physical sources, with unchanged parameters and constants.The proof accounts for off-support perturbations through quadratic minimization before applying the compressed estimate.Source: §11 · pp. 43–44

12 A small square-root term and the aspect-ratio choice

A small square-root regularizer supplies numerical regularity for the rectangular potential while preserving its response bound at the new optimizer. The aspect-ratio choice balances costs, keeps the same walk, and yields the stated rectangular signing guarantee.

12 A small square-root term and the aspect-ratio choice

  • The added square-root term is for numerical regularity because the power potential’s density floor alone is inadequate for a uniform polynomial accuracy bound as its exponent grows.The response estimate is checked at the new optimizing density.Source: §12 · pp. 44–45

12.1 Choosing the exponent and balancing the two costs

  • The exponent choice changes the response budget and time scale, while the uniform signed projection step and its progress calculation remain the same.The square estimate is recovered at q = 1/2, θ = 1, and κ = 0.Source: §12.1 · pp. 45–46
  • 108√(n(1 + log(2m/n))) bounds rectangular signing discrepancy, with failure probability at most 2^-b.The rectangular argument uses the same geometric walk and probability argument as the square case.Source: §12.1 · pp. 45–46

12.2 Why the extra square root gives polynomial conditioning

  • The added square-root term gives the implemented potential a polynomial density floor under the stated bounds on epoch size and center norm.The bound depends on the density regularizer and total source budget.Source: §12.2 · p. 46

13 Computing the first derivatives from a primal SDP solution

The section derives reports for the algorithm from feasible primal SDP solutions: objective accuracy controls density accuracy, which supports stable covariance-derivative evaluation and a supporting-plane report. The derivative formula uses a positive shift to avoid relying on the unshifted source’s smallest positive eigenvalue.

13 Computing the first derivatives from a primal SDP solution

  • A feasible approximate primal solution supplies both covariance-derivative and supporting-density reports through density accuracy, transport, and a positive shift.The shift stabilizes derivative evaluation without modifying the potential.Source: §13 · p. 46, §13.3 · p. 48

13.1 What a certified primal solution provides

  • A certified primal gap controls distance from the returned density to the unique maximizing density.Feasibility of the lifted SDP point lets the objective gap control that density distance.Source: §13.1 · p. 47

13.2 Stability of the covariance derivative

  • Relative density stability controls the covariance derivative, without requiring a lower bound on a positive eigenvalue of the physical source.The derivative is a nonnegative quadratic form monotone in its positive matrix arguments.Source: §13.2 · pp. 47–48

13.3 A stable formula for the covariance derivative

  • A positive shift enables stable direct derivative evaluation without conditioning on the smallest positive eigenvalue of the unshifted physical source.With approximate eigendecomposition, certified matrix-function accuracy is needed rather than accurate individual eigenvectors or an eigenvalue-gap bound.Source: §13.3 · pp. 48–50

13.4 The supporting plane for epoch acceptance

  • A feasible source-free primal solution gives a supporting-plane report directly, replacing finite differences for the cap test and epoch acceptance.The step size and fourth-derivative bound for finite movement remain separate parts of the proof.Source: §13.4 · p. 50

14 Computing a feasible optimizing density

The density optimization is recast as a semidefinite program with an explicit interior point, enabling a feasible primal solution through an ellipsoid algorithm. In the stated real-arithmetic model, the solver runs in polynomial time and its objective accuracy yields density accuracy under the stated concavity and faithfulness conditions.

14.1 An equivalent SDP with a uniform interior point

  • The equivalent SDP lift has an explicit interior ball, so ellipsoid optimization remains available even when a direct fidelity block is singular.Factoring the source moves its coefficient matrices into the objective; the lift's interior radius depends only on its dimensions, even for sources with arbitrarily small positive eigenvalues.Source: §14 · p. 50, §14.1 · p. 52
  • The fidelity lift attains its maximum even when the density or covariance is singular, using a contraction factorization of the cross-term matrix.The factorization is X = P^1/2 K Q^1/2 with ||K||op ≤ 1.Source: §14.1 · p. 51
  • One SDP formulation represents both potentials using a density, positive semidefinite power variables, and a matrix lift.The power-block constraints recover the trace regularizer, and the feasible set is compact and convex.Source: §14.1 · p. 51

14.2 A standard ellipsoid theorem and the returned certificate

  • The ellipsoid solver returns a feasible primal solution with certified objective accuracy in polynomially many scalar operations and exact EVD calls.The complexity is polynomial in the dimensions and log(2 + B_obj + ν^-1); it is a real-arithmetic bound, not a binary encoding bound.Source: §14 · p. 50, §14.2 · p. 53
  • Under strong concavity and a faithful optimizer, objective accuracy controls density error; a density floor yields a faithful approximation within a chosen operator-norm tolerance.The stated choice requires ν ≤ c e^2/4 and e ≤ μ/2 when S* ⪰ μ I_D.Source: §14.2 · p. 53

15 Implementing preparation, sampling, and acceptance

The implementation combines covariance preparation, constrained random movements, and approximate SDP reports in a finite signing algorithm. Its work is polynomial on every execution in the stated arithmetic model, with retry amplification controlling failure probability.

15.1 The numerical recipe and complete algorithm

  • The numerical recipe implements Solve, Prepare, Project, and Sample, then runs bounded epoch trials, rounds near-face coordinates, and checks acceptance reports.Movement updates the live coordinates and discrepancy while subtracting the movement covariance; the full algorithm retries failed epoch requests.Source: §15.1 · pp. 54–55

15.2 A covariance cap from one approximate density

  • Prepare returns zero covariance or a covariance whose positive eigenvalues are at least 2δ and whose response is capped; every call terminates.Preparation decreases covariance by dust removal and paid cuts while leaving the center H fixed.Source: §15.2 · p. 56

15.3 Sampling and acceptance

  • Sample uses one exact EVD and one uniform draw to produce movements satisfying the walk's feasibility and progress conditions.The signed sampler is uniform over the eigenvectors of the legal movement projection and their two signs.Source: §15.3 · p. 57
  • The reported excess and martingale differ from their exact counterparts by at most 5ε_A/3 and ε_A, respectively.These accuracy bounds allow the acceptance lemma to apply to the actual primal SDP reports.Source: §15.3 · p. 57

15.4 Polynomial work on every execution

  • Polynomial work is bounded on every execution, and the retry count r = M + b + 1 makes total failure probability at most 2^-b.The bound includes rejected trials, exact EVD calls, scalar operations, and uniform draws.Source: §15.4 · pp. 57–58

16 AI Usage

The paper reports AI contributions to the development of its SDP representation, proof strategies, and Lean formalizations. The author distinguishes those contributions from the conception of the core discrepancy-potential approach.

16 AI Usage

  • The author conceived operator-valued K-transform discrepancy potentials, including Tsallis–1/2 variants, in 2022–2023.The semidefinite representation of the Tsallis–1/2 regularized potential was later conceived by an internal version of Gemini used with a specific harness.Source: §16 · p. 58
  • ChatGPT 5.5–5.6 Sol Ultra helped develop and test proof strategies and rule out simpler approaches.The author says this work led to the strategy presented in the paper.Source: §16 · p. 58
  • GPT 6 Astra Ultra was used to develop Lean formalizations of the Matrix Spencer and Weaver/Kadison–Singer arguments.The formalizations included separate existence and algorithmic formulations.Source: §16 · p. 58

A Uniform derivative bounds for the finite walk

The appendix establishes uniform derivative bounds for the optimized potential and its optimizer, with constants controlled by density and retained covariance floors rather than the smallest positive eigenvalue of the physical source. These bounds control covariance cuts and finite movement remainders in the walk.

A.3 Why physical-source conditioning does not enter

A Uniform derivative bounds for the finite walk

  • Theorem A.1 gives a faithful optimizer with a uniform density floor and smooth optimized value on each fixed covariance support.The theorem also supplies covariance and movement derivative bounds under its stated support and floor conditions.Source: A Uniform derivative bounds for the… · p. 59

A.4 Passing the bounds through the optimizer

  • The implicit function theorem transfers local smoothness of the density objective and invertible tangent Hessian to the unique global optimizer on each fixed face.Compactness and uniqueness ensure continuity of the global optimizer, keeping it in the local solution neighborhood.Source: §A.1 · p. 59, §A.2 · p. 60, §A.4 · p. 62

A.2 Density floor and inverse response

  • The optimizer's density floor bounds the inverse tangent Hessian, providing the stability needed to differentiate its stationarity equation.At faithful trace-one densities, the negative density Hessian is at least χ/2 on the trace-zero tangent space, with inverse norm at most 2/χ.Source: §A.2 · p. 60

A.4 Passing the bounds through the optimizer

  • The covariance curvature bound controls finite paid cuts, while the fourth-derivative bound controls the remainder from averaging both signs of a finite movement.The finite-step remainder remains part of the walk analysis and is made affordable by the mesh size, independently of solver precision and spectral gap.Source: §A.4 · pp. 62–63
Loading 2609.18914v1…