Fact 35, p. 23 — normal equations: X* = C⁻D solves min ‖CX − D‖_F², Cᵀ(CX* − D) = 0, and the error splits
ProvedInputSparsity.Regress.fact_35least-squareslinear-algebramoore-penrosenormal-equationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and a real matrix, and consider the multiple-response least-squares problem
Then:
- has a Moore–Penrose inverse (a matrix satisfying the four Penrose equations), and for every such the matrix is a minimizer.
- Every minimizer satisfies the normal equations .
- Consequently for every vector in the column space of .
- For every minimizer and every ,
The identity in 4 says that the excess error of any is exactly ; Theorem 36 bounds this quantity for the sketched solution.
Formalization Note The paper writes "the solution"; when is rank-deficient minimizers are not unique, so items 2–4 are stated for every minimizer, which is stronger than for alone. The pseudoinverse enters only through the Penrose equations. In item 3 the row vector is Lean's vecMul.
Preamble
import Mathlib import Definitions.Def_InputSparsity_Regress_Basic
Formal statement
namespace InputSparsity.Regress
open Matrix
theorem fact_35 {n d d' : ℕ} (C : Matrix (Fin n) (Fin d) ℝ) (D : Matrix (Fin n) (Fin d') ℝ) :
(∃ G : Matrix (Fin d) (Fin n) ℝ, IsMoorePenrose C G) ∧
(∀ G : Matrix (Fin d) (Fin n) ℝ, IsMoorePenrose C G → IsLSMinimizer C D (G * D)) ∧
(∀ Xstar : Matrix (Fin d) (Fin d') ℝ, IsLSMinimizer C D Xstar →
Cᵀ * (C * Xstar - D) = 0 ∧
(∀ x : Fin d → ℝ, (C *ᵥ x) ᵥ* (C * Xstar - D) = 0) ∧
(∀ X : Matrix (Fin d) (Fin d') ℝ,
InputSparsity.Embed.frobSq (C * X - D) = InputSparsity.Embed.frobSq (C * (X - Xstar)) + InputSparsity.Embed.frobSq (C * Xstar - D))) := by sorry
end InputSparsity.Regress
Source
Clarkson and Woodruff, Low Rank Approximation and Regression in Input Sparsity Time, arXiv:1207.6365v4, p. 23, Fact 35
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.