§4.1, proof of Theorem 7, p. 188 — ‖W − CUT(S,T,d)‖²_F − ‖W‖²_F = −|S||T|d² = −W(S,T)²/(|S||T|) for d = W(S,T)/(|S||T|)
ProvedFriezeKannan.CutDecomp.frobenius_dropcut-decompositionenergy-incrementfrobenius-normp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let , be nonempty. Put
the average entry of on the rectangle , and let . Then
Subtracting from its average on a rectangle therefore lowers the squared Frobenius norm by exactly . This is the energy-decrement computation that drives the existence proof of cut decompositions (Theorem 7).
Formalization Note and are assumed nonempty, as in the paper, where they come from a rectangle with ; this keeps the division defining meaningful. All three equalities of the display are stated.
Preamble
import Mathlib import Definitions.Def_FriezeKannan_CutDecomp_Setting
Formal statement
namespace FriezeKannan.CutDecomp
/-- §4.1, proof of Theorem 7, p. 188: subtracting `CUT(S, T, d)` with
`d = W(S, T)/(|S||T|)` lowers `‖W‖²_F` by exactly `|S||T| d² = W(S, T)²/(|S||T|)`. -/
theorem frobenius_drop {R C : Type*} [Fintype R] [Fintype C] [DecidableEq R] [DecidableEq C]
(W : Matrix R C ℝ) (S : Finset R) (T : Finset C) (hS : S.Nonempty) (hT : T.Nonempty) :
let d : ℝ := blockSum W S T / ((S.card : ℝ) * T.card)
(frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
= ∑ i ∈ S, ∑ j ∈ T, ((W i j - d) ^ 2 - W i j ^ 2)) ∧
(frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
= -((S.card : ℝ) * T.card) * d ^ 2) ∧
(frobNorm (W - cutMatrix S T d) ^ 2 - frobNorm W ^ 2
= -(blockSum W S T) ^ 2 / ((S.card : ℝ) * T.card)) := 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 (displayed computation of ‖W^(t+1)‖²_F − ‖W‖²_F)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.