scalar_centered_sampling_bernstein_natural_tail_from_quadratic_base_bounds
ProvedRole. It is a centered-sampling fluctuation estimate, one of the reusable concentration interfaces used repeatedly by the Neumann-term bounds.
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. Generic fixed-coordinate scalar Bernstein estimate at the natural quadratic kernel-square scale. A scalar random variable represented as the entry-sum of a centered sampling fluctuation is controlled from entry-sup and Frobenius bounds for the base matrix.
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 4 subclaims: scalar centered sampling bernstein tail from entry Frobenius scales; quadratic base scalar bernstein natural scale absorption; Bernoulli event probability mono; sample ratio between zero and one.
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
theorem scalar_centered_sampling_bernstein_natural_tail_from_quadratic_base_bounds
(Centry Cfro : ℝ) :
0 < Centry → 0 < Cfro →
∃ Cpoint cpoint : ℝ, 0 < Cpoint ∧ 0 < cpoint ∧
∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
∀ (n₁ n₂ r m : ℕ) (μ₀ : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
1 ≤ μ₀ →
(m : ℝ) ≥
lam * Real.rpow μ₀ ((4 : ℝ) / 3) *
(↑(max n₁ n₂)) * Real.rpow (r : ℝ) ((4 : ℝ) / 3) *
(β * Real.log (↑(max n₁ n₂))) →
∀ (Coeff : Finset (Fin n₁ × Fin n₂) → ℝ)
(B : Matrix (Fin n₁) (Fin n₂) ℝ),
(∀ Omega : Finset (Fin n₁ × Fin n₂),
Coeff Omega =
matrixEntrySum
(centeredSamplingFluctuation Omega
((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) B)) →
entrySupNorm B ≤
Centry * μ₀ ^ 2 *
(((r : ℝ) / (↑(max n₁ n₂))) ^ 2) →
frobeniusNorm B ≤
Cfro * Real.rpow μ₀ ((3 : ℝ) / 2) *
Real.rpow ((r : ℝ) / (↑(max n₁ n₂))) ((3 : ℝ) / 2) →
bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
|Coeff Omega| ≤
Cpoint *
Real.sqrt (β * Real.log (↑(max n₁ n₂))) *
Real.rpow
((μ₀ * (↑(max n₁ n₂)) * (r : ℝ)) / (m : ℝ))
((3 : ℝ) / 2)) ≥
1 - cpoint * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry