Theorem 36, p. 24 — sketched multiple-response regression: ‖AỸ − B‖_F² ≤ (1 + 4ε)‖AY* − B‖_F²
ProvedInputSparsity.Regress.theorem_36Let and . Let have rank at most , let be an orthonormal basis of the column space , let , and let be a fixed matrix. Let be any solution of
and suppose that
- is a subspace embedding for with parameter : for every ;
- satisfies the approximate matrix multiplication event of Lemma 32 for the pair with error parameter :
Then every solution of the sketched problem
satisfies
Taking square roots, , which is the paper's guarantee after rescaling by a constant factor.
This is the sketch-and-solve principle for regression: solving the small problem gives a near-optimal solution of the original problem whenever embeds and approximates the products . It underlies the paper's input-sparsity-time regression and low-rank approximation algorithms, where random sketches satisfy both conditions with constant probability.
Formalization Note The statement is deterministic: is any matrix satisfying the two conditions. The conclusion is the squared bound with the explicit constant that the proof derives; the printed "" holds only after a rescaling of that the paper leaves unspecified. plays the role of the paper's (), as in the proof of Lemma 37 (p. 37). " satisfies Lemma 32" is read as the event for the pair that the proof uses (p. 37), with for the printed . and are arbitrary minimizers, since "the solution" need not be unique. makes meaningful; the paper's "" concerns running times and is not assumed.
import Mathlib import Definitions.Def_InputSparsity_Regress_Basic
namespace InputSparsity.Regress
open Matrix
theorem theorem_36 {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) ℝ) (ε η : ℝ) (Ystar Ytil : Matrix (Fin d) (Fin d') ℝ)
(hr : 1 ≤ r) (hrank : A.rank ≤ r)
(hε : 0 < ε) (hη₀ : 0 ≤ η) (hη : η ≤ 1 / 2)
(hU : IsOrthonormalBasisOf U A)
(hemb : IsSubspaceEmbedding S A η)
(hYstar : IsLSMinimizer A B Ystar)
(hamm : AMMEvent S U (B - A * Ystar) (Real.sqrt (ε / r)))
(hYtil : IsSketchedMinimizer S A B Ytil) :
InputSparsity.Embed.frobSq (A * Ytil - B) ≤ (1 + 4 * ε) * InputSparsity.Embed.frobSq (A * Ystar - B) := by sorry
end InputSparsity.Regress
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.