Partitions of unity and monotonicity-preserving approximation

There are many ways to approximate a given continuous function ${f\colon [a, b]\to \mathbb R}$ (I will consider the interval ${[a, b]=[0, 1]}$ for convenience.) For example, one can use piecewise linear interpolation through the points ${(k/n, f(k/n))}$ , where ${k=0, 1, \dots, n}$ . The resulting piecewise linear function ${g}$ has some nice properties: for example, it is increasing if ${f}$ is increasing. But it is not smooth.

A convenient way to represent piecewise linear interpolation is the sum ${g(x) = \sum_{k=0}^n f(k/n) \varphi_k(x)}$ where the functions ${\varphi_k}$ are the triangles shown below: ${\varphi_k(x) = \max(0, 1 - |nx-k|)}$ .

The functions ${{\varphi_k}}$ form a partition of unity, meaning that ${\sum_k \varphi_k \equiv 1}$ and all ${\varphi_k}$ are nonnegative. This property leads to the estimate

$|f(x) - g(x)| = \left| \sum_{k=0}^n (f(x) - f(k/n)) \varphi_k(x)\right| \le \sum_{k=0}^n |f(x) - f(k/n)| \varphi_k(x)$

The latter sum is small because when ${x}$ is close to ${k/n}$ , the first factor ${|f(x) - f(k/n)|}$ is small by virtue of continuity, while the second factor ${\varphi_k(x)}$ is bounded by ${1}$ . When ${x}$ is far from ${k/n}$ , the second factor ${\varphi_k(x)}$ is zero, so the first one is irrelevant. The upshot is that ${f-g}$ is uniformly small.

But if we want a smooth approximation ${g}$ , we need a smooth partition of unity ${{\varphi_k}}$ . But not just any set of smooth nonnegative functions that add up to ${0}$ is equally good. One desirable property is preserving monotonicity: if ${f}$ is increasing, then ${g}$ should be increasing, just as this works for piecewise linear interpolation. What does this condition require of our partition of unity?

An increasing function can be expressed as a limit of sums of the form ${\sum_{j} c_j [x \ge t_j]}$ where ${c_j>0}$ and ${[\cdots ]}$ is the Iverson bracket: 1 if true, 0 if false. By linearity, it suffices to have increasing ${g}$ for the case ${f(x) = [x \ge t]}$ . In this case ${g}$ is simply ${s_m := \sum_{k=m}^n \varphi_k}$ for some ${m}$ , ${0\le m\le n}$ . So we want all ${s_m}$ to be increasing functions. Which is the case for the triangular partition of unity, when each ${s_m}$ looks like this:

Also known as a piecewise linear activation function

One smooth choice is Bernstein basis polynomials: $\varphi_k(x) = \binom{n}{k} x^k (1-x)^{n-k}$ . These are nonnegative on ${[0, 1]}$ , and the binomial formula shows $\sum_{k=0}^n \varphi_k(x) = (x + 1-x)^n \equiv 1$ . Are the sums $s_m(x) = \sum_{k=m}^n \binom{n}{k} x^k (1-x)^{n-k}$ increasing with ${x}$ ? Let’s find out. By the product rule,

$s_m'(x) = \sum_{k=m}^n \binom{n}{k} k x^{k-1} (1-x)^{n-k} - \sum_{k=m}^n \binom{n}{k} (n-k) x^{k} (1-x)^{n-k - 1}$

In the second sum the term with ${k=n}$ vanishes, and the terms with ${k<n}$ can be rewritten as $\frac{n!}{k! (n-k)!} (n-k) x^{k} (1-x)^{n-k - 1}$ , which is ${\frac{n!}{(k+1)! (n-k-1)!} (k+1) x^{k} (1-x)^{n-k - 1}}$ , which is ${\binom{n}{k+1} (k+1) x^{k} (1-x)^{n-k - 1} }$ . After the index shift ${k+1\mapsto k}$ this becomes identical to the terms of the first sum and cancels them out (except for the first one). Thus,

$s_m'(x) = \binom{n}{m} m x^{m-1} (1-x)^{n-m} \ge 0$

