tangent_sampling_concentration_controls_unsampled_tangent_frobenius_norm
ProvedRole. It belongs to the tangent-space injectivity branch, where concentration of the sampled tangent operator rules out nonzero feasible tangent perturbations.
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 tangent-space nodes, the main event is that the sampled tangent operator is well conditioned; this prevents a nonzero tangent perturbation from agreeing with M on the sampled entries.
Claim. Under positive sampling rate, the 1/2 tangent concentration estimate forces every tangent vector invisible to sampling to have zero Frobenius norm.
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_tangent open MatrixCompletion
theorem tangent_sampling_concentration_controls_unsampled_tangent_frobenius_norm
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(Omega : Finset (Fin n₁ × Fin n₂)) (S : SVD M r) (p : ℝ)
(H : Matrix (Fin n₁) (Fin n₂) ℝ) :
0 < p →
TangentSamplingConcentration Omega S p ((1 : ℝ) / 2) →
tangentProjection S H = H →
samplingProjection Omega H = 0 →
frobeniusNorm H = 0 := by
sorry