Lemma 7 — sup norm of a uniform spherical direction
ProvedAdaptiveStepIPM.Probabilistic.lemma_7p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-subspaces
For every , let be an orthogonal matrix, and draw uniformly from the unit sphere in . The frames may vary arbitrarily with . Then
This is the probabilistic coordinate bound applied to the direction from Lemma 6 in the proof of Theorem 5.
Formalization Note The spherical law is the normalized standard Gaussian law. The finitely many dimensions below two are assigned probability one in the limit expression; no orthogonal frame is requested there.
Preamble
import Definitions.Def_AdaptiveStepIPM_Probabilistic_Model open MeasureTheory ProbabilityTheory Filter
Formal statement
namespace AdaptiveStepIPM.Probabilistic
/-- Lemma 7 for an arbitrary sequence of orthogonal frames. -/
theorem lemma_7 (F : ∀ n : ℕ, 2 ≤ n → Frame n) :
Tendsto (fun n : ℕ =>
if hn : 2 ≤ n then
((sphereGaussian (n - 1))
{v | supNorm ((F n hn).H v) ≤
Real.sqrt (3 * Real.log (n : ℝ) / (n : ℝ))}).toReal
else 1) atTop (nhds 1) := by sorry
end AdaptiveStepIPM.Probabilistic
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 15, Lemma 7; https://doi.org/10.1287/moor.18.4.964
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.