Projected samples with , and their law
DefinitionSelfSelReg_Supplement_ProjectedSamplehermite-momentslearning-theorylinear-regressionp2o-gran-per-chapterp2o-plan-paperp2o-v1self-selection
Theorem 8.1 assumes "fresh samples where ". Here is an observation of the self-selection model with regressors , the vector is independent of it, and is a projection map, so that
The bundle defines this vector and two laws:
- the law of , the projected sample of Theorem 8.1(i);
- the law of , used for Theorem 8.1(ii): the odd features (108) contain the coordinate , so the supplied sample must carry as well.
The projected samples are how the estimation routine works with order- tensor features without ever forming a vector of entries.
Formalization Note A complex vector is stored as its real part followed by its imaginary part. Independent draws from these laws are "fresh": they are independent of the recovered list and of , which are fixed beforehand.
Definition code
import Mathlib
import Definitions.Def_SelfSelReg_jointLaw
import Definitions.Def_SelfSelReg_Tensor
open MeasureTheory ProbabilityTheory
namespace SelfSelReg
namespace Supplement
/-- The projected complex tensor power `U X̃^{⊗r} ∈ ℂᵖ`, `X̃ = X + iX′` (Theorem 8.1 and (107), (108),
pp.55–57, PDF pp.58–60): coordinate `a` is `Σ_J U_{a,J} ∏_h (x_{J_h} + i x′_{J_h})`. -/
noncomputable def projectedComplex {n p r : ℕ} (U : Matrix (Fin p) (Fin r → Fin n) ℝ)
(x x' : EuclideanSpace ℝ (Fin n)) : Fin p → ℂ :=
fun a => ∑ J, (U a J : ℂ) * ∏ h, ((x (J h) : ℂ) + Complex.I * (x' (J h) : ℂ))
/-- One projected sample `(X, U X̃^{⊗r}, Y_max)` as a vector of `ℝ^{n+2p+1}`: coordinates `0, …, n − 1`
are `X`, the next `p` are `Re(U X̃^{⊗r})`, the next `p` are `Im(U X̃^{⊗r})`, the last is `Y_max`. -/
noncomputable def projectedSampleOf {n k p r : ℕ}
(w : Fin k → EuclideanSpace ℝ (Fin n)) (U : Matrix (Fin p) (Fin r → Fin n) ℝ)
(z : (EuclideanSpace ℝ (Fin n) × EuclideanSpace ℝ (Fin k)) × EuclideanSpace ℝ (Fin n)) :
EuclideanSpace ℝ (Fin (n + 2 * p + 1)) :=
WithLp.toLp 2 fun m =>
if hX : (m : ℕ) < n then z.1.1 ⟨m, hX⟩
else if hRe : (m : ℕ) < n + p then (projectedComplex U z.1.1 z.2 ⟨m - n, by omega⟩).re
else if hIm : (m : ℕ) < n + 2 * p then (projectedComplex U z.1.1 z.2 ⟨m - (n + p), by omega⟩).im
else yMax w z.1.1 z.1.2
/-- **The law of one projected sample** `(X, U X̃^{⊗r}, Y_max)`.
F. Zhou, *Linear Regression with Self-Selection Bias in Polynomial Time*, STOC 2027 submission
(manuscript sha256 5d65f750…), Theorem 8.1, p.55 (PDF p.58): "fix a projection map U : ℝ^{n^r} → ℝᵖ,
where U ∈ ℝ^{p×n^r} has orthonormal rows. Assume we are given fresh samples (X, U X̃^{⊗r}, Y_max) where
X̃ = X + iX′."
`(X, ξ)` has the law `jointLaw n k` of the model and `X′ ∼ N(0, I_n)` is independent of it (§4.4, (13),
p.17: the complex component of the Hermite representation).
**Formalization Note.** The complex vector `U X̃^{⊗r}` is stored as its real and imaginary parts. A
stream of independent draws from this law is "fresh": it is independent of the recovered list and of
`U`, which are fixed before it. -/
noncomputable def projectedSampleLaw {n k p r : ℕ}
(w : Fin k → EuclideanSpace ℝ (Fin n)) (U : Matrix (Fin p) (Fin r → Fin n) ℝ) :
Measure (EuclideanSpace ℝ (Fin (n + 2 * p + 1))) :=
((jointLaw n k).prod (stdGaussian (EuclideanSpace ℝ (Fin n)))).map (projectedSampleOf w U)
/-- One projected sample that also carries the complex component: `(X, X′, U X̃^{⊗r}, Y_max)` as a
vector of `ℝ^{2n+2p+1}` (`X`, then `X′`, then real parts, imaginary parts, and `Y_max` last). -/
noncomputable def projectedSampleOfOdd {n k p r : ℕ}
(w : Fin k → EuclideanSpace ℝ (Fin n)) (U : Matrix (Fin p) (Fin r → Fin n) ℝ)
(z : (EuclideanSpace ℝ (Fin n) × EuclideanSpace ℝ (Fin k)) × EuclideanSpace ℝ (Fin n)) :
EuclideanSpace ℝ (Fin (2 * n + 2 * p + 1)) :=
WithLp.toLp 2 fun m =>
if hX : (m : ℕ) < n then z.1.1 ⟨m, hX⟩
else if hX' : (m : ℕ) < 2 * n then z.2 ⟨m - n, by omega⟩
else if hRe : (m : ℕ) < 2 * n + p then
(projectedComplex U z.1.1 z.2 ⟨m - 2 * n, by omega⟩).re
else if hIm : (m : ℕ) < 2 * n + 2 * p then
(projectedComplex U z.1.1 z.2 ⟨m - (2 * n + p), by omega⟩).im
else yMax w z.1.1 z.1.2
/-- The law of one projected sample for the odd features, `(X, X′, U X̃^{⊗r}, Y_max)`.
**Formalization Note.** The odd coordinate feature (108), p.57 (PDF p.60),
`Ψ^U_{odd,ℓ}(X, X′) = Re[(U X̃^{⊗r})(U X̃^{⊗r})ᵀ X̃_ℓ]/√((2r+1)!)`, contains `X̃_ℓ = X_ℓ + iX′_ℓ`, and
Algorithm 8.1 takes features "evaluated from the supplied samples"; so for the odd call the supplied
sample carries `X′` as well. -/
noncomputable def projectedSampleLawOdd {n k p r : ℕ}
(w : Fin k → EuclideanSpace ℝ (Fin n)) (U : Matrix (Fin p) (Fin r → Fin n) ℝ) :
Measure (EuclideanSpace ℝ (Fin (2 * n + 2 * p + 1))) :=
((jointLaw n k).prod (stdGaussian (EuclideanSpace ℝ (Fin n)))).map (projectedSampleOfOdd w U)
end Supplement
end SelfSelReg
Source
Zhou, Linear Regression with Self-Selection Bias in Polynomial Time, STOC 2027 submission (manuscript sha256 5d65f750…), Theorem 8.1, p.55 (PDF p.58); Section 8.1.2, (107), (108), pp.56–57 (PDF pp.59–60)