1

The Nyquist limit for interpolation by trig functions states that one must give at least two data points per wavelength, because data just above and just below this "folding frequency" cannot be distinguished. I am currently playing with Hermite interpolation, providing the first few derivatives as well as the function values, and find that the Nyquist limit no longer applies. This cannot be a new observation, but I don't find anything about it online. Maybe I have not got the appropriate vocabulary?

Philip Roe
  • 1,140
  • Well, if you have the sample values and the derivatives, then you have more information than what is used to derive the Nyquist limit, so it doesn't sound surprising. – AnonSubmitter85 Oct 12 '23 at 17:54
  • @AnonSubmitter. I am not all that surprised, and indeed rather excited. My application is the high-order numerical solution of hyperbolic p.d.e.s. Before trying to dig into the implications for myself, I had hoped to discover what is already known. – Philip Roe Oct 12 '23 at 18:06
  • It's interesting. The best I can do is point you to this other question that caught my interest here. It's seems very germane to your question. – AnonSubmitter85 Oct 12 '23 at 19:59
  • Thanks! I feel as if Im either about to make a breakthrough or else fall fall into a deep dark pit. – Philip Roe Oct 12 '23 at 21:04
  • There's way too little information in your question. It's unclear what you mean by "the Nyquist limit doesn't apply" or how you decided this is the case. As far as PDEs go, in both FDM and FEM methods higher order discretisations lead to a faster convergence to the true solution in terms of the grid spacing, e.g. $O(h^p)$ where $p$ is related to the degree of the polynomials usdd for the approximation. – lightxbulb Oct 14 '23 at 09:11
  • @lightxbulb. Yes, I do know that about PDEs, and you probably know that von Neumann analysis typically is applied up tp $\theta=\pi$, the Nyquist folding frequency, as I described in my post. When you also have derivative information, the two frequencies CAN be distinguished, and the analysis APPEARS to be significant, at least up to $2\pi$, but has some odd features that I intend to analyse somehow. Before embarking on this, I want to find out what may already be known about Hermite interpolation at subNyquist wavelengths – Philip Roe Oct 15 '23 at 16:25
  • @PhilipRoe Maybe I am misunderstanding something, but in your post you're referring to Shannon's sampling theorem. However the latter applies to regular grid point samples of the function you care about. For Hermite interpolation you use both point samples and derivatives - note that Shannon's theorem doesn't even assume the function is differentiable, so I cannot understand what "the Nyquist limit no longer applies" means. As far as PDEs ard concerned there are elements in FEM which support defining derivatives, which results in a better $O(h^p)$ convergence of the error. – lightxbulb Oct 16 '23 at 16:57
  • What I want to know is whether there is some kind of analogue to Shannons theorem if regularly sampled derivatives are also available. At $x_j=j\Delta x$ I have $u(x_j), u^1(x_j),u^2(x_j)..$. Does this allow me to go to subNyquist wavelengths? I have seen some of the FEM analysis (discontinuous Galerkin, flux reconstruction) showing dispersion relations that seem to do so, but it seems to me that these require interpretation to understand their practical significance. This is complicated by the existence of multiple solutions to the polynomials that arise. – Philip Roe Oct 17 '23 at 05:53
  • I have a pde method that I believe has advantages over those, but before diving into comparisons I was hoping to discover more about Hermite interpolation in the simplest possible setting. I have found survey papers about Hermitian integration for ODEs, for example, but much to my surprise have not yet found mentionof any "Shannon-like" theorem. I believe that I must be looking in the wrong places – Philip Roe Oct 17 '23 at 06:08

1 Answers1

1

Since you're looking for a Shannon-like theorem that involves the derivatives you can have a look at the following stackexhcange post which refers to the following paper by Papoulis. The theorem there is more powerful as you can take $m$ linear functionals (with some constraints on those) and if you sample at a frequency higher than $1/m$ the Nyquist rate you will get a perfect reconstruction. In the paper the author specifically shows some examples involving the derivatives. Note that the reconstruction function is not necessarily a $sinc$ function anymore. In essence if you provide $m$ times more non-redundant information you can expect to require a rate that is $m$ times lower.

Note however, that the $sinc$ kernel isn't even the best kernel to formulate a sampling theorem for trigonometric polynomials in practice. Instead the Dirichlet kernel $$D_n(x) = \frac{\sin\left(\left(n+\frac{1}{2}\right)\pi x\right)}{\sin\left(\frac{\pi x}{2}\right)}$$ allows one to formulate a similar result as the sampling theorem for trigonometric polynomials of order $n$, where you only need to sum up finitely many terms (unlike the usual case where you need infinitely many terms).

