Multiresolution
How to manipulate the period of splines.
Roadmap
We propose the solution to three common tasks.
The upscaling of a spline by some integer magnification factor
An exact upscaling, seen as a geometric operation
A projected upscaling, where a spline of arbitrary degree and delay is produced
The downscaling of a spline by some integer minification factor, with provisions for the case when the minification factor fails to divide entirely the spline period
The rescaling of a spline from a nominal period to an arbitrary period
Upscaling
We consider two approaches to upscale a spline by an arbitrary positive integer magnification \(M\in{\mathbb{N}}+1.\) The first one builds an upscaled spline that is an exact replica of the spline at the nominal scale, except for being larger. The second one offers freedom in the choice of the degree and delay of the upscaled spline.
Exact
A polynomial B-spline \(\beta^{n_{0}}\) of any nonnegative integer degree \(n_{0}\in{\mathbb{N}}\) satisfies the M-scale equality, according to which its version at nominal scale can be expressed as a finite weighted sum of B-splines that are appropriately shifted and shrunk by the factor \(M.\) (Equivalently, a B-spline enlarged by \(M\) can be expressed through B-splines at their nominal scale.) The collection of weights depend on \(n_{0}\) and \(M\) and is called the M-scale filter \(h_{M}^{n_{0}}.\)
Because a spline is itself a weighted sum of shifted B-splines, it benefits from the M-scale equality. Indeed, let a spline of positive integer period \(K_{0}\in{\mathbb{N}}+1\) and delay \(\delta x_{0}\in{\mathbb{R}}\) be defined at nominal scale as
where \(\left(c_{0}[k]\right)_{k=0}^{K_{0}-1}\in{\mathbb{R}}^{K_{0}}\) is the vector of its spline coefficients. Then, we set the origin as the center of enlargment and let its \(M\)-enlarged version be
There, the B-splines that take part in the sum are not at their nominal scale. However, for all \(x\in{\mathbb{R}},\) the M-scale equality implies that
also holds true, where it is more immediately apparent that \(f_{\uparrow M}\) is not only \(K\)-periodic with \(K=M\,K_{0},\) but also a weighted sum of integer-shifted B-splines at nominal scale, with the vector of weights being \({\mathbf{c}}_{\uparrow M}=\left(c_{\uparrow M}[k]\right)_{k=0}^{K-1}\) and the delay being \(\delta x_{\uparrow M}.\) More precisely, the equality between \(f_{\uparrow M}\) and the enlarged \(f_{0}\) is achieved for
and
We now propose a few lines of code that first create a random spline of specified period, degree, and delay, and then enlarge it by a factor \(M.\) We display a stack where the top figure contains the spline at its nominal size and the bottom figure contains the enlarged spline. A pair of synchronized sliders allows one to explore the values taken by the two functions and to conclude that, up to change of scale, the two versions are identical.
Jupyter Lab notebook
Projected
We want now to determine which spline \(\tilde{f}_{\uparrow M}\) of arbitrary degree \(n\in{\mathbb{N}}\) and arbitrary delay \(\delta x\in{\mathbb{R}}\) best approximates the exact magnified spline \(f_{\uparrow M}\) with, as before, a positive integer magnification \(M\in{\mathbb{N}}+1\) and
where the spline of positive integer period \(K_{0}\in{\mathbb{N}}+1\) at nominal scale is
More precisely, for \(K=M\,K_{0},\) we want to establish the value of the spline coefficients \(\tilde{c}_{\uparrow M}\) that parameterize the \(K\)-periodic spline
and are such that the least-squares criterion
is minimized. While the desired spline \(\tilde{f}_{\uparrow M}\) could be directly obtained as f0.upscaled(m).projected(degree = n, delay = dx), we propose here a combined approach. Letting \({\mathbf{[\![}}\cdot\,{\mathbf{]\!]}}\) be the notation for the Iverson bracket, we observe that, \(\forall q\in[0\ldots K],\)
When the coefficients are optimal, \(\frac{\partial J}{\partial \tilde{c}_{\uparrow M}[q]}\) vanishes. Now, the multiplication of this zero value by the quantity \(\tilde{c}_{\uparrow M}[q]\) is still zero, and so is the sum over all indices \(q.\) This leads to
where the last equality involves periodic convolutions and mirrored versions \(\tilde{f}_{\uparrow M}^{\vee}\) of \(\tilde{f}_{\uparrow M}.\) The solution of this equation in terms of the vector \(\tilde{{\mathbf{c}}}_{\uparrow M}=\left(\tilde{c}_{\uparrow M}[q]\right)_{q=0}^{K-1}\) is obtained in the three successive steps
where \(\tilde{x}_{0}=\left(\delta x-M\,\delta x_{0}+\frac{\left(M-1\right)\,\left(n_{0}+1\right)}{2}\right)\) and where \(\left(b^{2n+1}\right)^{-1}\) represents a B-spline inverse sequence.
We now propose a few lines of code that first create a random spline \(f_{0}\) of specified period \(K_{0},\) degree \(n_{0},\) and delay \(\delta x_{0},\) and then display its \(M\)-magnified version \(f_{\uparrow M}.\) The spline \(\tilde{f}_{\uparrow M}\) of arbitrary degree \(n\) and arbitrary delay \(\delta x\) that best represents \(f_{\uparrow M}\) is then determined and displayed. We validate optimality by verifying that a quantity that vanishes in theory does so numerically, too, first through the explicit numerical estimate of an integral, then with the help of convolutions.
Jupyter Lab notebook
Downscaling
Let \(m\in{\mathbb{N}}+1\) be a positive integer minification factor. The goal now is to create an \(m\)-coarser version \(f_{K_{0}\downarrow m}\) of the \(K_{0}\)-periodic spline \(f_{0}\) at nominal scale defined, as before, as
The coarser version \(f_{K_{0}\downarrow m}\) is assumed to be a periodic spline of arbitrary nonnegative integer degree \(n\in{\mathbb{N}},\) arbitrary delay \(\delta x\in{\mathbb{R}},\) and positive integer period \(K=\frac{K_{0}}{\gcd(K_{0},m)}\in{\mathbb{N}}+1.\) This period is shorter than that of \(f_{0}\) when \(m\) and \(K_{0}\) have multiplicative factors in common; otherwise, when \(K_{0}\) and \(M\) are co-primes, \(f_{K_{0}\downarrow m}\) is still coarser than the spline \(f_{0}\) in terms of data details but nevertheless retains its periodicity.
Here is a table that gives \(K\) in terms of \(K_{0}\) and \(m\) for a few examples. The blue entries highlight those cases where the period at nominal scale can be entirely divided by the minification factor. In all other cases, just sufficiently many periods of the \(K_{0}\)-periodic \(f_{0}\) are concatenated to make an extended spline whose overall period is entirely divisible both by \(K_{0}\) and by \(m.\)
K m 1 2 3 4 5 6 K0 1 1 1 1 1 1 1 2 2 1 2 1 2 1 3 3 3 1 3 3 1 4 4 2 4 1 4 2 5 5 5 5 5 1 5 6 6 3 2 3 6 1 7 7 7 7 7 7 7 8 8 4 8 2 8 4 9 9 9 3 9 9 3 10 10 5 10 5 2 5 11 11 11 11 11 11 11 12 12 6 4 3 12 2 13 13 13 13 13 13 13 14 14 7 14 7 14 7 15 15 15 5 15 3 5
From now on, we assume for simplicity the generic case where \(K_{0}=m\,K\) and let the desired minified spline be
Our goal is to determine the spline coefficients \(c_{K_{0}\downarrow m}\) such that the least-squares criterion
is minimized. For reasons that are similar to those developed in the projected-upscaling case, it turns out that
where \(f_{\left(K_{0}\downarrow m\right)\uparrow m}\) is the exact \(m\)-upscaled version of \(f_{K_{0}\downarrow m},\) with \(f_{\left(K_{0}\downarrow m\right)\uparrow m}(x)=f_{K_{0}\downarrow m}(\frac{x}{m})\) for all \(x\in{\mathbb{R}}.\) The vector \({\mathbf{c}}_{K_{0}\downarrow m}=\left(c_{K_{0}\downarrow m}[q]\right)_{q=0}^{K-1}\) is obtained in the three successive steps
where \(x_{0}=\left(\delta x_{0}-m\,\delta x-\frac{\left(m-1\right)\,\left(n+1\right)}{2}\right)\) and \(k_{0}=\left\lfloor x_{0}-\frac{n_{0}+n}{2}\right\rfloor.\)
We now propose a few lines of code that first create a random spline \(f_{0}\) that has a highly composite period \(K_{0}\) that is fixed, but whose degree \(n_{0}\) and delay \(\delta x_{0}\) can be specified. We then determine and display the \(m\)-minified version \(f_{K_{0}\downarrow m}\) of arbitrary degree \(n\) and arbitrary delay \(\delta x.\) We validate optimality by verifying that a quantity that vanishes in theory does so numerically, too, first through the explicit numerical estimate of an integral, then with the help of convolutions.
Jupyter Lab notebook
Next, we propose a notebook where the period of the spline at nominal scale can also be chosen freely. In this case, we display separately \(f_{0}\) and \(f_{K_{0}\downarrow m}.\)
Jupyter Lab notebook
Rescaling
Consider again a periodic spline \(f_{0}\) of nominal period \(K_{0},\) degree \(n_{0},\) and delay \(\delta x_{0},\) characterized by the vector \(\left(c_{0}[k]\right)_{k=0}^{K_{0}-1}\) of spline coefficients. We want now to establish a new periodic spline \(f_{K_{0}\rightarrow K}\) of arbitrary period \(K\in{\mathbb{N}}+1,\) arbitrary degree \(n\in{\mathbb{N}},\) and arbitrary delay \(\delta x\in{\mathbb{R}}\) such that the least-squares criterion
is minimized, with
To do so, we first perform an exact upscaling of \(f_{0}\) by the integer magnification factor \(\frac{K}{G},\) with \(G=\gcd(K_{0},K).\) This yields the intermediate spline \(f_{K_{0}\uparrow\frac{K}{G}},\) which is \(\left(\frac{K_{0}\,K}{G}\right)\)-periodic, has the same degree as \(f_{0},\) and has the non-arbitrary delay \(\delta x_{\uparrow\frac{K}{G}}.\) Then, we perform a downscaling of \(f_{K_{0}\uparrow\frac{K}{G}}\) by the integer minification factor \(\frac{K_{0}}{G},\) with arbitrary degree \(n\) and arbitrary delay \(\delta x.\) This yields the final spline \(f_{K_{0}\rightarrow K}=f_{\left(K_{0}\uparrow\frac{K}{G}\right)\downarrow\frac{K_{0}}{G}},\) which is \(K\)-periodic.
Our proposed approach has the desirable property that it results in the exact minimization of the least-squares criterion. However, it relies on the explicit computation and storage of an intermediate spline whose period can be as large as the product \(K_{0}\,K\) whenever the nominal period \(K_{0}\) and the final period \(K\) are co-prime.
Here is a table that gives \(\frac{K_{0}\,K}{\gcd(K_{0},K)}\) in terms of \(K_{0}\) and \(K\) for a few examples. The blue entries highlight those cases where the intermediate period exceeds neither the nominal nor the rescaled period.
K0 K ∕ gcd(K0, K) K 1 2 3 4 5 6 7 8 9 10 K0 1 1 2 3 4 5 6 7 8 9 10 2 2 2 6 4 10 6 14 8 18 10 3 3 6 3 12 15 6 21 24 9 30 4 4 4 12 4 20 12 28 8 36 20 5 5 10 15 20 5 30 35 40 45 10 6 6 6 6 12 30 6 42 24 18 30 7 7 14 21 28 35 42 7 56 63 70 8 8 8 24 8 40 24 56 8 72 40 9 9 18 9 36 45 18 63 72 9 90 10 10 10 30 20 10 30 70 40 90 10
Here are a few lines of code that first create a random spline \(f_{0}\) whose period \(K_{0},\) degree \(n_{0},\) and delay \(\delta x_{0}\) can be specified. We then determine and display its optimal version \(f_{K_{0}\rightarrow K}\) of arbitrary period \(K,\) degree \(n,\) and delay \(\delta x.\) We validate optimality by verifying that a quantity that vanishes in theory does so numerically.
Jupyter Lab notebook