(9), p. 620 — Pythagorean split of shape cost
ProvedTinyCoreset.DimRed.eq9_pythagoras_for_shapesclusteringorthogonal-projectionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sum-of-squared-distances
Let and have complementary orthonormal columns. Let be nonempty and contained in the column space of . For every data matrix ,
This separates the cost perpendicular to the span of from the cost of the projected rows inside that span. It applies to both and in the paper.
Preamble
import Mathlib import Definitions.Def_ProjLikeRetr_FixedRank_SVD import Definitions.Def_TinyCoreset_DimRed_Setting
Formal statement
namespace TinyCoreset.DimRed
open scoped Matrix
theorem eq9_pythagoras_for_shapes {n d j : ℕ} (hjd : j ≤ d)
(X : Matrix (Fin d) (Fin j) ℝ) (Y : Matrix (Fin d) (Fin (d - j)) ℝ)
(hX : Xᵀ * X = 1) (hY : Yᵀ * Y = 1) (hXY : Xᵀ * Y = 0)
(B : Matrix (Fin n) (Fin d) ℝ)
(C : Set (EuclideanSpace ℝ (Fin d))) (hC : C.Nonempty)
(hCX : C ⊆ LinearMap.range (Matrix.toEuclideanLin X)) :
distSq B C = frobSq (B * Y) + distSq (B * X * Xᵀ) C := by sorry
end TinyCoreset.DimRed
Source
Feldman, Schmidt & Sohler, Turning Big Data into Tiny Data, SIAM J. Comput. 49(3) (2020), p. 620, display (9) and the preceding displayed line
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.