Lemma 37, p. 24 — for A with orthonormal columns, ‖A(Ỹ − Y*)‖_F ≤ 2√ε‖B − AY*‖_F
ProvedInputSparsity.Regress.lemma_37least-squaresp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-linear-algebrasketchingsubspace-embedding
Let and . Let have orthonormal columns () with , let , and let . Suppose that
- is a subspace embedding for with parameter : for all ;
- minimizes ;
- satisfies the approximate matrix multiplication event of Lemma 32 for the pair with error parameter : ;
- minimizes .
Then
This is the core estimate of the sketch-and-solve analysis: the sketched solution is close to the true one in the geometry of .
Formalization Note "For and as in Theorem 36" is spelled out. With orthonormal columns , so "rank at most " is . The embedding parameter plays the role of the paper's , and becomes : the proof (Appendix A, p. 37) bounds by and uses ; under the norm convention of §1.2 with the constant would fail. The Lemma 32 event is the inequality it is used as in the proof (p. 37), with for the printed .
Preamble
import Mathlib import Definitions.Def_InputSparsity_Regress_Basic
Formal statement
namespace InputSparsity.Regress
open Matrix
theorem lemma_37 {n k d' t : ℕ} (r : ℕ) (A : Matrix (Fin n) (Fin k) ℝ)
(B : Matrix (Fin n) (Fin d') ℝ) (S : Matrix (Fin t) (Fin n) ℝ) (ε η : ℝ)
(Ystar Ytil : Matrix (Fin k) (Fin d') ℝ)
(hr : 1 ≤ r) (hA : InputSparsity.Embed.HasOrthonormalCols A) (hk : k ≤ r)
(hε : 0 < ε) (hη₀ : 0 ≤ η) (hη : η ≤ 1 / 2)
(hemb : IsSubspaceEmbedding S A η)
(hYstar : IsLSMinimizer A B Ystar)
(hamm : AMMEvent S A (B - A * Ystar) (Real.sqrt (ε / r)))
(hYtil : IsSketchedMinimizer S A B Ytil) :
Real.sqrt (InputSparsity.Embed.frobSq (A * (Ytil - Ystar))) ≤
2 * Real.sqrt ε * Real.sqrt (InputSparsity.Embed.frobSq (B - A * Ystar)) := by sorry
end InputSparsity.Regress
Source
Clarkson and Woodruff, Low Rank Approximation and Regression in Input Sparsity Time, arXiv:1207.6365v4, p. 24, Lemma 37 (proof in Appendix A, p. 37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.