§3.1, p. 8 — a unit vector's squared coordinate is bounded by leverage
ProvedInputSparsity.Embed.coordinate_boundleverage-scoresp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1subspace-embedding
Let have orthonormal columns, with leverage scores . Every unit vector in the column space of satisfies
This coordinate bound is the input to the paper's light-coordinate concentration analysis.
Formalization Note Unit length is expressed by ; the statement is independent of how the rows are ordered.
Preamble
import Mathlib import Definitions.Def_InputSparsity_Embed_SparseEmbedding
Formal statement
namespace InputSparsity.Embed
open Matrix
/-- Clarkson--Woodruff, §3.1, p. 8: a coordinate of a unit vector in the column space is bounded by its leverage score. -/
theorem coordinate_bound {n r : ℕ} (U : Matrix (Fin n) (Fin r) ℝ)
(hU : HasOrthonormalCols U) (y : Fin n → ℝ)
(hy : y ∈ LinearMap.range (Matrix.mulVecLin U)) (hunit : sqNorm y = 1) :
∀ i : Fin n, y i ^ 2 ≤ lev U i := by sorry
end InputSparsity.Embed
Source
Clarkson and Woodruff, Low Rank Approximation and Regression in Input Sparsity Time, arXiv:1207.6365v4, p. 8, §3.1, first paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.