Theorem 39, p. 25 — affine embedding: S preserves ‖AX − B‖² up to 2ε (weak) and 3ε if it also preserves ‖B̃‖²
ProvedInputSparsity.Regress.theorem_39Let and . Let have rank at most , let be an orthonormal basis of its column space, let and . Let minimize and set . Suppose that
- is a subspace embedding for with parameter : for all ;
- satisfies the approximate matrix multiplication event of Lemma 32 for the pair with error parameter : .
Then for every ,
so is an affine embedding with relative error up to an additive constant (a weak affine embedding). If moreover , then for every
which is display (9): is a -affine embedding.
Since adding a constant does not change minimizers, the weak form already suffices for sketched optimization; the strong form preserves the objective value itself.
Formalization Note The norms are Frobenius norms (the paper writes ). "" is read as up to an error of , as the proof shows. The subspace embedding is in squared form with parameter , as the proof uses it. The Lemma 32 event is for the pair , the pair the proof uses after replacing by an orthonormal basis of ; replaces the printed . is a named matrix fixed by the hypothesis .
import Mathlib import Definitions.Def_InputSparsity_Regress_Basic
namespace InputSparsity.Regress
open Matrix
theorem theorem_39 {n d d' t k : ℕ} (r : ℕ) (A : Matrix (Fin n) (Fin d) ℝ)
(B : Matrix (Fin n) (Fin d') ℝ) (S : Matrix (Fin t) (Fin n) ℝ)
(U : Matrix (Fin n) (Fin k) ℝ) (ε : ℝ) (Xstar : Matrix (Fin d) (Fin d') ℝ)
(Btil : Matrix (Fin n) (Fin d') ℝ)
(hr : 1 ≤ r) (hrank : A.rank ≤ r) (hε : 0 < ε) (hε' : ε ≤ 1 / 2)
(hU : IsOrthonormalBasisOf U A)
(hemb : IsSubspaceEmbedding S A ε)
(hXstar : IsLSMinimizer A B Xstar)
(hBtil : Btil = A * Xstar - B)
(hamm : AMMEvent S U Btil (ε / Real.sqrt r)) :
(∀ X : Matrix (Fin d) (Fin d') ℝ,
|(InputSparsity.Embed.frobSq (S * (A * X - B)) - InputSparsity.Embed.frobSq (S * Btil)) - (InputSparsity.Embed.frobSq (A * X - B) - InputSparsity.Embed.frobSq Btil)| ≤
2 * ε * InputSparsity.Embed.frobSq (A * X - B)) ∧
(|InputSparsity.Embed.frobSq (S * Btil) - InputSparsity.Embed.frobSq Btil| ≤ ε * InputSparsity.Embed.frobSq Btil →
∀ X : Matrix (Fin d) (Fin d') ℝ,
|InputSparsity.Embed.frobSq (S * (A * X - B)) - InputSparsity.Embed.frobSq (A * X - B)| ≤ 3 * ε * InputSparsity.Embed.frobSq (A * X - B)) := by sorry
end InputSparsity.Regress
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.