§4.1, proof of Theorem 7, p. 188 — if |W(S,T)| > ε√(|S||T|)‖A‖_F, removing the block average lowers ‖W‖²_F by at least ε²‖A‖²_F
ProvedFriezeKannan.CutDecomp.frobenius_drop_leLet and be real matrices, let , and let , be a rectangle on which (17) fails:
(This forces and to be nonempty.) With ,
Each rectangle that violates the target bound (17) thus buys a fixed decrease of the squared Frobenius norm of the error, which is what limits the number of cut matrices to in Theorem 7.
Formalization Note The paper writes the violation as ""; the negation of (17) is the strict "", and with "" the empty rectangle would qualify and would divide by zero, so the strict form is stated. The hypothesis is the paper's standing range of the error parameter; some sign condition on is needed, since for the hypothesis holds for every rectangle with while the conclusion fails.
import Mathlib import Definitions.Def_FriezeKannan_CutDecomp_Setting
namespace FriezeKannan.CutDecomp
/-- §4.1, proof of Theorem 7, p. 188: if `|W(S, T)| > ε √(|S||T|) ‖A‖_F` then subtracting
`CUT(S, T, d)` with `d = W(S, T)/(|S||T|)` lowers `‖W‖²_F` by at least `ε² ‖A‖²_F`. -/
theorem frobenius_drop_le {R C : Type*} [Fintype R] [Fintype C] [DecidableEq R] [DecidableEq C]
(A W : Matrix R C ℝ) (ε : ℝ) (hε : 0 < ε) (S : Finset R) (T : Finset C)
(h : ε * Real.sqrt ((S.card : ℝ) * T.card) * frobNorm A < |blockSum W S T|) :
frobNorm (W - cutMatrix S T (blockSum W S T / ((S.card : ℝ) * T.card))) ^ 2
- frobNorm W ^ 2 ≤ -ε ^ 2 * frobNorm A ^ 2 := by sorry
end FriezeKannan.CutDecomp
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.