CR eq. (4.8): min-dimension increment feed for Talagrand
Provedtangent_sampling_talagrand_increment_bound_from_coordinate_bound_minconcentrationmatrix-completionprobability
Dimension-correct (min-radius) Talagrand increment feed for the tangent sampling deviation. From the ACHIEVABLE coordinate Frobenius estimate (Candès-Recht eq. (4.8); the min-dimension is the binding one — the max-dimension variant is FALSE from A0), the Talagrand increment (uniform boundedness) hypothesis holds with , where . Proof: Cauchy-Schwarz on the Frobenius inner product gives for unit ; then via . This replaces the unsatisfiable max-radius hypothesis of tangent_sampling_talagrand_increment_bound_from_coordinate_bound with the achievable min-radius one (same output B).
Preamble
import Definitions.Def_matrix_completion_talagrand open MatrixCompletion
Formal statement
theorem tangent_sampling_talagrand_increment_bound_from_coordinate_bound_min :
∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r → 0 < m → m ≤ n₁ * n₂ →
1 ≤ μ₀ →
TangentCoordinateFrobeniusBound S
(2 * μ₀ * (r : ℝ) / (min n₁ n₂ : ℝ)) →
TangentSamplingTalagrandIncrementBound S
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) := by sorrySource
Candès & Recht, Exact Matrix Completion via Convex Optimization, arXiv:0805.4471, eq. (4.8) coordinate Frobenius estimate (2μ₀r/min(n₁,n₂)) and §9.1.