Matrix signing discrepancy
DefinitionSpencerEight_Supplement_discmatdiscrepancymatrix-spencerp2o-gran-per-chapterp2o-plan-bookp2o-v1random-matrices
For real symmetric matrices , the matrix signing discrepancy is the operator norm of the best signing:
It is the quantity the lower-bound families of Section 15 compute or bound, and the inner term of the constant .
Formalization Note The minimum is a real infimum over the finite, nonempty set of real sign vectors (); the norms are nonnegative, so it is attained. The family's index type and the matrix size are arbitrary finite types; Definition 15.1 uses and .
Definition code
import Mathlib
import Definitions.Def_SpencerEight_signedSum
open scoped Matrix.Norms.L2Operator
namespace SpencerEight.Supplement
/-- The matrix signing discrepancy (Definition 15.1, Song, Zhang, *Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input*, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), pp.288-289 (PDF pp.288-289)):
`discmat(A₁, …, A_n) := min_{ε ∈ {−1,1}ⁿ} ‖∑ᵢ εᵢ Aᵢ‖`, the norm of the best signing.
**Formalization Note** `‖·‖` is Mathlib's L2 operator norm. A signing is a real vector `ε` with
`ε i = 1 ∨ ε i = -1` for every `i`. The minimum is written as a real infimum over this finite set of
signings; the set is nonempty (the all-ones signing) and the norms are nonnegative, so the infimum is a
genuine minimum. The index type `ι` of the family and the index type `d` of the rows are arbitrary
finite types; the source's `ι = [n]`, `d ≤ n` is the case used by `Dmat`. -/
noncomputable def discmat {ι d : Type*} [Fintype ι] [Fintype d] [DecidableEq d]
(A : ι → Matrix d d ℝ) : ℝ :=
⨅ ε : {ε : ι → ℝ // ∀ i, ε i = 1 ∨ ε i = -1}, ‖signedSum A ε.1‖
end SpencerEight.Supplement
Source
Song, Zhang, Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input, arXiv:2609.15025 (held version, sha256 9ccbcdb8…), Definition 15.1, pp.288-289 (PDF pp.288-289)