§4.1, proof of Theorem 7, p. 188 — if ‖W^(t)‖²_F ≤ (1 − ε²t)‖A‖²_F, either (17) holds or one more cut matrix keeps the invariant at t + 1
ProvedFriezeKannan.CutDecomp.inductive_stepcut-decompositionenergy-incrementfrobenius-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and . Suppose cut matrices , , have been found such that the error satisfies
Then at least one of the following holds:
- satisfies (17): for all , ;
- there are , and a real such that
This is the inductive step of the existence proof of cut decompositions: the invariant cannot persist beyond , so the process stops with (17) after at most cut matrices.
Formalization Note The paper also assumes ; the step does not use it, and the statement is given without it. The family is indexed by Fin t (so , the empty family, is allowed), and the new cut matrix is added to their sum.
Preamble
import Mathlib import Definitions.Def_FriezeKannan_CutDecomp_Setting
Formal statement
namespace FriezeKannan.CutDecomp
/-- §4.1, proof of Theorem 7, p. 188: if the cut matrices `D^(1), …, D^(t)` leave a remainder
`W^(t) = A - (D^(1) + ⋯ + D^(t))` with `‖W^(t)‖²_F ≤ (1 - ε² t) ‖A‖²_F`, then either `W^(t)`
already satisfies (17), or one further cut matrix keeps the invariant with `t + 1`. -/
theorem inductive_step {R C : Type*} [Fintype R] [Fintype C] [DecidableEq R] [DecidableEq C]
(A : Matrix R C ℝ) (ε : ℝ) (hε : 0 < ε) (t : ℕ)
(Rs : Fin t → Finset R) (Cs : Fin t → Finset C) (d : Fin t → ℝ)
(hinv : frobNorm (A - cutSum Rs Cs d) ^ 2 ≤ (1 - ε ^ 2 * t) * frobNorm A ^ 2) :
(∀ (S : Finset R) (T : Finset C),
|blockSum (A - cutSum Rs Cs d) S T|
≤ ε * Real.sqrt ((S.card : ℝ) * T.card) * frobNorm A) ∨
∃ (S : Finset R) (T : Finset C) (d' : ℝ),
frobNorm (A - (cutSum Rs Cs d + cutMatrix S T d')) ^ 2
≤ (1 - ε ^ 2 * (t + 1)) * frobNorm A ^ 2 := by sorry
end FriezeKannan.CutDecomp
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 188, §4.1, proof of Theorem 7 (inductive hypothesis ‖W‖²_F ≤ (1 − ε²t)‖A‖²_F and the dichotomy)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.