This is a cross-post from signal processing forum as it was not conclusive. Let $x[n]$ be a finite-length sequence with length $N$. The continuous DTFT $X(\omega)$ is then $$ X(\omega) = \sum_{n = 0}^{N-1} x[n] e^{-j \omega n}. $$

The length-$N$ DFT of $x[n]$ is $$ X[k] = \sum_{n = 0}^{N-1} x[n] e^{-j 2 \pi \frac{k n}{N}}. $$ For this, the DFT is a sampled version of the DTFT, i.e., $$ X[k] = X(2\pi k / N). $$ Please also see posts here and here. Now, we consider the maximum magnitudes $m_{\textrm{d}} = \max_k |X[k]|$ and $m_{\textrm{c}} = \max_\omega |X(\omega)|$. Because of above, we have $m_{\textrm{d}} \leq m_{\textrm{c}}$.

How much does $m_{\textrm{d}}$ underestimate $m_{\textrm{c}}$? Is there $\gamma > 1$ such that $\gamma m_{\textrm{d}} \geq m_{\textrm{c}}$?

  • WLOG scale so that the norm is 1, and then we have the inequalities $1/\sqrt{N}\le m_d\le m_c \le 1$. So at the least you can take $\gamma=\sqrt{N}$. Since at each of the inequalities we must have $m_c=m_d$, I'm guessing there's a much better bound... – Dror Speiser Oct 4 at 21:06
  • @DrorSpeiser thanks for the first bound. I also believe that there must be a much better bound as this would be highly impracticable for signal analysis purposes. – Sebastian Schlecht Oct 5 at 8:28
  • I find this question to be interesting, though the subject matter is not my field of expertise. But I do have two things to report on, both from Montgomery's paper An Exponential Polynomial Formed with the Lagrange Symbol: 1. the Fekete polynomials give a lower bound $\gamma>2\log\log n/\pi$, so there's no uniform constant $\gamma$. 2. as Montgomery writes, Bernstein's inequality give a bound in terms of "a higher sampling rate", i.e. the polynomial evaluated at roots of unity of higher order. He doesn't prove the bound in the paper, but I think it works for all real polynomials. – Dror Speiser Oct 6 at 12:08

I believe to have found a partial answer in the paper:

Gronwall, T. H. (1921). A sequence of polynomials connected with the $n$th roots of unity. Bulletin of the American Mathematical Society, 27(6), 275–279. http://doi.org/10.1090/S0002-9904-1921-03411-2

It actually gives a full construction of a polynomial $F(z)$ such that $|F(e^{i2\pi k/N})| \leq 1$, but $\max |F(z)| = \frac{1}{N} \sum_{n=0}^{N-1} \frac{1}{\sin \frac{2n + 1}{2N}\pi}$.

This makes the upper bound $\gamma$ in the original question to be asymptotically equal to

$$ \frac{2}{\pi}\left( \log N + C + \log \frac{2}{\pi} \right) + o(1), $$
where $C$ is the Euler's constant, and $o(1)$ tends to zero as $N$ increases indefinitely. There are various follow up questions:

  1. $F(z)$ has complex coefficients. What is the bound for real coefficients?
  2. How does this bound change if we add zero padding? It will tend to 1, but how quickly?
  3. $F(z)$ gives the worst case bound, but how is this bound for random (Gaussian) distributed coefficients?
  • Nice! I find it remarkable that, though the question is intended for signal processing purposes, Gronwall was tightening a bound of Landau that was used to study a number theory problem, namely about what are now called Fekete polynomials, that come up while studying class numbers of quadratic fields. (See reference in loc. cit.) – Dror Speiser Oct 15 at 23:54

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.