sign_matrix_coordinate_energy_bounds_from_a1
Provedcandes-rechtcoherencelean4lemma-4-5lemma-6-4matrix-completionneumann-seriesspectral-norm
This lemma extracts coordinate-energy bounds from the A1 sign-matrix incoherence assumption.
Let have rank- SVD data and let
be the sign matrix. The A1 assumption says
for every coordinate . Since the rows of and the rows of are orthonormal, the row and column Euclidean norms of are exactly the coordinate energies
Therefore A1 implies
Source: Candes-Recht 2008, PDF p. 4, assumption A1, together with the SVD orthonormality identities used throughout Section 6.
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion open scoped Classical BigOperators
Formal statement
theorem sign_matrix_coordinate_energy_bounds_from_a1 :
∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₁ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r → 1 ≤ μ₁ → A1 S μ₁ →
(∀ i : Fin n₁,
∑ k : Fin r, (S.u k i) ^ 2 ≤ μ₁ ^ 2 * (r : ℝ) / (n₁ : ℝ)) ∧
(∀ j : Fin n₂,
∑ k : Fin r, (S.v k j) ^ 2 ≤ μ₁ ^ 2 * (r : ℝ) / (n₂ : ℝ)) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.