Regularized second moment , pseudoinverse, leverage and the score
DefinitionPFRelease_Supplement_phiLamLet be a nonempty dataset of vectors in , with null records represented by zero vectors and counted in . Its Gram matrix is and its regularized second moment is
For a real square matrix , is its Moore–Penrose pseudoinverse.
The -regularized leverage of with respect to is for , and for its limit as :
where . The friendliness score is , with , , and .
The score measures how well a record is explained by the reference data: it is large when lies in a thin ellipsoid shaped like the data, and it is the score of the Gaussian sketches (§5.2) and, with zero ridge, of the effective-resistance mechanism (§5.4).
Formalization Note Records are Option (EuclideanSpace ℝ ι) (none is ). The pseudoinverse is the matrix of the published Moore–Penrose pseudoinverse HarmonicGames.Decomposition.pinv of the map on Euclidean space. Leverages and scores take values in (ℝ≥0∞). The value of at the null record is not fixed by the paper; it is set to , and the theorems that use the score have inputs without null records. The definition is intended for .
import Mathlib
import Definitions.Def_PFRelease_Dataset
import Definitions.Def_HarmonicGames_Decomposition_Pinv
open Matrix
namespace PFRelease.Supplement
/-- The vector of a record of `ℝ^ι`, with the null record `⊥` represented by the zero vector
(Shenfeld, Tsfadia, Ligett, arXiv:2610.40654, held version sha256 e1d516b3…, Definition D.7, p.41 =
PDF p.43: "with null records represented by zero vectors"). -/
def recVec {ι : Type*} : Option (EuclideanSpace ℝ ι) → (ι → ℝ)
| none => 0
| some x => WithLp.ofLp x
/-- The Gram matrix `sᵀs = Σ_{slots} x xᵀ` of a dataset of vectors (Definition D.7, p.41; §D.4, p.50,
where it is the Laplacian `L_s = Σ_{e∈s} x_e x_eᵀ` of a dataset of edge records); null records
contribute zero and are still counted in `|s|`. -/
noncomputable def gram {ι : Type*} [Fintype ι] (l : List (Option (EuclideanSpace ℝ ι))) :
Matrix ι ι ℝ :=
(l.map fun x => vecMulVec (recVec x) (recVec x)).sum
/-- The regularized second moment `Σ̂_λ(s) := sᵀs/|s| + λ I_d` of a nonempty dataset of vectors
(Definition D.7, p.41 = PDF p.43). -/
noncomputable def secondMoment {ι : Type*} [Fintype ι] [DecidableEq ι] (lam : ℝ)
(l : List (Option (EuclideanSpace ℝ ι))) : Matrix ι ι ℝ :=
(l.length : ℝ)⁻¹ • gram l + lam • (1 : Matrix ι ι ℝ)
/-- The Moore–Penrose pseudoinverse `A†` of a real square matrix (§5.4, p.20; §D.4, p.50): the matrix of
the published Moore–Penrose pseudoinverse `HarmonicGames.Decomposition.pinv` of the linear map
`x ↦ A x` on the Euclidean space `ℝ^ι`.
**Formalization Note** `Matrix.toEuclideanLin` identifies matrices with linear maps of `EuclideanSpace ℝ ι`
(standard inner product), so `A†` is the usual matrix pseudoinverse; for a symmetric
`A = Q diag(μ) Qᵀ` it is `Q diag(μ†) Qᵀ` with `μ† = 1/μ` for `μ ≠ 0` and `0† = 0`. -/
noncomputable def pinv {ι : Type*} [Fintype ι] [DecidableEq ι] (A : Matrix ι ι ℝ) :
Matrix ι ι ℝ :=
Matrix.toEuclideanLin.symm (HarmonicGames.Decomposition.pinv (Matrix.toEuclideanLin A))
open Classical in
/-- The `λ`-regularized leverage `L_λ(s, x)` of a vector `x` with respect to a nonempty dataset `s`
(Definition D.7, p.41 = PDF p.43; the zero-ridge formula of §D.4, p.50 = PDF p.52):
`L_λ(s, x) := xᵀ Σ̂_λ(s)⁻¹ x` for `λ > 0`, and for `λ = 0` its limit as `λ → 0⁺`, which is
`xᵀ Σ̂_0(s)† x` if `x ∈ range(Σ̂_0(s))` and `∞` otherwise.
**Formalization Note** Values in `[0, ∞]`. For `λ = 0`, `Σ̂_0(s) = L_s/|s|`, so the finite branch is
`|s| xᵀ L_s† x` and the range is `range(L_s)`, exactly the display on p.50. The definition is intended
for `λ ≥ 0`; for `λ < 0` it returns the zero-ridge value (never used). -/
noncomputable def leverage {ι : Type*} [Fintype ι] [DecidableEq ι] (lam : ℝ)
(l : List (Option (EuclideanSpace ℝ ι))) (x : EuclideanSpace ℝ ι) : ENNReal :=
if 0 < lam then
ENNReal.ofReal (WithLp.ofLp x ⬝ᵥ ((secondMoment lam l)⁻¹ *ᵥ WithLp.ofLp x))
else if WithLp.ofLp x ∈ LinearMap.range (Matrix.toLin' (secondMoment 0 l)) then
ENNReal.ofReal (WithLp.ofLp x ⬝ᵥ (pinv (secondMoment 0 l) *ᵥ WithLp.ofLp x))
else ⊤
/-- The friendliness score `φ_λ(s, x) := 1/L_λ(s, x)` (Definition D.7, p.41 = PDF p.43; eq. (2),
p.17; with `λ = 0` the score `φ_0` of eq. (4), p.20), with `1/0 := ∞` and `1/∞ := 0`, and
`φ_λ(∅, x) := 0` (Definition 4.4).
**Formalization Note** `ENNReal` inversion gives `1/0 = ∞` and `1/∞ = 0`. The value at the null
record `⊥` (`none`) is unrestricted by the paper (footnote 5, p.12); it is set to `0` here and
never matters for the theorems, whose inputs have no null records. -/
noncomputable def phiLam {ι : Type*} [Fintype ι] [DecidableEq ι] (lam : ℝ) :
List (Option (EuclideanSpace ℝ ι)) → Option (EuclideanSpace ℝ ι) → ENNReal
| [], _ => 0
| _ :: _, none => 0
| y :: l, some x => (leverage lam (y :: l) x)⁻¹
end PFRelease.Supplement