Definition 6.4 — -approximate observable-operator family
DefinitionSelfSelReg_Supplement_ObservableFamilyhermite-momentslearning-theorylinear-regressionp2o-gran-per-chapterp2o-plan-paperp2o-v1self-selection
Let be a finite index set with elements and let be vectors of . Symmetric matrices form an -approximate observable-operator family for if there is an orthonormal basis of such that, for every ,
The basis is chosen once and serves every : every contraction is then close to a matrix with the same eigenvectors and eigenvalues , which is what lets an eigendecomposition read off the vectors coordinate by coordinate (Theorem 6.6).
Formalization Note is a finite subset of the index set of a family . The conditions and are stated by the theorems that use the definition.
Definition code
import Mathlib
import Definitions.Def_SelfSelReg_Tensor
namespace SelfSelReg
namespace Supplement
/-- **Definition 6.4** (Approximate Observable-Operator Family).
F. Zhou, *Linear Regression with Self-Selection Bias in Polynomial Time*, STOC 2027 submission
(manuscript sha256 5d65f750…), Definition 6.4, p.30 (PDF p.33): "Fix a non-empty set J and vectors
(a_i)_{i∈J} in ℝⁿ. For ε_fam ≥ 0, we call symmetric matrices D̂_1, …, D̂_n ∈ ℝ^{|J|×|J|} an
ε_fam-approximate observable-operator family for (a_i)_{i∈J} if there is an orthonormal basis
(z_i)_{i∈J} of ℝ^{|J|} such that, for every b ∈ ℝⁿ,
‖Σ_ℓ b_ℓ D̂_ℓ − Σ_{i∈J} ⟨b, a_i⟩ z_i z_iᵀ‖_F ≤ ε_fam ‖b‖₂ (41)."
**Formalization Note.** `J` is a finite subset of the index type of the family `a`, with `|J| = p`.
The basis is an orthonormal family `z` indexed by the elements of `J`; having `|J| = p` members in
`ℝᵖ`, it is a basis. It is chosen once, before `b`. Symmetry of the `D̂_ℓ` is a clause of the
predicate; `J ≠ ∅` and `ε_fam ≥ 0` are left to the theorems. -/
def IsApproxObservableFamily {n k p : ℕ} (a : Fin k → EuclideanSpace ℝ (Fin n))
(J : Finset (Fin k)) (_hcard : J.card = p)
(D : Fin n → Matrix (Fin p) (Fin p) ℝ) (εfam : ℝ) : Prop :=
(∀ l, (D l).IsHermitian) ∧
∃ z : {i : Fin k // i ∈ J} → EuclideanSpace ℝ (Fin p),
(∀ i j, inner ℝ (z i) (z j) = if i = j then (1 : ℝ) else 0) ∧
∀ b : EuclideanSpace ℝ (Fin n),
matFrobNorm ((∑ l, b l • D l) -
∑ i : {i : Fin k // i ∈ J}, inner ℝ b (a i) • Matrix.vecMulVec (z i) (z i)) ≤ εfam * ‖b‖
end Supplement
end SelfSelReg
Source
Zhou, Linear Regression with Self-Selection Bias in Polynomial Time, STOC 2027 submission (manuscript sha256 5d65f750…), Definition 6.4, Eq. (41), p.30 (PDF p.33)