To summarize: the Bernstein polynomials $B_n(x) = \sum_{k=0}^n f(k/n) \binom{n}{k} x^k (1-x)^{n-k}$ are monotone whenever ${f}$ is. On the other hand, the proof that ${B_n\to f}$ uniformly is somewhat complicated by the fact that the polynomial basis functions ${\varphi_k}$ are not localized the way that the triangle basis functions are: the factors ${\varphi_k(x)}$ do not vanish when ${x}$ is far from ${k/n}$ . I refer to Wikipedia for a proof of convergence (which, by the way, is quite slow).

Is there some middle ground between non-smooth triangles and non-localized polynomials? Yes, of course: piecewise polynomials, splines. More specifically, B-splines which can be defined as follows: B-splines of degree ${1}$ are the triangle basis functions shown above; a B-spline of degree ${d+1}$ is the moving averages of a ${B}$ -spline of degree ${d}$ with a window of length ${h = 1/n}$ . The moving average of ${F}$ can be written as ${\frac{1}{h} \int_{x-h/2}^{x+h/2} f}$ . We get a partition of unity because the sum of moving averages is the moving average of a sum, and averaging a constant function does not change it.

The splines of even degrees are awkward to work with… they are obtained from the triangles by taking those integrals with ${h/2}$ an odd number of times, which makes their knots fall in the midpoints of the uniform grid instead of the grid points themselves. But I will use ${d=2}$ anyway, because this degree is enough for ${C^1}$ -smooth approximation.

Recall that a triangular basis function ${\varphi_k}$ has slope ${\pm n}$ and is supported on an interval ${[(k-1)h, (k+1)h]}$ where ${h=1/n}$ . Accordingly, its moving average ${\psi_k}$ will be supported on ${[(k-3/2)h, (k+3/2)h]}$ . Since ${\psi_k'(x) = n(\phi_k(x+h/2) - \phi_k(x-h/2))}$ , the second derivative ${\psi_k''}$ is ${n^2}$ when ${-3/2< nx-k< -1/2}$ , is ${-2n^2}$ when ${|nx-k| < 1/2}$ , and is ${n^2}$ again when ${1/2 < nx-k < 3/2}$ . This is enough to figure out the formula for ${\psi_k}$ :

$\psi_k(n) = \begin{cases} (nx-k+3/2)^2 / 2, & -3/2\le nx -k\le -1/2 \\ 3/4 -(nx-k)^2, & -1/2\le nx-k \le 1/2 \\ (nx-k-3/2)^2 / 2, & 1/2\le nx -k \le 3/2 \\ \end{cases}$

These look like:

Nice! But wait a moment, the sum near the endpoints is not constant: it is less than 1 because we do not get a contributions of two splines to the left and right of the interval. To correct for this boundary effect, replace ${\psi_0}$ with ${\psi_0 + \psi_{-1}}$ and ${\psi_n}$ with ${\psi_n + \psi_{n+1}}$ , using “ghost” elements of the basis that lie outside of the actual grid. Now the quadratic B-spline basis is correct:

A smooth partition of unity by quadratic splines

Does this partition of unity preserve monotinicity? Yes, it does: $\sum_{k\ge m}\psi_k'(x) = n\sum_{k\ge m} (\phi_k(x+h/2) - \phi_k(x-h/2)) = n(s(x+h/2) - s(x-h/2))$ which is nonnegative because the sum ${s := \sum_{k\ge m} \phi_k}$ is an increasing piecewise linear function, as noted previously. Same logic works for B-splines of higher degree.

In conclusion, here is a quadratic B-spline approximation (orange) to a tricky increasing function (blue).

One may wonder why the orange curve deviates from the line at the end – did we miss some boundary effect there? Yes, in a way… the spline actually approximates the continuous extension of our original function by constant values on the left and right. Imagine the blue graph continuing to the right as a horizontal line: this creates a corner at ${x=1}$ and the spline is smoothing that corner. To avoid this effect, one may want to extend ${f}$ in a better way and then work with the extended function, not folding the ghosts ${\psi_{-1}, \psi_{n+1}}$ into ${\psi_0, \psi_n}$ .

But even so, B-spline achieves a better approximation than the Bernstein polynomial with the same number of basis functions (eight):

The reason is the non-local nature of the polynomial basis ${\varphi_k}$ , which was noted above. Bernstein polynomials do match the function perfectly at the endpoints, but this is small consolation.

Partitions of unity and monotonicity-preserving approximation

Related

Leave a Reply Cancel reply