rudelson_selection_expected_tangent_deviation_from_coordinate_radius_bound_dense_proviso
ProvedCorrected Rudelson selection estimate (expected tangent-sampling deviation) WITH the Candès–Recht Theorem 4.2 “right-hand side ” proviso. There is an absolute constant such that for every , all sizes with , every reduced SVD of , and every radius : if the sampling is dense, , if the desymmetrization parameter is bounded, (with ), and if every tangent-coordinate projection has Frobenius norm at most , then the expected tangent-sampling deviation is at most . The added proviso is exactly Candès–Recht 2009, Theorem 4.2 part 1 (eq. (4.9), p.18): “provided the right-hand side is smaller than 1.” It comes from the self-bounding desymmetrization with , which yields the linear bound only when ; without it the stated linear bound can fail (the true bound is when ). This corrects the radius_dense node which omitted the proviso (R a free parameter).
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
theorem rudelson_selection_expected_tangent_deviation_from_coordinate_radius_bound_dense_proviso :
∃ Csel : ℝ, 0 < Csel ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(S : SVD M r) (R : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
0 ≤ R →
(m : ℝ) ≥ β * (↑(max n₁ n₂)) * (r : ℝ) *
Real.log (↑(max n₁ n₂)) →
Real.sqrt
(Real.log (↑(max n₁ n₂)) /
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) * R ≤ 1 →
(∀ i : Fin n₁, ∀ j : Fin n₂,
frobeniusNorm (tangentProjection S (coordinateMatrix i j)) ≤ R) →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
tangentSamplingDeviation Omega S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) ≤
Csel *
Real.sqrt
(Real.log (↑(max n₁ n₂)) /
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
R := by sorry