src/kernels/gaussian.rs

branch
dev
changeset 61
4f468d35fa29
parent 35
b087e3eab191
equal deleted inserted replaced
60:9738b51d90d7 61:4f468d35fa29
1 //! Implementation of the gaussian kernel. 1 //! Implementation of the gaussian kernel.
2 2
3 use alg_tools::bisection_tree::{Constant, Support, Weighted};
4 use alg_tools::bounds::{Bounded, Bounds, GlobalAnalysis, LocalAnalysis};
5 use alg_tools::euclidean::Euclidean;
6 use alg_tools::loc::Loc;
7 use alg_tools::mapping::{
8 DifferentiableImpl, Differential, Instance, LipschitzDifferentiableImpl, Mapping,
9 };
10 use alg_tools::maputil::array_init;
11 use alg_tools::norms::*;
12 use alg_tools::sets::Cube;
13 use alg_tools::types::*;
3 use float_extras::f64::erf; 14 use float_extras::f64::erf;
4 use numeric_literals::replace_float_literals; 15 use numeric_literals::replace_float_literals;
5 use serde::Serialize; 16 use serde::Serialize;
6 use alg_tools::types::*; 17
7 use alg_tools::euclidean::Euclidean; 18 use super::ball_indicator::CubeIndicator;
8 use alg_tools::norms::*; 19 use super::base::*;
9 use alg_tools::loc::Loc; 20 use crate::fourier::Fourier;
10 use alg_tools::sets::Cube;
11 use alg_tools::bisection_tree::{
12 Support,
13 Constant,
14 Bounds,
15 LocalAnalysis,
16 GlobalAnalysis,
17 Weighted,
18 Bounded,
19 };
20 use alg_tools::mapping::{
21 Mapping,
22 Instance,
23 Differential,
24 DifferentiableImpl,
25 };
26 use alg_tools::maputil::array_init;
27
28 use crate::types::*; 21 use crate::types::*;
29 use crate::fourier::Fourier;
30 use super::base::*;
31 use super::ball_indicator::CubeIndicator;
32 22
33 /// Storage presentation of the the anisotropic gaussian kernel of `variance` $σ^2$. 23 /// Storage presentation of the the anisotropic gaussian kernel of `variance` $σ^2$.
34 /// 24 ///
35 /// This is the function $f(x) = C e^{-\\|x\\|\_2^2/(2σ^2)}$ for $x ∈ ℝ^N$ 25 /// This is the function $f(x) = C e^{-\\|x\\|\_2^2/(2σ^2)}$ for $x ∈ ℝ^N$
36 /// with $C=1/(2πσ^2)^{N/2}$. 26 /// with $C=1/(2πσ^2)^{N/2}$.
37 #[derive(Copy,Clone,Debug,Serialize,Eq)] 27 #[derive(Copy, Clone, Debug, Serialize, Eq)]
38 pub struct Gaussian<S : Constant, const N : usize> { 28 pub struct Gaussian<S: Constant, const N: usize> {
39 /// The variance $σ^2$. 29 /// The variance $σ^2$.
40 pub variance : S, 30 pub variance: S,
41 } 31 }
42 32
43 impl<S1, S2, const N : usize> PartialEq<Gaussian<S2, N>> for Gaussian<S1, N> 33 impl<S1, S2, const N: usize> PartialEq<Gaussian<S2, N>> for Gaussian<S1, N>
44 where S1 : Constant, 34 where
45 S2 : Constant<Type=S1::Type> { 35 S1: Constant,
46 fn eq(&self, other : &Gaussian<S2, N>) -> bool { 36 S2: Constant<Type = S1::Type>,
37 {
38 fn eq(&self, other: &Gaussian<S2, N>) -> bool {
47 self.variance.value() == other.variance.value() 39 self.variance.value() == other.variance.value()
48 } 40 }
49 } 41 }
50 42
51 impl<S1, S2, const N : usize> PartialOrd<Gaussian<S2, N>> for Gaussian<S1, N> 43 impl<S1, S2, const N: usize> PartialOrd<Gaussian<S2, N>> for Gaussian<S1, N>
52 where S1 : Constant, 44 where
53 S2 : Constant<Type=S1::Type> { 45 S1: Constant,
54 46 S2: Constant<Type = S1::Type>,
55 fn partial_cmp(&self, other : &Gaussian<S2, N>) -> Option<std::cmp::Ordering> { 47 {
48 fn partial_cmp(&self, other: &Gaussian<S2, N>) -> Option<std::cmp::Ordering> {
56 // A gaussian is ≤ another gaussian if the Fourier transforms satisfy the 49 // A gaussian is ≤ another gaussian if the Fourier transforms satisfy the
57 // corresponding inequality. That in turns holds if and only if the variances 50 // corresponding inequality. That in turns holds if and only if the variances
58 // satisfy the opposite inequality. 51 // satisfy the opposite inequality.
59 let σ1sq = self.variance.value(); 52 let σ1sq = self.variance.value();
60 let σ2sq = other.variance.value(); 53 let σ2sq = other.variance.value();
61 σ2sq.partial_cmp(&σ1sq) 54 σ2sq.partial_cmp(&σ1sq)
62 } 55 }
63 } 56 }
64 57
65 58 #[replace_float_literals(S::Type::cast_from(literal))]
66 #[replace_float_literals(S::Type::cast_from(literal))] 59 impl<'a, S, const N: usize> Mapping<Loc<N, S::Type>> for Gaussian<S, N>
67 impl<'a, S, const N : usize> Mapping<Loc<S::Type, N>> for Gaussian<S, N> 60 where
68 where 61 S: Constant,
69 S : Constant
70 { 62 {
71 type Codomain = S::Type; 63 type Codomain = S::Type;
72 64
73 // This is not normalised to neither to have value 1 at zero or integral 1 65 // This is not normalised to neither to have value 1 at zero or integral 1
74 // (unless the cut-off ε=0). 66 // (unless the cut-off ε=0).
75 #[inline] 67 #[inline]
76 fn apply<I : Instance<Loc<S::Type, N>>>(&self, x : I) -> Self::Codomain { 68 fn apply<I: Instance<Loc<N, S::Type>>>(&self, x: I) -> Self::Codomain {
77 let d_squared = x.eval(|x| x.norm2_squared()); 69 let d_squared = x.eval(|x| x.norm2_squared());
78 let σ2 = self.variance.value(); 70 let σ2 = self.variance.value();
79 let scale = self.scale(); 71 let scale = self.scale();
80 (-d_squared / (2.0 * σ2)).exp() / scale 72 (-d_squared / (2.0 * σ2)).exp() / scale
81 } 73 }
82 } 74 }
83 75
84 #[replace_float_literals(S::Type::cast_from(literal))] 76 #[replace_float_literals(S::Type::cast_from(literal))]
85 impl<'a, S, const N : usize> DifferentiableImpl<Loc<S::Type, N>> for Gaussian<S, N> 77 impl<'a, S, const N: usize> DifferentiableImpl<Loc<N, S::Type>> for Gaussian<S, N>
86 where S : Constant { 78 where
87 type Derivative = Loc<S::Type, N>; 79 S: Constant,
88 80 {
89 #[inline] 81 type Derivative = Loc<N, S::Type>;
90 fn differential_impl<I : Instance<Loc<S::Type, N>>>(&self, x0 : I) -> Self::Derivative { 82
91 let x = x0.cow(); 83 #[inline]
84 fn differential_impl<I: Instance<Loc<N, S::Type>>>(&self, x0: I) -> Self::Derivative {
85 let x = x0.decompose();
92 let f = -self.apply(&*x) / self.variance.value(); 86 let f = -self.apply(&*x) / self.variance.value();
93 *x * f 87 *x * f
94 } 88 }
95 } 89 }
96
97 90
98 // To calculate the the Lipschitz factors, we consider 91 // To calculate the the Lipschitz factors, we consider
99 // f(t) = e^{-t²/2} 92 // f(t) = e^{-t²/2}
100 // f'(t) = -t f(t) which has max at t=1 by f''(t)=0 93 // f'(t) = -t f(t) which has max at t=1 by f''(t)=0
101 // f''(t) = (t²-1)f(t) which has max at t=√3 by f'''(t)=0 94 // f''(t) = (t²-1)f(t) which has max at t=√3 by f'''(t)=0
115 // ‖-Id + x ⊗ x/σ²‖ = ‖[-Id + x ⊗ x/σ²](x/‖x‖)‖ = |-1 + ‖x²/σ^2‖|. 108 // ‖-Id + x ⊗ x/σ²‖ = ‖[-Id + x ⊗ x/σ²](x/‖x‖)‖ = |-1 + ‖x²/σ^2‖|.
116 // This means that ‖∇²g(x)‖ = (C/σ²)|f''(‖x‖/σ)|, which is maximised with ‖x‖/σ=√3. 109 // This means that ‖∇²g(x)‖ = (C/σ²)|f''(‖x‖/σ)|, which is maximised with ‖x‖/σ=√3.
117 // Hence the Lipschitz factor of ∇g is (C/σ²)f''(√3) = (C/σ²)2e^{-3/2}. 110 // Hence the Lipschitz factor of ∇g is (C/σ²)f''(√3) = (C/σ²)2e^{-3/2}.
118 111
119 #[replace_float_literals(S::Type::cast_from(literal))] 112 #[replace_float_literals(S::Type::cast_from(literal))]
120 impl<S, const N : usize> Lipschitz<L2> for Gaussian<S, N> 113 impl<S, const N: usize> Lipschitz<L2> for Gaussian<S, N>
121 where S : Constant { 114 where
115 S: Constant,
116 {
122 type FloatType = S::Type; 117 type FloatType = S::Type;
123 fn lipschitz_factor(&self, L2 : L2) -> Option<Self::FloatType> { 118 fn lipschitz_factor(&self, L2: L2) -> DynResult<Self::FloatType> {
124 Some((-0.5).exp() / (self.scale() * self.variance.value().sqrt())) 119 Ok((-0.5).exp() / (self.scale() * self.variance.value().sqrt()))
125 } 120 }
126 } 121 }
127 122
128 123 #[replace_float_literals(S::Type::cast_from(literal))]
129 #[replace_float_literals(S::Type::cast_from(literal))] 124 impl<'a, S: Constant, const N: usize> LipschitzDifferentiableImpl<Loc<N, S::Type>, L2>
130 impl<'a, S : Constant, const N : usize> Lipschitz<L2> 125 for Gaussian<S, N>
131 for Differential<'a, Loc<S::Type, N>, Gaussian<S, N>> { 126 {
132 type FloatType = S::Type; 127 type FloatType = S::Type;
133 128
134 fn lipschitz_factor(&self, _l2 : L2) -> Option<S::Type> { 129 fn diff_lipschitz_factor(&self, _l2: L2) -> DynResult<S::Type> {
135 let g = self.base_fn(); 130 let σ2 = self.variance.value();
136 let σ2 = g.variance.value(); 131 let scale = self.scale();
137 let scale = g.scale(); 132 Ok(2.0 * (-3.0 / 2.0).exp() / (σ2 * scale))
138 Some(2.0*(-3.0/2.0).exp()/(σ2*scale))
139 } 133 }
140 } 134 }
141 135
142 // From above, norm bounds on the differnential can be calculated as achieved 136 // From above, norm bounds on the differnential can be calculated as achieved
143 // for f' at t=1, i.e., the bound is |f'(1)|. 137 // for f' at t=1, i.e., the bound is |f'(1)|.
144 // For g then |C/σ f'(1)|. 138 // For g then |C/σ f'(1)|.
145 // It follows that the norm bounds on the differential are just the Lipschitz 139 // It follows that the norm bounds on the differential are just the Lipschitz
146 // factors of the undifferentiated function, given how the latter is calculed above. 140 // factors of the undifferentiated function, given how the latter is calculed above.
147 141
148 #[replace_float_literals(S::Type::cast_from(literal))] 142 #[replace_float_literals(S::Type::cast_from(literal))]
149 impl<'b, S : Constant, const N : usize> NormBounded<L2> 143 impl<'b, S: Constant, const N: usize> NormBounded<L2>
150 for Differential<'b, Loc<S::Type, N>, Gaussian<S, N>> { 144 for Differential<'b, Loc<N, S::Type>, Gaussian<S, N>>
145 {
151 type FloatType = S::Type; 146 type FloatType = S::Type;
152 147
153 fn norm_bound(&self, _l2 : L2) -> S::Type { 148 fn norm_bound(&self, _l2: L2) -> S::Type {
154 self.base_fn().lipschitz_factor(L2).unwrap() 149 self.base_fn().lipschitz_factor(L2).unwrap()
155 } 150 }
156 } 151 }
157 152
158 #[replace_float_literals(S::Type::cast_from(literal))] 153 #[replace_float_literals(S::Type::cast_from(literal))]
159 impl<'b, 'a, S : Constant, const N : usize> NormBounded<L2> 154 impl<'b, 'a, S: Constant, const N: usize> NormBounded<L2>
160 for Differential<'b, Loc<S::Type, N>, &'a Gaussian<S, N>> { 155 for Differential<'b, Loc<N, S::Type>, &'a Gaussian<S, N>>
156 {
161 type FloatType = S::Type; 157 type FloatType = S::Type;
162 158
163 fn norm_bound(&self, _l2 : L2) -> S::Type { 159 fn norm_bound(&self, _l2: L2) -> S::Type {
164 self.base_fn().lipschitz_factor(L2).unwrap() 160 self.base_fn().lipschitz_factor(L2).unwrap()
165 } 161 }
166 } 162 }
167 163
168 164 #[replace_float_literals(S::Type::cast_from(literal))]
169 #[replace_float_literals(S::Type::cast_from(literal))] 165 impl<'a, S, const N: usize> Gaussian<S, N>
170 impl<'a, S, const N : usize> Gaussian<S, N> 166 where
171 where S : Constant { 167 S: Constant,
172 168 {
173 /// Returns the (reciprocal) scaling constant $1/C=(2πσ^2)^{N/2}$. 169 /// Returns the (reciprocal) scaling constant $1/C=(2πσ^2)^{N/2}$.
174 #[inline] 170 #[inline]
175 pub fn scale(&self) -> S::Type { 171 pub fn scale(&self) -> S::Type {
176 let π = S::Type::PI; 172 let π = S::Type::PI;
177 let σ2 = self.variance.value(); 173 let σ2 = self.variance.value();
178 (2.0*π*σ2).powi(N as i32).sqrt() 174 (2.0 * π * σ2).powi(N as i32).sqrt()
179 } 175 }
180 } 176 }
181 177
182 impl<'a, S, const N : usize> Support<S::Type, N> for Gaussian<S, N> 178 impl<'a, S, const N: usize> Support<N, S::Type> for Gaussian<S, N>
183 where S : Constant { 179 where
184 #[inline] 180 S: Constant,
185 fn support_hint(&self) -> Cube<S::Type,N> { 181 {
182 #[inline]
183 fn support_hint(&self) -> Cube<N, S::Type> {
186 array_init(|| [S::Type::NEG_INFINITY, S::Type::INFINITY]).into() 184 array_init(|| [S::Type::NEG_INFINITY, S::Type::INFINITY]).into()
187 } 185 }
188 186
189 #[inline] 187 #[inline]
190 fn in_support(&self, _x : &Loc<S::Type,N>) -> bool { 188 fn in_support(&self, _x: &Loc<N, S::Type>) -> bool {
191 true 189 true
192 } 190 }
193 } 191 }
194 192
195 #[replace_float_literals(S::Type::cast_from(literal))] 193 #[replace_float_literals(S::Type::cast_from(literal))]
196 impl<S, const N : usize> GlobalAnalysis<S::Type, Bounds<S::Type>> for Gaussian<S, N> 194 impl<S, const N: usize> GlobalAnalysis<S::Type, Bounds<S::Type>> for Gaussian<S, N>
197 where S : Constant { 195 where
196 S: Constant,
197 {
198 #[inline] 198 #[inline]
199 fn global_analysis(&self) -> Bounds<S::Type> { 199 fn global_analysis(&self) -> Bounds<S::Type> {
200 Bounds(0.0, 1.0/self.scale()) 200 Bounds(0.0, 1.0 / self.scale())
201 } 201 }
202 } 202 }
203 203
204 impl<S, const N : usize> LocalAnalysis<S::Type, Bounds<S::Type>, N> for Gaussian<S, N> 204 impl<S, const N: usize> LocalAnalysis<S::Type, Bounds<S::Type>, N> for Gaussian<S, N>
205 where S : Constant { 205 where
206 #[inline] 206 S: Constant,
207 fn local_analysis(&self, cube : &Cube<S::Type, N>) -> Bounds<S::Type> { 207 {
208 #[inline]
209 fn local_analysis(&self, cube: &Cube<N, S::Type>) -> Bounds<S::Type> {
208 // The function is maximised/minimised where the 2-norm is minimised/maximised. 210 // The function is maximised/minimised where the 2-norm is minimised/maximised.
209 let lower = self.apply(cube.maxnorm_point()); 211 let lower = self.apply(cube.maxnorm_point());
210 let upper = self.apply(cube.minnorm_point()); 212 let upper = self.apply(cube.minnorm_point());
211 Bounds(lower, upper) 213 Bounds(lower, upper)
212 } 214 }
213 } 215 }
214 216
215 #[replace_float_literals(C::Type::cast_from(literal))] 217 #[replace_float_literals(C::Type::cast_from(literal))]
216 impl<'a, C : Constant, const N : usize> Norm<C::Type, L1> 218 impl<'a, C: Constant, const N: usize> Norm<L1, C::Type> for Gaussian<C, N> {
217 for Gaussian<C, N> { 219 #[inline]
218 #[inline] 220 fn norm(&self, _: L1) -> C::Type {
219 fn norm(&self, _ : L1) -> C::Type {
220 1.0 221 1.0
221 } 222 }
222 } 223 }
223 224
224 #[replace_float_literals(C::Type::cast_from(literal))] 225 #[replace_float_literals(C::Type::cast_from(literal))]
225 impl<'a, C : Constant, const N : usize> Norm<C::Type, Linfinity> 226 impl<'a, C: Constant, const N: usize> Norm<Linfinity, C::Type> for Gaussian<C, N> {
226 for Gaussian<C, N> { 227 #[inline]
227 #[inline] 228 fn norm(&self, _: Linfinity) -> C::Type {
228 fn norm(&self, _ : Linfinity) -> C::Type {
229 self.bounds().upper() 229 self.bounds().upper()
230 } 230 }
231 } 231 }
232 232
233 #[replace_float_literals(C::Type::cast_from(literal))] 233 #[replace_float_literals(C::Type::cast_from(literal))]
234 impl<'a, C : Constant, const N : usize> Fourier<C::Type> 234 impl<'a, C: Constant, const N: usize> Fourier<C::Type> for Gaussian<C, N> {
235 for Gaussian<C, N> { 235 type Domain = Loc<N, C::Type>;
236 type Domain = Loc<C::Type, N>;
237 type Transformed = Weighted<Gaussian<C::Type, N>, C::Type>; 236 type Transformed = Weighted<Gaussian<C::Type, N>, C::Type>;
238 237
239 #[inline] 238 #[inline]
240 fn fourier(&self) -> Self::Transformed { 239 fn fourier(&self) -> Self::Transformed {
241 let π = C::Type::PI; 240 let π = C::Type::PI;
242 let σ2 = self.variance.value(); 241 let σ2 = self.variance.value();
243 let g = Gaussian { variance : 1.0 / (4.0*π*π*σ2) }; 242 let g = Gaussian { variance: 1.0 / (4.0 * π * π * σ2) };
244 g.weigh(g.scale()) 243 g.weigh(g.scale())
245 } 244 }
246 } 245 }
247 246
248 /// Representation of the “cut” gaussian $f χ\_{[-a, a]^n}$ 247 /// Representation of the “cut” gaussian $f χ\_{[-a, a]^n}$
249 /// where $a>0$ and $f$ is a gaussian kernel on $ℝ^n$. 248 /// where $a>0$ and $f$ is a gaussian kernel on $ℝ^n$.
250 pub type BasicCutGaussian<C, S, const N : usize> = SupportProductFirst<CubeIndicator<C, N>, 249 pub type BasicCutGaussian<C, S, const N: usize> =
251 Gaussian<S, N>>; 250 SupportProductFirst<CubeIndicator<C, N>, Gaussian<S, N>>;
252
253 251
254 /// This implements $g := χ\_{[-b, b]^n} \* (f χ\_{[-a, a]^n})$ where $a,b>0$ and $f$ is 252 /// This implements $g := χ\_{[-b, b]^n} \* (f χ\_{[-a, a]^n})$ where $a,b>0$ and $f$ is
255 /// a gaussian kernel on $ℝ^n$. For an expression for $g$, see Lemma 3.9 in the manuscript. 253 /// a gaussian kernel on $ℝ^n$. For an expression for $g$, see Lemma 3.9 in the manuscript.
256 #[replace_float_literals(F::cast_from(literal))] 254 #[replace_float_literals(F::cast_from(literal))]
257 impl<'a, F : Float, R, C, S, const N : usize> Mapping<Loc<F, N>> 255 impl<'a, F: Float, R, C, S, const N: usize> Mapping<Loc<N, F>>
258 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 256 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
259 where R : Constant<Type=F>, 257 where
260 C : Constant<Type=F>, 258 R: Constant<Type = F>,
261 S : Constant<Type=F> { 259 C: Constant<Type = F>,
262 260 S: Constant<Type = F>,
261 {
263 type Codomain = F; 262 type Codomain = F;
264 263
265 #[inline] 264 #[inline]
266 fn apply<I : Instance<Loc<F, N>>>(&self, y : I) -> F { 265 fn apply<I: Instance<Loc<N, F>>>(&self, y: I) -> F {
267 let Convolution(ref ind, 266 let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self;
268 SupportProductFirst(ref cut,
269 ref gaussian)) = self;
270 let a = cut.r.value(); 267 let a = cut.r.value();
271 let b = ind.r.value(); 268 let b = ind.r.value();
272 let σ = gaussian.variance.value().sqrt(); 269 let σ = gaussian.variance.value().sqrt();
273 let t = F::SQRT_2 * σ; 270 let t = F::SQRT_2 * σ;
274 let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2 271 let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2
275 272
276 // This is just a product of one-dimensional versions 273 // This is just a product of one-dimensional versions
277 y.cow().product_map(|x| { 274 y.decompose().product_map(|x| {
278 let c1 = -(a.min(b + x)); //(-a).max(-x-b); 275 let c1 = -(a.min(b + x)); //(-a).max(-x-b);
279 let c2 = a.min(b - x); 276 let c2 = a.min(b - x);
280 if c1 >= c2 { 277 if c1 >= c2 {
281 0.0 278 0.0
282 } else { 279 } else {
291 288
292 /// This implements the differential of $g := χ\_{[-b, b]^n} \* (f χ\_{[-a, a]^n})$ where $a,b>0$ 289 /// This implements the differential of $g := χ\_{[-b, b]^n} \* (f χ\_{[-a, a]^n})$ where $a,b>0$
293 /// and $f$ is a gaussian kernel on $ℝ^n$. For an expression for the value of $g$, from which the 290 /// and $f$ is a gaussian kernel on $ℝ^n$. For an expression for the value of $g$, from which the
294 /// derivative readily arises (at points of differentiability), see Lemma 3.9 in the manuscript. 291 /// derivative readily arises (at points of differentiability), see Lemma 3.9 in the manuscript.
295 #[replace_float_literals(F::cast_from(literal))] 292 #[replace_float_literals(F::cast_from(literal))]
296 impl<'a, F : Float, R, C, S, const N : usize> DifferentiableImpl<Loc<F, N>> 293 impl<'a, F: Float, R, C, S, const N: usize> DifferentiableImpl<Loc<N, F>>
297 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 294 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
298 where R : Constant<Type=F>, 295 where
299 C : Constant<Type=F>, 296 R: Constant<Type = F>,
300 S : Constant<Type=F> { 297 C: Constant<Type = F>,
301 298 S: Constant<Type = F>,
302 type Derivative = Loc<F, N>; 299 {
300 type Derivative = Loc<N, F>;
303 301
304 /// Although implemented, this function is not differentiable. 302 /// Although implemented, this function is not differentiable.
305 #[inline] 303 #[inline]
306 fn differential_impl<I : Instance<Loc<F, N>>>(&self, y0 : I) -> Loc<F, N> { 304 fn differential_impl<I: Instance<Loc<N, F>>>(&self, y0: I) -> Loc<N, F> {
307 let Convolution(ref ind, 305 let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self;
308 SupportProductFirst(ref cut, 306 let y = y0.decompose();
309 ref gaussian)) = self;
310 let y = y0.cow();
311 let a = cut.r.value(); 307 let a = cut.r.value();
312 let b = ind.r.value(); 308 let b = ind.r.value();
313 let σ = gaussian.variance.value().sqrt(); 309 let σ = gaussian.variance.value().sqrt();
314 let t = F::SQRT_2 * σ; 310 let t = F::SQRT_2 * σ;
315 let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2 311 let c = 0.5; // 1/(σ√(2π) * σ√(π/2) = 1/2
316 let c_mul_erf_scale_div_t = c * F::FRAC_2_SQRT_PI / t; 312 let c_mul_erf_scale_div_t = c * F::FRAC_2_SQRT_PI / t;
317 313
318 // Calculate the values for all component functions of the 314 // Calculate the values for all component functions of the
319 // product. This is just the loop from apply above. 315 // product. This is just the loop from apply above.
320 let unscaled_vs = y.map(|x| { 316 let unscaled_vs = y.map(|x| {
321 let c1 = -(a.min(b + x)); //(-a).max(-x-b); 317 let c1 = -(a.min(b + x)); //(-a).max(-x-b);
322 let c2 = a.min(b - x); 318 let c2 = a.min(b - x);
338 } else { 334 } else {
339 // erf'(z) = (2/√π)*exp(-z^2), and we get extra factor 1/(√2*σ) = -1/t 335 // erf'(z) = (2/√π)*exp(-z^2), and we get extra factor 1/(√2*σ) = -1/t
340 // from the chain rule (the minus comes from inside c_1 or c_2, and changes the 336 // from the chain rule (the minus comes from inside c_1 or c_2, and changes the
341 // order of de2 and de1 in the final calculation). 337 // order of de2 and de1 in the final calculation).
342 let de1 = if b + x < a { 338 let de1 = if b + x < a {
343 (-((b+x)/t).powi(2)).exp() 339 (-((b + x) / t).powi(2)).exp()
344 } else { 340 } else {
345 0.0 341 0.0
346 }; 342 };
347 let de2 = if b - x < a { 343 let de2 = if b - x < a {
348 (-((b-x)/t).powi(2)).exp() 344 (-((b - x) / t).powi(2)).exp()
349 } else { 345 } else {
350 0.0 346 0.0
351 }; 347 };
352 c_mul_erf_scale_div_t * (de1 - de2) 348 c_mul_erf_scale_div_t * (de1 - de2)
353 } 349 }
354 }) 350 })
355 } 351 }
356 } 352 }
357 353
358
359 #[replace_float_literals(F::cast_from(literal))] 354 #[replace_float_literals(F::cast_from(literal))]
360 impl<'a, F : Float, R, C, S, const N : usize> Lipschitz<L1> 355 impl<'a, F: Float, R, C, S, const N: usize> Lipschitz<L1>
361 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 356 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
362 where R : Constant<Type=F>, 357 where
363 C : Constant<Type=F>, 358 R: Constant<Type = F>,
364 S : Constant<Type=F> { 359 C: Constant<Type = F>,
360 S: Constant<Type = F>,
361 {
365 type FloatType = F; 362 type FloatType = F;
366 363
367 fn lipschitz_factor(&self, L1 : L1) -> Option<F> { 364 fn lipschitz_factor(&self, L1: L1) -> DynResult<F> {
368 // To get the product Lipschitz factor, we note that for any ψ_i, we have 365 // To get the product Lipschitz factor, we note that for any ψ_i, we have
369 // ∏_{i=1}^N φ_i(x_i) - ∏_{i=1}^N φ_i(y_i) 366 // ∏_{i=1}^N φ_i(x_i) - ∏_{i=1}^N φ_i(y_i)
370 // = [φ_1(x_1)-φ_1(y_1)] ∏_{i=2}^N φ_i(x_i) 367 // = [φ_1(x_1)-φ_1(y_1)] ∏_{i=2}^N φ_i(x_i)
371 // + φ_1(y_1)[ ∏_{i=2}^N φ_i(x_i) - ∏_{i=2}^N φ_i(y_i)] 368 // + φ_1(y_1)[ ∏_{i=2}^N φ_i(x_i) - ∏_{i=2}^N φ_i(y_i)]
372 // = ∑_{j=1}^N [φ_j(x_j)-φ_j(y_j)]∏_{i > j} φ_i(x_i) ∏_{i < j} φ_i(y_i) 369 // = ∑_{j=1}^N [φ_j(x_j)-φ_j(y_j)]∏_{i > j} φ_i(x_i) ∏_{i < j} φ_i(y_i)
396 // 393 //
397 // If c_1(x) ≥ c_2(x), then x ∉ [-(a+b), a+b]. If also y is outside that range, 394 // If c_1(x) ≥ c_2(x), then x ∉ [-(a+b), a+b]. If also y is outside that range,
398 // θ * ψ(x) = θ * ψ(y). If only y is in the range [-(a+b), a+b], we can replace 395 // θ * ψ(x) = θ * ψ(y). If only y is in the range [-(a+b), a+b], we can replace
399 // x by -(a+b) or (a+b), either of which is closer to y and still θ * ψ(x)=0. 396 // x by -(a+b) or (a+b), either of which is closer to y and still θ * ψ(x)=0.
400 // Thus same calculations as above work for the Lipschitz factor. 397 // Thus same calculations as above work for the Lipschitz factor.
401 let Convolution(ref ind, 398 let Convolution(ref ind, SupportProductFirst(ref cut, ref gaussian)) = self;
402 SupportProductFirst(ref cut,
403 ref gaussian)) = self;
404 let a = cut.r.value(); 399 let a = cut.r.value();
405 let b = ind.r.value(); 400 let b = ind.r.value();
406 let σ = gaussian.variance.value().sqrt(); 401 let σ = gaussian.variance.value().sqrt();
407 let π = F::PI; 402 let π = F::PI;
408 let t = F::SQRT_2 * σ; 403 let t = F::SQRT_2 * σ;
409 let l1d = F::SQRT_2 / (π.sqrt() * σ); 404 let l1d = F::SQRT_2 / (π.sqrt() * σ);
410 let e0 = F::cast_from(erf((a.min(b) / t).as_())); 405 let e0 = F::cast_from(erf((a.min(b) / t).as_()));
411 Some(l1d * e0.powi(N as i32-1)) 406 Ok(l1d * e0.powi(N as i32 - 1))
412 } 407 }
413 } 408 }
414 409
415 /* 410 /*
416 impl<'a, F : Float, R, C, S, const N : usize> Lipschitz<L2> 411 impl<'a, F : Float, R, C, S, const N : usize> Lipschitz<L2>
424 self.lipschitz_factor(L1).map(|l1| l1 * <S::Type>::cast_from(N).sqrt()) 419 self.lipschitz_factor(L1).map(|l1| l1 * <S::Type>::cast_from(N).sqrt())
425 } 420 }
426 } 421 }
427 */ 422 */
428 423
429 impl<F : Float, R, C, S, const N : usize> 424 impl<F: Float, R, C, S, const N: usize> Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
430 Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 425 where
431 where R : Constant<Type=F>, 426 R: Constant<Type = F>,
432 C : Constant<Type=F>, 427 C: Constant<Type = F>,
433 S : Constant<Type=F> { 428 S: Constant<Type = F>,
434 429 {
435 #[inline] 430 #[inline]
436 fn get_r(&self) -> F { 431 fn get_r(&self) -> F {
437 let Convolution(ref ind, 432 let Convolution(ref ind, SupportProductFirst(ref cut, ..)) = self;
438 SupportProductFirst(ref cut, ..)) = self;
439 ind.r.value() + cut.r.value() 433 ind.r.value() + cut.r.value()
440 } 434 }
441 } 435 }
442 436
443 impl<F : Float, R, C, S, const N : usize> Support<F, N> 437 impl<F: Float, R, C, S, const N: usize> Support<N, F>
444 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 438 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
445 where R : Constant<Type=F>, 439 where
446 C : Constant<Type=F>, 440 R: Constant<Type = F>,
447 S : Constant<Type=F> { 441 C: Constant<Type = F>,
448 #[inline] 442 S: Constant<Type = F>,
449 fn support_hint(&self) -> Cube<F, N> { 443 {
444 #[inline]
445 fn support_hint(&self) -> Cube<N, F> {
450 let r = self.get_r(); 446 let r = self.get_r();
451 array_init(|| [-r, r]).into() 447 array_init(|| [-r, r]).into()
452 } 448 }
453 449
454 #[inline] 450 #[inline]
455 fn in_support(&self, y : &Loc<F, N>) -> bool { 451 fn in_support(&self, y: &Loc<N, F>) -> bool {
456 let r = self.get_r(); 452 let r = self.get_r();
457 y.iter().all(|x| x.abs() <= r) 453 y.iter().all(|x| x.abs() <= r)
458 } 454 }
459 455
460 #[inline] 456 #[inline]
461 fn bisection_hint(&self, cube : &Cube<F, N>) -> [Option<F>; N] { 457 fn bisection_hint(&self, cube: &Cube<N, F>) -> [Option<F>; N] {
462 let r = self.get_r(); 458 let r = self.get_r();
463 // From c1 = -a.min(b + x) and c2 = a.min(b - x) with c_1 < c_2, 459 // From c1 = -a.min(b + x) and c2 = a.min(b - x) with c_1 < c_2,
464 // solve bounds for x. that is 0 ≤ a.min(b + x) + a.min(b - x). 460 // solve bounds for x. that is 0 ≤ a.min(b + x) + a.min(b - x).
465 // If b + x ≤ a and b - x ≤ a, the sum is 2b ≥ 0. 461 // If b + x ≤ a and b - x ≤ a, the sum is 2b ≥ 0.
466 // If b + x ≥ a and b - x ≥ a, the sum is 2a ≥ 0. 462 // If b + x ≥ a and b - x ≥ a, the sum is 2a ≥ 0.
468 // If b + x ≥ a and b - x ≤ a, the sum is a + b - x ⟹ need x ≤ a + b = r. 464 // If b + x ≥ a and b - x ≤ a, the sum is a + b - x ⟹ need x ≤ a + b = r.
469 cube.map(|c, d| symmetric_peak_hint(r, c, d)) 465 cube.map(|c, d| symmetric_peak_hint(r, c, d))
470 } 466 }
471 } 467 }
472 468
473 impl<F : Float, R, C, S, const N : usize> GlobalAnalysis<F, Bounds<F>> 469 impl<F: Float, R, C, S, const N: usize> GlobalAnalysis<F, Bounds<F>>
474 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 470 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
475 where R : Constant<Type=F>, 471 where
476 C : Constant<Type=F>, 472 R: Constant<Type = F>,
477 S : Constant<Type=F> { 473 C: Constant<Type = F>,
474 S: Constant<Type = F>,
475 {
478 #[inline] 476 #[inline]
479 fn global_analysis(&self) -> Bounds<F> { 477 fn global_analysis(&self) -> Bounds<F> {
480 Bounds(F::ZERO, self.apply(Loc::ORIGIN)) 478 Bounds(F::ZERO, self.apply(Loc::ORIGIN))
481 } 479 }
482 } 480 }
483 481
484 impl<F : Float, R, C, S, const N : usize> LocalAnalysis<F, Bounds<F>, N> 482 impl<F: Float, R, C, S, const N: usize> LocalAnalysis<F, Bounds<F>, N>
485 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>> 483 for Convolution<CubeIndicator<R, N>, BasicCutGaussian<C, S, N>>
486 where R : Constant<Type=F>, 484 where
487 C : Constant<Type=F>, 485 R: Constant<Type = F>,
488 S : Constant<Type=F> { 486 C: Constant<Type = F>,
489 #[inline] 487 S: Constant<Type = F>,
490 fn local_analysis(&self, cube : &Cube<F, N>) -> Bounds<F> { 488 {
489 #[inline]
490 fn local_analysis(&self, cube: &Cube<N, F>) -> Bounds<F> {
491 // The function is maximised/minimised where the absolute value is minimised/maximised. 491 // The function is maximised/minimised where the absolute value is minimised/maximised.
492 let lower = self.apply(cube.maxnorm_point()); 492 let lower = self.apply(cube.maxnorm_point());
493 let upper = self.apply(cube.minnorm_point()); 493 let upper = self.apply(cube.minnorm_point());
494 Bounds(lower, upper) 494 Bounds(lower, upper)
495 } 495 }
496 } 496 }
497

mercurial