tangent_sampling_concentration_implies_least_squares_certificate_exists_pos
ProvedPOSITIVE-p CORRECTION of the disproved node tangent_sampling_concentration_implies_least_squares_certificate_exists (id 1ba6da65). With the inclusion probability strengthened to (the original allowed , where it is false: at with the tangent-concentration predicate holds vacuously, yet there is no supported on with , so no least-squares certificate exists). Claim: if and the tangent operator concentrates, , then the least-squares dual certificate problem (4.1) has a solution — i.e. there exists vanishing outside with that minimizes over all such matrices. This is the existence/well-definedness part of the certificate construction: concentration at scale makes well-conditioned, hence invertible on , so the ansatz of eq. (4.2) is well-defined and feasible, and the affine feasible set then admits a minimum-Frobenius-norm element. This is the genuine §4.2 invertibility core (it requires the finite-dimensional injective⟹surjective step and existence of the minimizer), not a pointwise algebraic identity. Source: Candès–Recht 2009 (arXiv:0805.4471), §4 "Architecture of the proof", eq. (4.1)-(4.2), p.17, and §4.2, Theorem 4.1 with the well-conditioning/invertibility conclusion after eq. (4.11), pp.19-20.
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
theorem tangent_sampling_concentration_implies_least_squares_certificate_exists_pos
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(Omega : Finset (Fin n₁ × Fin n₂)) (S : SVD M r) (p : ℝ) :
0 < p →
TangentSamplingConcentration Omega S p ((1 : ℝ) / 2) →
∃ Y : Matrix (Fin n₁) (Fin n₂) ℝ, LeastSquaresDualCertificate Omega S Y := by
sorry