§8, proof of Theorem 12, p. 217 — if |w(S,T)| > ε‖f‖₂ then subtracting CUT(S,T,d) lowers ‖w‖²₂ by at least ε²‖f‖²₂
ProvedFriezeKannan.Continuum.l2_drop_lecut-decompositionl2-spacep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-regularity
Let and be real functions on with square integrable, let , and let be measurable sets with
Put , where is the Lebesgue measure of . Then
In the proof of Theorem 12, is the current error and the function being decomposed; each new cut function lowers the squared error by at least , which bounds the number of steps by .
Formalization Note. is the paper's implicit range of the error parameter. No positivity of is assumed: it follows from the hypothesis, since when . No hypothesis on is needed beyond what means; is the square root of .
Preamble
import Mathlib import Definitions.Def_FriezeKannan_Continuum_Setting open MeasureTheory
Formal statement
namespace FriezeKannan.Continuum
theorem l2_drop_le (f w : Sq → ℝ) (hw : MemLp w 2) (ε : ℝ) (hε : 0 < ε)
(S T : Set unitInterval) (hS : MeasurableSet S) (hT : MeasurableSet T)
(h : ε * l2Norm f < |rectInt w S T|) :
let d := rectInt w S T / ((volume S).toReal * (volume T).toReal)
l2Norm (fun p => w p - cutFun S T d p) ^ 2 - l2Norm w ^ 2 ≤ -ε ^ 2 * l2Norm f ^ 2 := by sorry
end FriezeKannan.Continuum
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 217, §8, proof of Theorem 12 (final inequality of the displayed computation)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.