bernoulli_rademacher_moment_bound_by_conditional_khintchine_scales
DisprovedRole. 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. Integrate the pointwise conditional Khintchine bound over the Bernoulli sample. This is the finite-expectation monotonicity step between the conditional Rademacher estimate and the sampled-energy scale moment.
Lecture-note formulation:
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_rademacher open MatrixCompletion
theorem bernoulli_rademacher_moment_bound_by_conditional_khintchine_scales
(Ckh : ℝ) :
∀ (n₁ n₂ m q : ℕ) (X : Matrix (Fin n₁) (Fin n₂) ℝ),
(∀ Omega : Finset (Fin n₁ × Fin 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) →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
rademacherExpectation
(fun eps =>
spectralNorm
(rademacherSampledMatrix Omega eps
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q)) ≤
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
(Ckh * Real.sqrt (q : ℝ) *
(((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))⁻¹) *
Real.sqrt
(max (sampledRowEnergyMax Omega X)
(sampledColumnEnergyMax Omega X))) ^ q) := by
sorry