a0_implies_tangent_coordinate_frobenius_bound_min
Provedlinear-algebramatrix-completion
Corrected Candès–Recht coordinate Frobenius estimate. Under the coherence assumption A0 (both column and row singular spaces have coherence at most ), every projected coordinate basis matrix satisfies . This is the true estimate: writing and , one has the exact identity . (This replaces the earlier form, which is false when .)
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem a0_implies_tangent_coordinate_frobenius_bound_min {n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r) (μ₀ : ℝ) : 0 < n₁ → 0 < n₂ → 0 < r → 1 ≤ μ₀ → A0 S μ₀ → TangentCoordinateFrobeniusBound S (2 * μ₀ * (r : ℝ) / (min n₁ n₂ : ℝ)) := by sorrySource
Candès, Recht, Exact Matrix Completion via Convex Optimization (2009), §3