As far as Hermite interpolation goes there is the following paper by Shin that provides an expansion of a function in terms of generalized Hermite interpolating polynomials involving samples of the function and its derivatives, and the author also formulates a sampling theorem for this at the end. You can see a similar result to the one from Papoulis' paper where the required sampling frequency $\sigma'$ scales inversely proportionally to the amount of data provided $N$.

lightxbulb
  • 2,047
  • I would think that paper by Papoulis exactly answers the question. – AnonSubmitter85 Oct 19 '23 at 18:41
  • @AnonSubmitter85 I am not sure, since Philip Roe seemed to have other questions related to Hermite interpolation, finite elements, von Neumann analysis and so on, but since I am not sure I answered only the question I could make sense of. However based on the comments I am assuming that it is something related to Hermite interpolation elements and their approximation qualities for numerical solutions of PDEs, and specifically some kind of Fourier analysis of said error. Without more details I can't say anything though, and even with more details I may still be unable to. – lightxbulb Oct 19 '23 at 18:48
  • @lightxbulb. You are correct(ish) There are surprising differences of expectation between apparently similar fields. In signal processing errors may already have occurred in measuring the signal. In numerical PDEs the data is fine, but errors accumulate as the solution proceeds. In computer graphics we often require an aesthetically pleasing surface. In PDEs we often deal with non-smooth behavior.

    Hermite methods are almost unused in hyperbolic PDEs but I think they may have merit. Before getting in too deeply I wanted to find what was known from other fields. Your guesses were helpful.

     – Philip Roe Oct 21 '23 at 02:53
  • @PhilipRoe Hermite elements should be perfectly applicable to hyperbloic PDEs. For example onsider as a model problem the wave equation $\partial_{tt} u = c^2\Delta u$. Compared to Lagrange elements Hermite elements allow you to prescribe derivative information at vertices: useful to implement boundary conditions involving $\partial_{n} u = g$ or to prescribe derivative constraints within the domain. In 2D this generalizes in many different ways: see Hermite, Thomas-Raviart, Nedelec, Morley, Bell, and Argyris elements. The latter three can be used for PDEs with $\Delta^2$. – lightxbulb Oct 21 '23 at 07:11
  • @PhilipRoe As far as Shannon-like sampling theorems go - I don't think those are very useful for FEM solutions of PDEs. The latter cares more about the smoothness of your solution space (that's why one typically studies error convergence in terms of the polynomial degree), while Shannon is concerned with when one can reproduce a continuous function exactly using a sinc interpolant, or trigonometric polynomials in the periodic case. So Shannon-like stories may be useful in FEM analysis if you e.g. use trigonometric polynomials for your finite-dimensional subspace. – lightxbulb Oct 21 '23 at 07:19
  • @lightxbulb Thank you for these remarks. You are speaking largely from the viewpoint of second-order PDEs. I prefer first-order PDEs as more descriptive of the physics. Currently people are looking at high-order FD and FE methods that are very accurate at low frequencies. In practice, breakdown occurs at high frequencies and I think that Hermite methods may have some advantage there. I am looking at the model advection problem $\partial_tu+a\partial_xu=0$ by interpolating in a Hermite spline that incorporates p derivatives. I have used MAPLE to find the dispersion relationship. – Philip Roe Oct 21 '23 at 19:32
  • @PhilipRoe Transport equations are trickier I agree. In FDM they require upwinding/downwinding schemes. I haven't tackled those in an FEM setting, but at least in 1D with linear Lagrange elements on a regular grid it should result in essentially the same thing as for FDM if you implement it correctly. It's just about in which direction you discretise $\partial_x$ so that it can actually "see" what must be propagated. I don't think that Hermite elements should change much w.r.t. the above logic - you'll just have more degrees of freedom. – lightxbulb Oct 21 '23 at 19:45
  • @lightxbulb I have to solve a polynomial of order p+1. For p=0,1,2,3 I find accuracy 2p+1. I can choose roots of the polynomial that collectively provide plausible behavior up to frequencies $(p+1)\pi$, but my gut tells me that this is too good to be true. I was very interested in the Papoulis result, which I was not aware of, and gives theoretical support to my tentative findings.

    My student already has some remarkable results with simplex elements in 2D, and is planning 3D, but I feel a need to also find better foundations in 1D

     – Philip Roe Oct 21 '23 at 19:56
  • Let us continue this discussion in chat. – Philip Roe Oct 21 '23 at 19:57