diff -r 9738b51d90d7 -r 4f468d35fa29 src/kernels/gaussian.rs --- a/src/kernels/gaussian.rs Sun Apr 27 15:03:51 2025 -0500 +++ b/src/kernels/gaussian.rs Thu Feb 26 11:38:43 2026 -0500 @@ -1,58 +1,51 @@ //! Implementation of the gaussian kernel. +use alg_tools::bisection_tree::{Constant, Support, Weighted}; +use alg_tools::bounds::{Bounded, Bounds, GlobalAnalysis, LocalAnalysis}; +use alg_tools::euclidean::Euclidean; +use alg_tools::loc::Loc; +use alg_tools::mapping::{ + DifferentiableImpl, Differential, Instance, LipschitzDifferentiableImpl, Mapping, +}; +use alg_tools::maputil::array_init; +use alg_tools::norms::*; +use alg_tools::sets::Cube; +use alg_tools::types::*; use float_extras::f64::erf; use numeric_literals::replace_float_literals; use serde::Serialize; -use alg_tools::types::*; -use alg_tools::euclidean::Euclidean; -use alg_tools::norms::*; -use alg_tools::loc::Loc; -use alg_tools::sets::Cube; -use alg_tools::bisection_tree::{ - Support, - Constant, - Bounds, - LocalAnalysis, - GlobalAnalysis, - Weighted, - Bounded, -}; -use alg_tools::mapping::{ - Mapping, - Instance, - Differential, - DifferentiableImpl, -}; -use alg_tools::maputil::array_init; -use crate::types::*; +use super::ball_indicator::CubeIndicator; +use super::base::*; use crate::fourier::Fourier; -use super::base::*; -use super::ball_indicator::CubeIndicator; +use crate::types::*; /// Storage presentation of the the anisotropic gaussian kernel of `variance` $σ^2$. /// /// This is the function $f(x) = C e^{-\\|x\\|\_2^2/(2σ^2)}$ for $x ∈ ℝ^N$ /// with $C=1/(2πσ^2)^{N/2}$. -#[derive(Copy,Clone,Debug,Serialize,Eq)] -pub struct Gaussian { +#[derive(Copy, Clone, Debug, Serialize, Eq)] +pub struct Gaussian { /// The variance $σ^2$. - pub variance : S, + pub variance: S, } -impl PartialEq> for Gaussian -where S1 : Constant, - S2 : Constant { - fn eq(&self, other : &Gaussian) -> bool { +impl PartialEq> for Gaussian +where + S1: Constant, + S2: Constant, +{ + fn eq(&self, other: &Gaussian) -> bool { self.variance.value() == other.variance.value() } } -impl PartialOrd> for Gaussian -where S1 : Constant, - S2 : Constant { - - fn partial_cmp(&self, other : &Gaussian) -> Option { +impl PartialOrd> for Gaussian +where + S1: Constant, + S2: Constant, +{ + fn partial_cmp(&self, other: &Gaussian) -> Option { // A gaussian is ≤ another gaussian if the Fourier transforms satisfy the // corresponding inequality. That in turns holds if and only if the variances // satisfy the opposite inequality. @@ -62,18 +55,17 @@ } } - #[replace_float_literals(S::Type::cast_from(literal))] -impl<'a, S, const N : usize> Mapping> for Gaussian +impl<'a, S, const N: usize> Mapping> for Gaussian where - S : Constant + S: Constant, { type Codomain = S::Type; // This is not normalised to neither to have value 1 at zero or integral 1 // (unless the cut-off ε=0). #[inline] - fn apply>>(&self, x : I) -> Self::Codomain { + fn apply>>(&self, x: I) -> Self::Codomain { let d_squared = x.eval(|x| x.norm2_squared()); let σ2 = self.variance.value(); let scale = self.scale(); @@ -82,19 +74,20 @@ } #[replace_float_literals(S::Type::cast_from(literal))] -impl<'a, S, const N : usize> DifferentiableImpl> for Gaussian -where S : Constant { - type Derivative = Loc; +impl<'a, S, const N: usize> DifferentiableImpl> for Gaussian +where + S: Constant, +{ + type Derivative = Loc; #[inline] - fn differential_impl>>(&self, x0 : I) -> Self::Derivative { - let x = x0.cow(); + fn differential_impl>>(&self, x0: I) -> Self::Derivative { + let x = x0.decompose(); let f = -self.apply(&*x) / self.variance.value(); *x * f } } - // To calculate the the Lipschitz factors, we consider // f(t) = e^{-t²/2} // f'(t) = -t f(t) which has max at t=1 by f''(t)=0 @@ -117,25 +110,26 @@ // Hence the Lipschitz factor of ∇g is (C/σ²)f''(√3) = (C/σ²)2e^{-3/2}. #[replace_float_literals(S::Type::cast_from(literal))] -impl Lipschitz for Gaussian -where S : Constant { +impl Lipschitz for Gaussian +where + S: Constant, +{ type FloatType = S::Type; - fn lipschitz_factor(&self, L2 : L2) -> Option { - Some((-0.5).exp() / (self.scale() * self.variance.value().sqrt())) + fn lipschitz_factor(&self, L2: L2) -> DynResult { + Ok((-0.5).exp() / (self.scale() * self.variance.value().sqrt())) } } - #[replace_float_literals(S::Type::cast_from(literal))] -impl<'a, S : Constant, const N : usize> Lipschitz -for Differential<'a, Loc, Gaussian> { +impl<'a, S: Constant, const N: usize> LipschitzDifferentiableImpl, L2> + for Gaussian +{ type FloatType = S::Type; - - fn lipschitz_factor(&self, _l2 : L2) -> Option { - let g = self.base_fn(); - let σ2 = g.variance.value(); - let scale = g.scale(); - Some(2.0*(-3.0/2.0).exp()/(σ2*scale)) + + fn diff_lipschitz_factor(&self, _l2: L2) -> DynResult { + let σ2 = self.variance.value(); + let scale = self.scale(); + Ok(2.0 * (-3.0 / 2.0).exp() / (σ2 * scale)) } } @@ -146,65 +140,73 @@ // factors of the undifferentiated function, given how the latter is calculed above. #[replace_float_literals(S::Type::cast_from(literal))] -impl<'b, S : Constant, const N : usize> NormBounded -for Differential<'b, Loc, Gaussian> { +impl<'b, S: Constant, const N: usize> NormBounded + for Differential<'b, Loc, Gaussian> +{ type FloatType = S::Type; - - fn norm_bound(&self, _l2 : L2) -> S::Type { + + fn norm_bound(&self, _l2: L2) -> S::Type { self.base_fn().lipschitz_factor(L2).unwrap() } } #[replace_float_literals(S::Type::cast_from(literal))] -impl<'b, 'a, S : Constant, const N : usize> NormBounded -for Differential<'b, Loc, &'a Gaussian> { +impl<'b, 'a, S: Constant, const N: usize> NormBounded + for Differential<'b, Loc, &'a Gaussian> +{ type FloatType = S::Type; - - fn norm_bound(&self, _l2 : L2) -> S::Type { + + fn norm_bound(&self, _l2: L2) -> S::Type { self.base_fn().lipschitz_factor(L2).unwrap() } } - #[replace_float_literals(S::Type::cast_from(literal))] -impl<'a, S, const N : usize> Gaussian -where S : Constant { - +impl<'a, S, const N: usize> Gaussian +where + S: Constant, +{ /// Returns the (reciprocal) scaling constant $1/C=(2πσ^2)^{N/2}$. #[inline] pub fn scale(&self) -> S::Type { let π = S::Type::PI; let σ2 = self.variance.value(); - (2.0*π*σ2).powi(N as i32).sqrt() + (2.0 * π * σ2).powi(N as i32).sqrt() } } -impl<'a, S, const N : usize> Support for Gaussian -where S : Constant { +impl<'a, S, const N: usize> Support for Gaussian +where + S: Constant, +{ #[inline] - fn support_hint(&self) -> Cube { + fn support_hint(&self) -> Cube { array_init(|| [S::Type::NEG_INFINITY, S::Type::INFINITY]).into() } #[inline] - fn in_support(&self, _x : &Loc) -> bool { + fn in_support(&self, _x: &Loc) -> bool { true } } #[replace_float_literals(S::Type::cast_from(literal))] -impl GlobalAnalysis> for Gaussian -where S : Constant { +impl GlobalAnalysis> for Gaussian +where + S: Constant, +{ #[inline] fn global_analysis(&self) -> Bounds { - Bounds(0.0, 1.0/self.scale()) + Bounds(0.0, 1.0 / self.scale()) } } -impl LocalAnalysis, N> for Gaussian -where S : Constant { +impl LocalAnalysis, N> for Gaussian +where + S: Constant, +{ #[inline] - fn local_analysis(&self, cube : &Cube) -> Bounds { + fn local_analysis(&self, cube: &Cube) -> Bounds { // The function is maximised/minimised where the 2-norm is minimised/maximised. let lower = self.apply(cube.maxnorm_point()); let upper = self.apply(cube.minnorm_point()); @@ -213,68 +215,63 @@ } #[replace_float_literals(C::Type::cast_from(literal))] -impl<'a, C : Constant, const N : usize> Norm -for Gaussian { +impl<'a, C: Constant, const N: usize> Norm for Gaussian { #[inline] - fn norm(&self, _ : L1) -> C::Type { + fn norm(&self, _: L1) -> C::Type { 1.0 } } #[replace_float_literals(C::Type::cast_from(literal))] -impl<'a, C : Constant, const N : usize> Norm -for Gaussian { +impl<'a, C: Constant, const N: usize> Norm for Gaussian { #[inline] - fn norm(&self, _ : Linfinity) -> C::Type { + fn norm(&self, _: Linfinity) -> C::Type { self.bounds().upper() } } #[replace_float_literals(C::Type::cast_from(literal))] -impl<'a, C : Constant, const N : usize> Fourier -for Gaussian { - type Domain = Loc; +impl<'a, C: Constant, const N: usize> Fourier for Gaussian { + type Domain = Loc; type Transformed = Weighted, C::Type>; #[inline] fn fourier(&self) -> Self::Transformed { let π = C::Type::PI; let σ2 = self.variance.value(); - let g = Gaussian { variance : 1.0 / (4.0*π*π*σ2) }; + let g = Gaussian { variance: 1.0 / (4.0 * π * π * σ2) }; g.weigh(g.scale()) } } /// Representation of the “cut” gaussian $f χ\_{[-a, a]^n}$ /// where $a>0$ and $f$ is a gaussian kernel on $ℝ^n$. -pub type BasicCutGaussian = SupportProductFirst, - Gaussian>; - +pub type BasicCutGaussian = + SupportProductFirst, Gaussian>; /// This implements $g := χ\_{[-b, b]^n} \* (f χ\_{[-a, a]^n})$ where $a,b>0$ and $f$ is /// a gaussian kernel on $ℝ^n$. For an expression for $g$, see Lemma 3.9 in the manuscript. #[replace_float_literals(F::cast_from(literal))] -impl<'a, F : Float, R, C, S, const N : usize> Mapping> -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { - +impl<'a, F: Float, R, C, S, const N: usize> Mapping> + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ type Codomain = F; #[inline] - fn apply>>(&self, y : I) -> F { - let Convolution(ref ind, - SupportProductFirst(ref cut, - ref gaussian)) = self; + fn apply>>(&self, y: I) -> F { + let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self; let a = cut.r.value(); let b = ind.r.value(); let σ = gaussian.variance.value().sqrt(); let t = F::SQRT_2 * σ; let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2 - + // This is just a product of one-dimensional versions - y.cow().product_map(|x| { + y.decompose().product_map(|x| { let c1 = -(a.min(b + x)); //(-a).max(-x-b); let c2 = a.min(b - x); if c1 >= c2 { @@ -293,28 +290,27 @@ /// and $f$ is a gaussian kernel on $ℝ^n$. For an expression for the value of $g$, from which the /// derivative readily arises (at points of differentiability), see Lemma 3.9 in the manuscript. #[replace_float_literals(F::cast_from(literal))] -impl<'a, F : Float, R, C, S, const N : usize> DifferentiableImpl> -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { - - type Derivative = Loc; +impl<'a, F: Float, R, C, S, const N: usize> DifferentiableImpl> + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ + type Derivative = Loc; /// Although implemented, this function is not differentiable. #[inline] - fn differential_impl>>(&self, y0 : I) -> Loc { - let Convolution(ref ind, - SupportProductFirst(ref cut, - ref gaussian)) = self; - let y = y0.cow(); + fn differential_impl>>(&self, y0: I) -> Loc { + let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self; + let y = y0.decompose(); let a = cut.r.value(); let b = ind.r.value(); let σ = gaussian.variance.value().sqrt(); let t = F::SQRT_2 * σ; let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2 let c_mul_erf_scale_div_t = c * F::FRAC_2_SQRT_PI / t; - + // Calculate the values for all component functions of the // product. This is just the loop from apply above. let unscaled_vs = y.map(|x| { @@ -340,12 +336,12 @@ // from the chain rule (the minus comes from inside c_1 or c_2, and changes the // order of de2 and de1 in the final calculation). let de1 = if b + x < a { - (-((b+x)/t).powi(2)).exp() + (-((b + x) / t).powi(2)).exp() } else { 0.0 }; let de2 = if b - x < a { - (-((b-x)/t).powi(2)).exp() + (-((b - x) / t).powi(2)).exp() } else { 0.0 }; @@ -355,16 +351,17 @@ } } - #[replace_float_literals(F::cast_from(literal))] -impl<'a, F : Float, R, C, S, const N : usize> Lipschitz -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { +impl<'a, F: Float, R, C, S, const N: usize> Lipschitz + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ type FloatType = F; - fn lipschitz_factor(&self, L1 : L1) -> Option { + fn lipschitz_factor(&self, L1: L1) -> DynResult { // To get the product Lipschitz factor, we note that for any ψ_i, we have // ∏_{i=1}^N φ_i(x_i) - ∏_{i=1}^N φ_i(y_i) // = [φ_1(x_1)-φ_1(y_1)] ∏_{i=2}^N φ_i(x_i) @@ -398,9 +395,7 @@ // θ * ψ(x) = θ * ψ(y). If only y is in the range [-(a+b), a+b], we can replace // x by -(a+b) or (a+b), either of which is closer to y and still θ * ψ(x)=0. // Thus same calculations as above work for the Lipschitz factor. - let Convolution(ref ind, - SupportProductFirst(ref cut, - ref gaussian)) = self; + let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self; let a = cut.r.value(); let b = ind.r.value(); let σ = gaussian.variance.value().sqrt(); @@ -408,7 +403,7 @@ let t = F::SQRT_2 * σ; let l1d = F::SQRT_2 / (π.sqrt() * σ); let e0 = F::cast_from(erf((a.min(b) / t).as_())); - Some(l1d * e0.powi(N as i32-1)) + Ok(l1d * e0.powi(N as i32 - 1)) } } @@ -426,39 +421,40 @@ } */ -impl -Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { - +impl Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ #[inline] fn get_r(&self) -> F { - let Convolution(ref ind, - SupportProductFirst(ref cut, ..)) = self; + let Convolution(ref ind, SupportProductFirst(ref cut, ..)) = self; ind.r.value() + cut.r.value() } } -impl Support -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { +impl Support + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ #[inline] - fn support_hint(&self) -> Cube { + fn support_hint(&self) -> Cube { let r = self.get_r(); array_init(|| [-r, r]).into() } #[inline] - fn in_support(&self, y : &Loc) -> bool { + fn in_support(&self, y: &Loc) -> bool { let r = self.get_r(); y.iter().all(|x| x.abs() <= r) } #[inline] - fn bisection_hint(&self, cube : &Cube) -> [Option; N] { + fn bisection_hint(&self, cube: &Cube) -> [Option; N] { let r = self.get_r(); // From c1 = -a.min(b + x) and c2 = a.min(b - x) with c_1 < c_2, // solve bounds for x. that is 0 ≤ a.min(b + x) + a.min(b - x). @@ -470,28 +466,31 @@ } } -impl GlobalAnalysis> -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { +impl GlobalAnalysis> + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ #[inline] fn global_analysis(&self) -> Bounds { Bounds(F::ZERO, self.apply(Loc::ORIGIN)) } } -impl LocalAnalysis, N> -for Convolution, BasicCutGaussian> -where R : Constant, - C : Constant, - S : Constant { +impl LocalAnalysis, N> + for Convolution, BasicCutGaussian> +where + R: Constant, + C: Constant, + S: Constant, +{ #[inline] - fn local_analysis(&self, cube : &Cube) -> Bounds { + fn local_analysis(&self, cube: &Cube) -> Bounds { // The function is maximised/minimised where the absolute value is minimised/maximised. let lower = self.apply(cube.maxnorm_point()); let upper = self.apply(cube.minnorm_point()); Bounds(lower, upper) } } -