tangent_sampling_deviation_candidates_bddAbove
Provedcandes-rechtfinite-dimensionalleafmatrix-completionsupremumtangent-space
This leaf supplies the boundedness hypothesis needed to use the supremum in the definition of tangent sampling deviation.
For fixed SVD data , observation set , and rate , consider the finite-dimensional candidate set
The theorem asserts that this set is bounded above. Mathematically this follows because , , and the identity map are linear operators on a finite-dimensional real matrix space, and a linear operator is bounded on the Frobenius unit ball. This is separated as its own leaf so the parent concentration argument can use the supremum cleanly.
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem tangent_sampling_deviation_candidates_bddAbove
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(Omega : Finset (Fin n₁ × Fin n₂)) (S : SVD M r) (p : ℝ) :
BddAbove {v : ℝ |
∃ X : Matrix (Fin n₁) (Fin n₂) ℝ,
tangentProjection S X = X ∧ frobeniusNorm X ≤ 1 ∧
v = (p⁻¹) *
frobeniusNorm
(tangentProjection S (samplingProjection Omega X) - p • X)} := by
sorrySource
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.