Corollary 21, p. 619 — weak triangle bound for squared shape costs
ProvedTinyCoreset.DimRed.corollary21_weak_triangleclusteringcoresetp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sum-of-squared-distances
Let , let , and let be nonempty. Then
This bounds how much a shape-fitting cost can change when every data point is perturbed.
Preamble
import Mathlib import Definitions.Def_ProjLikeRetr_FixedRank_SVD import Definitions.Def_TinyCoreset_DimRed_Setting
Formal statement
namespace TinyCoreset.DimRed
open scoped Matrix
theorem corollary21_weak_triangle {n d : ℕ} (ε : ℝ) (hε : 0 < ε)
(A B : Matrix (Fin n) (Fin d) ℝ)
(C : Set (EuclideanSpace ℝ (Fin d))) (hC : C.Nonempty) :
|distSq A C - distSq B C| ≤ ε * distSq A C + (1 + 1 / ε) * frobSq (A - B) := by sorry
end TinyCoreset.DimRed
Source
Feldman, Schmidt & Sohler, Turning Big Data into Tiny Data, SIAM J. Comput. 49(3) (2020), pp. 619–620, Corollary 21 and display (8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.