Interpolation and convolution

As I discussed in an earlier paper Fomel (1997b), a general approach for constructing the interpolant function W(x,n) in equation (1) is to select an appropriate function basis for representing the function f(x). The functional basis representation has the general form  

$$f (x) = \sum_{k \in K} c_k \psi_k (x)\;,$$ (6)

where $\psi_k(x)$ are basis function, and c_k are the corresponding coefficients. Once an appropriate basis is selected, one can define the W(x,n) function by means of the least squares method.

Unser et al. (1993a) noticed that the function basis idea has an especially simple implementation if the basis is convolutional and satisfies the equation  

$$\psi_k (x) = \beta (x-k)\;.$$ (7)

In other words, the basis is constructed by integer shifts of a single function $\beta(x)$. Substituting formula (7) into equation (6) yields  

$$f (x) = \sum_{k \in K} c_k \beta (x - k)\;.$$ (8)

Evaluating the function f(x) in equation (8) at an integer value n, we obtain the equation  

$$f (n) = \sum_{k \in K} c_k \beta (n-k)\;,$$ (9)

which has the exact form of a discrete convolution. The basis function $\beta(x)$, evaluated at integer values, is digitally convolved with the vector of basis coefficients to produce the sampled values of the function f(x). We can invert equation (9) to obtain the coefficients c_k from f(n) by inverse recursive filtering (deconvolution). In the case of a non-causal filter $\beta(n)$, an appropriate spectral factorization will be needed prior to applying the recursive filtering.

According to the convolutional basis idea, forward interpolation becomes a two-step procedure. The first step is the direct inversion of equation (9): the basis coefficients c_k are found by deconvolving the sampled function f(n) with the factorized filter $\beta(n)$. The second step reconstructs the continuous (or arbitrarily sampled) function f(x) according to formula (8). The two steps could be combined into one, but usually it is more convenient to apply them separately. I show a schematic relationship among different variables in Figure .

 

scheme Figure 10 Schematic relationship among different variables for interpolation with a convolutional basis.