§8, proof of Theorem 12, p. 217 — if ‖w_t‖²₂ ≤ (1 − ε²t)‖f‖²₂ then (63) holds or one more cut function gives ‖w_{t+1}‖²₂ ≤ (1 − ε²(t+1))‖f‖²₂
ProvedFriezeKannan.Continuum.inductive_stepcut-decompositionl2-spacep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1weak-regularity
Let be a measurable real function on with , and let . Suppose , , are cut functions with measurable , and that the error satisfies
Then one of the following holds:
- for all measurable , i.e. (inequality (63) with );
- there are measurable and a real such that
This is the induction of the proof of Theorem 12: as long as the cut norm of the error exceeds , one more cut function preserves the invariant with replaced by .
Formalization Note. The family of cut functions is indexed by (the page's is the empty sum). The cut norm bound is the definition unfolded over measurable . is the paper's implicit range. " measurable with " is MemLp f 2 (which includes almost-everywhere measurability, i.e. Lebesgue measurability).
Preamble
import Mathlib import Definitions.Def_FriezeKannan_Continuum_Setting open MeasureTheory
Formal statement
namespace FriezeKannan.Continuum
theorem inductive_step (f : Sq → ℝ) (hf : MemLp f 2)
(ε : ℝ) (hε : 0 < ε)
(t : ℕ) (Ss Ts : Fin t → Set unitInterval) (d : Fin t → ℝ)
(hmS : ∀ j, MeasurableSet (Ss j) ∧ MeasurableSet (Ts j))
(hinv : l2Norm (fun p => f p - cutFunSum Ss Ts d p) ^ 2
≤ (1 - ε ^ 2 * t) * l2Norm f ^ 2) :
(∀ S T : Set unitInterval, MeasurableSet S → MeasurableSet T →
|rectInt (fun p => f p - cutFunSum Ss Ts d p) S T| ≤ ε * l2Norm f) ∨
∃ (S T : Set unitInterval) (d' : ℝ), MeasurableSet S ∧ MeasurableSet T ∧
l2Norm (fun p => f p - cutFunSum Ss Ts d p - cutFun S T d' p) ^ 2
≤ (1 - ε ^ 2 * (t + 1)) * 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 (inductive hypothesis and the case split)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.