Real Gaussian Gram matrices and the quadratic oracle
DefinitionSketchAttr_LOO_Supplement_QuadraticFor a real matrix , let , with independent standard entries under the matrix law. For a real square matrix , its Frobenius norm is the published order-two tensor norm after embedding its entries into . Define
The real matrix-vector oracle returns . The quadratic oracle accepts every and every integer and returns together with for . A sequence stores these vector responses, with zero padding beyond the requested degree. The free value and gradient at zero are the fixed pair , so they carry no hidden input information. Query and terminal maps receive no matrix or circuit encoding. The two oracle specializations instantiate the unrestricted adaptive interface, and squared diagonal error means .
This fixes the real Gaussian normalization and preserves the transpose convention; no complex conjugation occurs in the quadratic polynomial.
import Mathlib
import Definitions.Def_SketchAttr_LOO_Taylor
import Definitions.Def_SketchAttr_LOO_Stability
import Definitions.Def_SketchAttr_LOO_Supplement_Adaptive
open MeasureTheory ProbabilityTheory
open scoped ENNReal
namespace SketchAttr.LOO.Supplement
instance realMatrixMeasurableSpace (r n : ℕ) :
MeasurableSpace (Matrix (Fin r) (Fin n) ℝ) :=
inferInstanceAs (MeasurableSpace (Fin r → Fin n → ℝ))
abbrev RealMatrix (n : ℕ) := Matrix (Fin n) (Fin n) ℝ
abbrev RealVector (n : ℕ) := Fin n → ℝ
noncomputable def matrixTensor {n : ℕ} (A : RealMatrix n) : Tensor n 2 :=
fun j => (A (j 0) (j 1) : ℂ)
/-- The published order-two tensor norm, with the real matrix embedded in C. -/
noncomputable def matrixFrobNorm {n : ℕ} (A : RealMatrix n) : ℝ :=
frobNorm (matrixTensor A)
noncomputable def realGaussianMatrix (r n : ℕ) :
Measure (Matrix (Fin r) (Fin n) ℝ) :=
Measure.pi fun _ : Fin r => Measure.pi fun _ : Fin n => gaussianReal 0 1
noncomputable def gram {r n : ℕ} (G : Matrix (Fin r) (Fin n) ℝ) : RealMatrix n :=
fun i j => ∑ a, G a i * G a j
/-- No conjugation: the source uses transpose, not conjugate transpose. -/
noncomputable def quadratic {n : ℕ} (A : RealMatrix n) (w : Vec n) : ℂ :=
∑ i, ∑ j, (A i j : ℂ) * w i * w j
noncomputable def quadraticProfile : StabilityProfile :=
fun B => ENNReal.ofReal (B.val ^ 2 / 16)
abbrev MatrixProcedure (Seed : Type*) [MeasurableSpace Seed] (n q : ℕ) :=
AdaptiveProcedure Seed (RealVector n) (RealVector n) (RealVector n) q
noncomputable def matrixEstimate {Seed : Type*} [MeasurableSpace Seed] {n q : ℕ}
(P : MatrixProcedure Seed n q) (A : RealMatrix n) (seed : Seed) : RealVector n :=
adaptiveOutput P (fun x => A.mulVec x) seed
noncomputable def squaredDiagonalError {n : ℕ} (v : RealVector n) (A : RealMatrix n) : ℝ :=
∑ i, |v i - A i i| ^ 2
/-- All positive query degrees are permitted, with no fixed cap. -/
abbrev QuadraticQuery (n : ℕ) := Vec n × Vec n × {N : ℕ // 1 ≤ N}
/-- The sequence represents degrees 0 through the chosen N; all later
coordinates are set to zero and reveal no additional information. -/
abbrev QuadraticAnswer (n : ℕ) := ℂ × (ℕ → Vec n)
/-- Exactly the oracle of Section 5.3, evaluated on the quadratic polynomial.
Degree zero of the vector sequence is the gradient itself. -/
noncomputable def quadraticOracle {n : ℕ} (A : RealMatrix n)
(Q : QuadraticQuery n) : QuadraticAnswer n :=
(quadratic A Q.1, fun r => if r ≤ Q.2.2.val then
iteratedFDeriv ℂ r (gradient (quadratic A)) Q.1 (fun _ => Q.2.1) else 0)
abbrev QuadraticProcedure (Seed : Type*) [MeasurableSpace Seed] (n q : ℕ) :=
AdaptiveProcedure Seed (QuadraticQuery n) (QuadraticAnswer n) (Vec n) q
/-- The free value and gradient at zero are identically (0,0) on this family.
They are public constants, so omitting a redundant argument gives every
procedure exactly the same access. No circuit encoding is passed to P. -/
noncomputable def quadraticEstimate {Seed : Type*} [MeasurableSpace Seed] {n q : ℕ}
(P : QuadraticProcedure Seed n q) (A : RealMatrix n) (seed : Seed) : Vec n :=
adaptiveOutput P (quadraticOracle A) seed
end SketchAttr.LOO.Supplement