sampled_row_column_energy_max_moment_from_row_and_column_bounds
DisprovedRole. It controls sampled row/column counts or energies, which feed the moment bounds for random sampled matrices.
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 . For sampled row/column nodes, counts observed entries in row , counts observed entries in column , and the corresponding energies sum over sampled entries. These estimates feed the noncommutative Khintchine and spectral-norm concentration bounds.
Claim. Combine separate row and column sampled-energy moment bounds into the moment bound for the maximum of the two energies.
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_neumann open MatrixCompletion
theorem sampled_row_column_energy_max_moment_from_row_and_column_bounds
(Crow Ccol : ℝ) :
∃ C : ℝ, 0 < C ∧
∀ {n₁ n₂ : ℕ} (m q : ℕ) (X : Matrix (Fin n₁) (Fin n₂) ℝ),
0 < Crow → 0 < Ccol →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega => sampledRowEnergyMax Omega X ^ q) ≤
(Crow * ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
(↑(max n₁ n₂)) * entrySupNorm X ^ 2) ^ q →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega => sampledColumnEnergyMax Omega X ^ q) ≤
(Ccol * ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
(↑(max n₁ n₂)) * entrySupNorm X ^ 2) ^ q →
bernoulliExpectation ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
(fun Omega =>
(max (sampledRowEnergyMax Omega X)
(sampledColumnEnergyMax Omega X)) ^ q) ≤
(C * ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
(↑(max n₁ n₂)) * entrySupNorm X ^ 2) ^ q := by
sorry