tangent_sampling_deviation_eq_talagrand_supremum_deviation
Disprovedappendix-91candes-rechtlinear-algebramatrix-completionoperator-normsource-faithfultangent-space
This theorem is the linear-algebra representation step in Candes-Recht Appendix 9.1.
The project definition
is an operator norm over the tangent space. Appendix 9.1 rewrites the same random variable as the bilinear supremum
The formal statement says the two functions of are equal. This isolates the representation/duality step from the probabilistic Talagrand inequality.
Source location: Candes-Recht 2008, Appendix 9.1, PDF p. 46, immediately after equation (9.2), where is expanded into the supremum over and .
Preamble
import Definitions.Def_matrix_completion_talagrand_supremum open MatrixCompletion
Formal statement
theorem tangent_sampling_deviation_eq_talagrand_supremum_deviation
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (p : ℝ) :
(fun Omega : Finset (Fin n₁ × Fin n₂) =>
tangentSamplingDeviation Omega S p) =
(fun Omega : Finset (Fin n₁ × Fin n₂) =>
tangentSamplingTalagrandSupremumDeviation Omega S p) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.