Self-bounding algebra:
Provedselfbounding_resolution_quadratic_linear_boundmatrix-completionprobabilityreal-analysis
Self-bounding desymmetrization algebra. If a nonnegative quantity satisfies the self-bounding recursion with , , then it linearises to . This is the elementary quadratic-formula resolution of the recursion arising in Rudelson's selection theorem, where is the right-hand-side quantity that Candes-Recht 2009 Theorem 4.2(1) / eq.(4.9) requires to be (encoded here as ). Writing , the hypothesis is ; under a short case split ( vs ) gives .
Preamble
import Mathlib.Analysis.SpecialFunctions.Sqrt import Mathlib.Tactic open Real
Formal statement
theorem selfbounding_resolution_quadratic_linear_bound :
∀ (EZ C A0 : ℝ), 0 ≤ EZ → 0 ≤ C → 0 ≤ A0 → A0 ≤ 1 →
EZ ≤ C * A0 + C * A0 * Real.sqrt EZ →
EZ ≤ 4 * (C + C ^ 2) * A0 := by sorrySource
Candes & Recht, Exact Matrix Completion via Convex Optimization, arXiv:0805.4471, sec 4.2 eq.(4.9) p.18; Rudelson, Random vectors in the isotropic position, J. Funct. Anal. 164 (1999).