Fact 34, p. 23 — Pythagorean theorem: CᵀD = 0 implies ‖C + D‖_F² = ‖C‖_F² + ‖D‖_F²
ProvedInputSparsity.Regress.fact_34frobenius-normleast-squareslinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be real matrices (the same number of rows and of columns). If , then
This is the matrix (Frobenius) form of the Pythagorean theorem. Combined with the normal equations (Fact 35) it splits the regression error into an irreducible part and a part caused by a suboptimal solution, which is the first step of the proof of Theorem 36.
Formalization Note is the explicit sum of squared entries.
Preamble
import Mathlib import Definitions.Def_InputSparsity_Regress_Basic
Formal statement
namespace InputSparsity.Regress
open Matrix
theorem fact_34 {n m : ℕ} (C D : Matrix (Fin n) (Fin m) ℝ) (h : Cᵀ * D = 0) :
InputSparsity.Embed.frobSq (C + D) = InputSparsity.Embed.frobSq C + InputSparsity.Embed.frobSq 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 34
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.