sum_rank_one_outer_product_square_collapse
Provedcandes-rechtlinear-algebramatrix-completionreferencerudelson
Gram-square collapse for a family of rank-one tensors. Summing the rank-one square collapse over a finite family: sum_c (y_c (x) y_c)^2 = sum_c ||y_c||^2 . (y_c (x) y_c). This is the sum X_c^2 = sum ||y_c||^2 (y_c (x) y_c) step of Rudelson's NC-Khintchine bound, immediately before the PSD-monotone domination by max_c ||y_c||^2 . sum (y_c (x) y_c). Proof: termwise application of the rank-one square collapse (yy*)^2 = ||y||^2 (yy*).
Preamble
import Mathlib.LinearAlgebra.Matrix.Trace import Mathlib.Data.Matrix.Mul import Mathlib.Data.Real.Basic open scoped BigOperators Matrix
Formal statement
theorem sum_rank_one_outer_product_square_collapse {d : Nat} {iota : Type*} (s : Finset iota) (y : iota → Fin d → Real) : ∑ c ∈ s, (Matrix.vecMulVec (y c) (y c) * Matrix.vecMulVec (y c) (y c)) = ∑ c ∈ s, (y c ⬝ᵥ y c) • Matrix.vecMulVec (y c) (y c) := by sorrySource
Rudelson, 'Random vectors in the isotropic position', J. Funct. Anal. 164 (1999), Thm 1 pp.3-6; van Handel, 'Structured Random Matrices', arXiv:1610.05200 Sec. 3 (Lemma 3.5); Candes-Recht 2009 (arXiv:0805.4471) Sec. 4.2 eq (4.9) p.18. These are the rank-one (outer-product) operator identities used by the noncommutative-Khintchine step of Rudelson's selection lemma; the rank-one summands are X_c = y_c (x) y_c on the Hilbert-Schmidt space, and the Gram square collapses by (yy*)^2 = ||y||^2 (yy*).