rademacher_sampled_matrix_conditional_khintchine_bound
ProvedRole. It is part of the symmetrization and matrix-moment machinery behind the spectral norm concentration estimates.
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. Noncommutative Khintchine specialized to the coordinate matrix series p^{-1} \sum \varepsilon_{ij} \delta_{ij} X_{ij} e_{i} e_{j}^\,, conditional on the sampled set Omega. The variance profile is the maximum sampled row/column energy.
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. A corresponding proof sketch reduces this node to smaller mathematical subclaims. The checked reduction uses 2 subclaims: spectral moment le Schatten moment for Rademacher sampled matrix; Rademacher sampled matrix Schatten moment Khintchine bound.
import Definitions.Def_matrix_completion_rademacher open MatrixCompletion
theorem rademacher_sampled_matrix_conditional_khintchine_bound :
∃ Ckh : ℝ, 0 < Ckh ∧
∀ (β : ℝ), 2 < β →
∀ (n₁ n₂ m q : ℕ)
(Omega : Finset (Fin n₁ × Fin n₂))
(X : Matrix (Fin n₁) (Fin n₂) ℝ),
1 ≤ q →
(q : ℝ) ≥ β * Real.log (↑(max n₁ n₂)) →
rademacherExpectation
(fun eps =>
spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q) ≤
(Ckh * Real.sqrt (q : ℝ) *
(((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))⁻¹) *
Real.sqrt
(max (sampledRowEnergyMax Omega X)
(sampledColumnEnergyMax Omega X))) ^ q := by
sorry