# Reproducing Polynomials with B-Splines

Niki (Diskussion | Beiträge) |
Niki (Diskussion | Beiträge) |
||

(4 dazwischenliegende Versionen von einem Benutzer werden nicht angezeigt) | |||

Zeile 1: | Zeile 1: | ||

<section begin="head"/> | <section begin="head"/> | ||

[[Datei:bspline_family.png|right|150px|Family of B-splines up to N=4]] | [[Datei:bspline_family.png|right|150px|Family of B-splines up to N=4]] | ||

− | A B-Spline of order <math>N</math> is known to be able to reproduce any polynomial up to order <math>N</math | + | A B-Spline of order <math>N</math> is known to be able to reproduce any polynomial up to order <math>N</math>: |

<math> | <math> | ||

Zeile 7: | Zeile 7: | ||

</math> | </math> | ||

− | In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order <math>N</math>. This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework | + | In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order <math>N</math>. This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework. In this case any kernel <math>\varphi</math> reproducing polynomials (that is, satisfying the Strang-Fix conditions) can be used. However, among all possible kernels, the B-Splines have the smallest possible support. |

An important question is how to obtain the coefficients <math>c_{m,n}</math> for the reproduction-formula. In this small article, I describe one way. | An important question is how to obtain the coefficients <math>c_{m,n}</math> for the reproduction-formula. In this small article, I describe one way. | ||

Zeile 18: | Zeile 18: | ||

</math> | </math> | ||

− | the coefficients can be obtained using the dual of <math>\varphi</math>, <math>\tilde{\varphi}</math> (I set <math>\beta_N = \varphi</math> for consistency with my notes): | + | the coefficients can be obtained using the dual of <math>\varphi</math>, <math>\tilde{\varphi}</math><ref>P.L. Dragotti, M. Vetterli, T.Blu: "Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang-Fix", ''IEEE Transactions on Signal Processing'', vol. 55, No. 5, May 2007</ref> (I set <math>\beta_N = \varphi</math> for consistency with my notes): |

<math> | <math> | ||

Zeile 56: | Zeile 56: | ||

</math> | </math> | ||

− | Now the whole procedure has been reduced to | + | Now the whole procedure has been reduced to calculating the derivative of <math>f(\omega)</math> and set the result to zero. |

− | An open question is how to obtain the dual of <math>\varphi</math>. As the reproduction formula spans a vector space, | + | An open question is how to obtain the dual of <math>\varphi</math>. As the reproduction formula spans a vector space, <math>\varphi</math> must be at least bi-orthogonal to <math>\tilde{\varphi}</math>. This translates in fourier domain to<ref>S. Mallat: "A Wavelet Tour of Signal Processing", ''Academic Press'' 1999</ref>: |

<math> | <math> | ||

Zeile 71: | Zeile 71: | ||

</math> | </math> | ||

− | The following derivation of the sum is borrowed from <ref>M.J.C.S. Reis, P.J.S.G. Ferreira, S.F.S.P. Soares: "Linear combinations of B-splines as generating functions for signal approximation", ''Elsevier Digital Signal Processing 15'', 2005</ref>. For this derivation to work, I set <math>L=N+1</math> | + | The following derivation of the sum is borrowed from <ref>M.J.C.S. Reis, P.J.S.G. Ferreira, S.F.S.P. Soares: "Linear combinations of B-splines as generating functions for signal approximation", ''Elsevier Digital Signal Processing 15'', 2005</ref>. For this derivation to work, I set <math>L=N+1</math> temporarily: |

<math> | <math> | ||

Zeile 98: | Zeile 98: | ||

</math> | </math> | ||

− | And finally the following relation is used: | + | And finally the following relation is used<ref>L.V. Ahlfors: "Complex Analysis", ''McGraw-Hill'', 1979</ref>: |

<math> | <math> | ||

Zeile 154: | Zeile 154: | ||

= References = | = References = | ||

+ | |||

+ | <ref name="schoenberg">I.J. Schoenberg: "Cardinal interpolation and spline functions", ''J. Approx. Theory volume 2'', pp. 167-206, 1969</ref> | ||

<references/> | <references/> |

## Aktuelle Version vom 19. Juli 2010, 16:45 Uhr

A B-Spline of order is known to be able to reproduce any polynomial up to order :

In words, a proper linear combination of shifted versions of a B-Spline can reproduce any polynomial up to order . This is needed for different applications, for example, for the Sampling at Finite Rate of Innovation (FRI) framework. In this case any kernel reproducing polynomials (that is, satisfying the Strang-Fix conditions) can be used. However, among all possible kernels, the B-Splines have the smallest possible support.

An important question is how to obtain the coefficients for the reproduction-formula. In this small article, I describe one way.

Starting from

the coefficients can be obtained using the dual of , ^{[1]} (I set for consistency with my notes):

However, even if the dual would be known, solving the infinite integral is only feasible when the dual has finite support. This is the case with the B-Spline itself but not with its dual!

A closer look at the formula tells that this is nothing more than a convolution (under the assumption that is symmetric which is the case):

Now, this can be transformed to fourier domain:

Writing the inverse of this expression yields:

It is known that^{[2]}:

so that

Now the whole procedure has been reduced to calculating the derivative of and set the result to zero.

An open question is how to obtain the dual of . As the reproduction formula spans a vector space, must be at least bi-orthogonal to . This translates in fourier domain to^{[3]}:

The fourier transform of a B-Spline of order is (e.g. ^{[4]}):

The following derivation of the sum is borrowed from ^{[5]}. For this derivation to work, I set temporarily:

and because is always even:

Because of the periodicity it is known that

such that

And finally the following relation is used^{[6]}:

in order to finally obtain:

and with :

Therefore, together with this yields:

and finally substituting for :

As this function is not well defined it is better to use the limit:

## Inhaltsverzeichnis |

# [Bearbeiten] Examples for a cubic spline

For a cubic spline (N=3) the coefficients are:

# [Bearbeiten] References

^{[7]}

- ↑ P.L. Dragotti, M. Vetterli, T.Blu: "Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang-Fix",
*IEEE Transactions on Signal Processing*, vol. 55, No. 5, May 2007 - ↑ http://en.wikipedia.org/wiki/Dirac_delta_function
- ↑ S. Mallat: "A Wavelet Tour of Signal Processing",
*Academic Press*1999 - ↑ M.Unser: "Splines - A Perfect Fit for Signal and Imaging Processing",
*IEEE Signal Processing Magazine*Nov. 1999 - ↑ M.J.C.S. Reis, P.J.S.G. Ferreira, S.F.S.P. Soares: "Linear combinations of B-splines as generating functions for signal approximation",
*Elsevier Digital Signal Processing 15*, 2005 - ↑ L.V. Ahlfors: "Complex Analysis",
*McGraw-Hill*, 1979 - ↑ I.J. Schoenberg: "Cardinal interpolation and spline functions",
*J. Approx. Theory volume 2*, pp. 167-206, 1969

Bussi

--Manu 19:47, 19. Jul. 2010 (MSD)