positive_bernoulli_least_squares_certificate_existence_from_tangent_concentration
Provedcandes-rechtlean4least-squares-certificatematrix-completionprobabilitytangent-space
This is the corrected positive-rate Bernoulli event transfer for least-squares certificate existence. Let be the Bernoulli sampling probability. If and the tangent-concentration event
has probability at least 1-c,n^{-eta}, then the event
also has probability at least 1-c,n^{-eta}. The assumption is essential: the zero-rate version has been disproved by the one-entry empty-sampling counterexample.
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem positive_bernoulli_least_squares_certificate_existence_from_tangent_concentration
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r)
(p c β : ℝ) :
0 < p → p ≤ 1 →
bernoulliEventProb p
(fun Omega => TangentSamplingConcentration Omega S p ((1 : ℝ) / 2)) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) →
bernoulliEventProb p
(fun Omega => ∃ Y : Matrix (Fin n₁) (Fin n₂) ℝ,
LeastSquaresDualCertificate Omega S Y) ≥
1 - c * Real.rpow (↑(max n₁ n₂)) (-β) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.