tangent_diagonal_multiplier_sign_spectral_norm_bound_from_a1
Provedcandes-rechtcoherencelean4lemma-4-5lemma-6-4matrix-completionneumann-seriesspectral-norm
This is the A1-effective form of the diagonal tangent-kernel multiplier estimate used for the deterministic mean term in Lemma 4.5.
For a matrix , write
Specialized to the sign matrix , A1 gives the sharper effective coordinate-energy scale for the actual singular-vector energies. Hence there is a universal constant such that
Source: Candes-Recht 2008, PDF p. 4, assumption A1, and PDF p. 27, Lemma 6.4, equations (6.10)--(6.11); PDF p. 24 states that rectangular estimates replace by .
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
Formal statement
theorem tangent_diagonal_multiplier_sign_spectral_norm_bound_from_a1 :
∃ Cdiag : ℝ, 0 < Cdiag ∧
∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₁ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r → 1 ≤ μ₁ → A1 S μ₁ →
spectralNorm (tangentDiagonalMultiplier S (signMatrix S)) ≤
Cdiag * (μ₁ ^ 2 * (r : ℝ) / (↑(min n₁ n₂))) *
spectralNorm (signMatrix S) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.