| 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) |
| 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 |
|