Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 36, p. 24 — sketched multiple-response regression: ‖AỸ − B‖_F² ≤ (1 + 4ε)‖AY* − B‖_F²

Proved
InputSparsity.Regress.theorem_36

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

least-squaresp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-linear-algebraregressionsketchingsubspace-embedding

Let r≥1r\ge1r≥1 and ε>0\varepsilon>0ε>0. Let A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d have rank at most rrr, let U∈Rn×kU\in\mathbb R^{n\times k}U∈Rn×k be an orthonormal basis of the column space C(A)C(A)C(A), let B∈Rn×d′B\in\mathbb R^{n\times d'}B∈Rn×d′, and let S∈Rt×nS\in\mathbb R^{t\times n}S∈Rt×n be a fixed matrix. Let Y∗Y^*Y∗ be any solution of

min⁡Y∥AY−B∥F2(8)\min_Y\|AY-B\|_F^2\qquad(8)Ymin​∥AY−B∥F2​(8)

and suppose that

  1. SSS is a subspace embedding for AAA with parameter η∈[0,1/2]\eta\in[0,1/2]η∈[0,1/2]: ∣∥SAx∥22−∥Ax∥22∣≤η∥Ax∥22\bigl|\|SAx\|_2^2-\|Ax\|_2^2\bigr|\le\eta\|Ax\|_2^2​∥SAx∥22​−∥Ax∥22​​≤η∥Ax∥22​ for every x∈Rdx\in\mathbb R^dx∈Rd;
  2. SSS satisfies the approximate matrix multiplication event of Lemma 32 for the pair (U, B−AY∗)(U,\,B-AY^*)(U,B−AY∗) with error parameter ε/r\sqrt{\varepsilon/r}ε/r​:
∥U⊤S⊤S(B−AY∗)−U⊤(B−AY∗)∥F2≤εr ∥U∥F2 ∥B−AY∗∥F2.\|U^\top S^\top S(B-AY^*)-U^\top(B-AY^*)\|_F^2\le\frac{\varepsilon}{r}\,\|U\|_F^2\,\|B-AY^*\|_F^2 .∥U⊤S⊤S(B−AY∗)−U⊤(B−AY∗)∥F2​≤rε​∥U∥F2​∥B−AY∗∥F2​.

Then every solution Y~\tilde YY~ of the sketched problem

min⁡Y∥S(AY−B)∥F2(7)\min_Y\|S(AY-B)\|_F^2\qquad(7)Ymin​∥S(AY−B)∥F2​(7)

satisfies

∥AY~−B∥F2≤(1+4ε) ∥AY∗−B∥F2.\|A\tilde Y-B\|_F^2\le(1+4\varepsilon)\,\|AY^*-B\|_F^2 .∥AY~−B∥F2​≤(1+4ε)∥AY∗−B∥F2​.

Taking square roots, ∥AY~−B∥F≤1+4ε ∥AY∗−B∥F≤(1+2ε)∥AY∗−B∥F\|A\tilde Y-B\|_F\le\sqrt{1+4\varepsilon}\,\|AY^*-B\|_F\le(1+2\varepsilon)\|AY^*-B\|_F∥AY~−B∥F​≤1+4ε​∥AY∗−B∥F​≤(1+2ε)∥AY∗−B∥F​, which is the paper's (1+ϵ)(1+\epsilon)(1+ϵ) guarantee after rescaling ε\varepsilonε by a constant factor.

This is the sketch-and-solve principle for regression: solving the small problem min⁡Y∥SAY−SB∥F\min_Y\|SAY-SB\|_FminY​∥SAY−SB∥F​ gives a near-optimal solution of the original problem whenever SSS embeds C(A)C(A)C(A) and approximates the products U⊤(B−AY∗)U^\top(B-AY^*)U⊤(B−AY∗). 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: SSS is any matrix satisfying the two conditions. The conclusion is the squared bound with the explicit constant 444 that the proof derives; the printed "∥AY~−B∥F≤(1+ϵ)∥AY∗−B∥F\|A\tilde Y-B\|_F\le(1+\epsilon)\|AY^*-B\|_F∥AY~−B∥F​≤(1+ϵ)∥AY∗−B∥F​" holds only after a rescaling of ϵ\epsilonϵ that the paper leaves unspecified. η\etaη plays the role of the paper's ϵ02\epsilon_0^2ϵ02​ (ϵ0≤1/2  ⟺  η≤1/2\epsilon_0\le1/\sqrt2\iff\eta\le1/2ϵ0​≤1/2​⟺η≤1/2), as in the proof of Lemma 37 (p. 37). "SSS satisfies Lemma 32" is read as the event for the pair (U,B−AY∗)(U,B-AY^*)(U,B−AY∗) that the proof uses (p. 37), with ≤\le≤ for the printed <<<. Y~\tilde YY~ and Y∗Y^*Y∗ are arbitrary minimizers, since "the solution" need not be unique. r≥1r\ge1r≥1 makes ε/r\varepsilon/rε/r meaningful; the paper's "n>dn>dn>d" concerns running times and is not assumed.

Preamble
import Mathlib
import Definitions.Def_InputSparsity_Regress_Basic
Formal statement
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
Source
Clarkson and Woodruff, Low Rank Approximation and Regression in Input Sparsity Time, arXiv:1207.6365v4, p. 24, Theorem 36, (7), (8) and its proof
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me