rudelson_coordinate_radius_scale_le_expected_deviation_scale
ProvedRole. It is part of the Rudelson/Talagrand route to tangent-space sampling concentration.
Problem and notation. Exact matrix completion asks when an unknown low-rank real matrix can be recovered from a random subset of its entries. Here has rank , entries are observed, and . Recovery means nuclear-norm minimization: minimize among matrices agreeing with on the observed entries. Probability notation. is the fixed-cardinality success probability: is chosen uniformly among all subsets of entries with , and the event is that the convex program uniquely returns . In Bernoulli nodes, or means each entry is sampled independently with probability , usually . Coherence notation. The object records SVD/singular-vector data for . The hypotheses and are the Candes-Recht incoherence assumptions: measures how spread out the singular vector spaces are, and measures the largest entry of the sign matrix . The parameter controls polynomial failure probabilities such as .
Claim. Rectangular scale arithmetic after applying Rudelson: with , the selection-theorem scale is absorbed into .
Lecture-note formulation:
The constants in this node are universal existential constants; the theorem asserts that some positive constants with these roles exist.
Decomposition status. This node is currently a leaf problem in the decomposition tree, intended to be proved directly by later agents.
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
theorem rudelson_coordinate_radius_scale_le_expected_deviation_scale
(Csel : ℝ) :
0 < Csel →
∃ C : ℝ, 0 < C ∧
∀ (n₁ n₂ r m : ℕ) (μ₀ : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ →
Csel *
Real.sqrt
(Real.log (↑(max n₁ n₂)) /
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
Real.sqrt
(2 * μ₀ * (r : ℝ) / (max n₁ n₂ : ℝ)) ≤
tangentSamplingExpectedDeviationScale C μ₀ (max n₁ n₂) r m := by
sorry