§4, eq. (17) — the Mahalanobis norm and the prior
DefinitionUnknownCovDP_General_Supplement_RelPriordifferential-privacymahalanobismean-estimationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix a dimension . This module sets up the experiment of §4.
- Mahalanobis norm. For a positive semidefinite matrix with Moore–Penrose pseudo-inverse and a vector ,
where is the column space of . 2. The prior (eq. (17)). The mean and the covariance are independent, with
So is the orthogonal projector onto the hyperplane , and exactly when . These objects are used by Theorem 4.1.
Formalization Note takes values in . The pseudo-inverse is the published LatentRobust.pinv (the unique matrix satisfying the four Penrose conditions). The uniform direction is realized as with , whose law is rotation invariant and carried by the sphere; the null point is sent to . The defining maps are proved measurable, so the laws are probability measures.
Definition code
import Mathlib
import Definitions.Def_UnknownCovDP_General_Model
import Definitions.Def_LatentRobust_pinv
open MeasureTheory ProbabilityTheory
open scoped ENNReal NNReal
namespace UnknownCovDP.General.Supplement
/-!
# The Mahalanobis norm `d_Σ` and the prior `P_rel`
Gaucher, Linder, Smith, Ullman, Zakynthinou, *Dimension-Free Private Mean Estimation is Impossible
Without the Covariance*, STOC 2027 submission #573 (October 2026), §4, the definition of `d_Σ` and
eq. (17) (printed p. 27, PDF p. 28).
**Formalization Note.**
* `d_Σ(y)` takes values in `[0, ∞]`: `√(yᵀ Σ† y)` when `y ∈ Span(Σ)` (the column space of `Σ`) and
`∞` otherwise. `Σ†` is the published Moore–Penrose inverse `LatentRobust.pinv`.
* The uniform direction `v` on the unit sphere of `ℝ^d` is realized as `g/‖g‖` with `g ∼ N(0, I_d)`,
whose law is rotation invariant and carried by the sphere (the null event `g = 0` maps to `0`).
The defining maps are proved measurable.
-/
/-- The Mahalanobis norm of `y` relative to `S` (§4, p. 27): `√(yᵀ S† y)` if `y ∈ Span(S)`, `∞`
otherwise. -/
noncomputable def mahalanobis {d : ℕ} (S : Mat d) (y : Vec d) : ℝ≥0∞ := by
classical
exact if (WithLp.ofLp y : Fin d → ℝ) ∈ LinearMap.range (Matrix.toLin' S) then
ENNReal.ofReal (Real.sqrt ((WithLp.ofLp y : Fin d → ℝ) ⬝ᵥ
(LatentRobust.pinv S).mulVec (WithLp.ofLp y)))
else ⊤
/-- `g ↦ g/‖g‖` (and `0 ↦ 0`). -/
noncomputable def normalize {d : ℕ} (g : Vec d) : Vec d := ‖g‖⁻¹ • g
lemma measurable_normalize (d : ℕ) : Measurable (normalize : Vec d → Vec d) :=
(measurable_norm.inv).smul measurable_id
/-- The uniform law on the unit sphere `{v : ‖v‖₂ = 1}` of `ℝ^d`: the law of `g/‖g‖`,
`g ∼ N(0, I_d)`. -/
noncomputable def sphereLaw (d : ℕ) : Measure (Vec d) :=
(multivariateGaussian (0 : Vec d) (1 : Mat d)).map normalize
/-- `v ↦ I_d − v vᵀ`. -/
noncomputable def relCov {d : ℕ} (v : Vec d) : Mat d :=
1 - Matrix.vecMulVec (WithLp.ofLp v) (WithLp.ofLp v)
lemma measurable_relCov (d : ℕ) : Measurable (relCov : Vec d → Mat d) := by
refine measurable_pi_iff.2 fun i => measurable_pi_iff.2 fun j => ?_
have h : (fun v : Vec d => relCov v i j) =
fun v => (1 : Mat d) i j - (WithLp.ofLp v) i * (WithLp.ofLp v) j := by
funext v; simp [relCov, Matrix.vecMulVec_apply]
rw [h]
exact measurable_const.sub
(((PiLp.continuous_apply 2 _ i).mul (PiLp.continuous_apply 2 _ j)).measurable)
instance sphereLaw_prob (d : ℕ) : IsProbabilityMeasure (sphereLaw d) :=
Measure.isProbabilityMeasure_map (measurable_normalize d).aemeasurable
/-- The `Σ`-marginal of `P_rel(d)` (eq. (17)): `Σ = I_d − v vᵀ` with `v` uniform on the unit
sphere. -/
noncomputable def relCovPrior (d : ℕ) : Measure (Mat d) :=
(sphereLaw d).map relCov
instance relCovPrior_prob (d : ℕ) : IsProbabilityMeasure (relCovPrior d) :=
Measure.isProbabilityMeasure_map (measurable_relCov d).aemeasurable
/-- The prior `P_rel(d)` of eq. (17): `μ ∼ N(0, I_d)` and, independently, `Σ = I_d − v vᵀ` with `v`
uniform on the unit sphere. -/
noncomputable def Prel (d : ℕ) : Measure (Vec d × Mat d) :=
(multivariateGaussian (0 : Vec d) (1 : Mat d)).prod (relCovPrior d)
end UnknownCovDP.General.Supplement
Source
Gaucher, Linder, Smith, Ullman, Zakynthinou, Dimension-Free Private Mean Estimation is Impossible Without the Covariance, STOC 2027 submission #573 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/573.pdf, §4, definition of d_Σ and eq. (17), printed p. 27 (PDF p. 28)