5
$\begingroup$

For a continuous signal (function), we have Bernstein inequality : $$ |{df(t)}/dt| \le 2AB\pi $$ where $A=\sup|f(t)|$ and $B$ is the bandwidth of $f(t)$. The question is: is there a relationship for a discrete function $x[n]$ like this? $$ |x[n] -x[n-1] | \le\ \mu\ W $$ where $$ X[k] = \sum\limits_{n = 0}^{N - 1} {x[n]{e^{ - j\frac{{2\pi }}{N}nk}}} $$ is the DFT for $x[n]$, $X[k]=0$ for $k> W$.

$\endgroup$
  • 1
    $\begingroup$ How do you define the bandwidth of $x[n]$? $\endgroup$ – AlexTP Oct 29 '18 at 18:17
  • 1
    $\begingroup$ I'm sitting – tired – in front of a paper; my understanding of the Bernstein ineq is: $$P(\omega)=\sum_{n=0}^N\left(a_k\cos(n \omega)+b_k\sin(n\omega)\right)$$ $$\max_{-\pi\le\omega < \pi} \left\lvert P'(\omega)\right\rvert\le \max_{-\pi\le\omega < \pi} \left\lvert P(\omega)\right\rvert $$ From that follows that continuous bandwidth would be $2N\omega$; assuming Nyquist-limiting $W < 2N\omega$. $\endgroup$ – Marcus Müller Oct 29 '18 at 18:35
  • $\begingroup$ @OlliNiemitalo edited $\endgroup$ – alwaystudent Oct 30 '18 at 8:06
  • 3
    $\begingroup$ If $A=\max |x[n]|$, then we simply have $|x[n]-x[n-1]|\le 2A$. So any formula involving the bandwidth should be tighter than that, if it's any good. $\endgroup$ – Matt L. Oct 30 '18 at 13:41
  • $\begingroup$ An alternative and not equivalent way to define $A$ is that it is the supremum of the absolute value of the band-limited continuous-time function the samples of which are $x[n].$ $\endgroup$ – Olli Niemitalo Oct 30 '18 at 14:02
3
$\begingroup$

As shown in the answers to this question, for continuous-time signals, the bound predicted by Bernstein's inequality is achieved with equality by a sinusoidal signal with a frequency equal to the upper frequency limit.

In analogy to this, in this answer I'll show a bound on $\big|x[n]-x[n-1]\big|$ for a discrete-time sinusoidal signal $x[n]$ at angular frequency $W$:

$$x[n]=A\sin(nW+\phi)\tag{1}$$

For the signal $x[n]$ given by $(1)$, the largest value of $\big|x[n]-x[n-1]\big|$ for all $n\in\mathbb{Z}$ occurs for two values $x[k]$ and $x[k-1]$ symmetrical to the point of the largest derivative of a (continuous) sinusoid, i.e., for $x[k]=A\sin(W/2)$ and $x[k-1]=A\sin(-W/2)$. Consequently, the bound for a sinusoid with frequency $W$ is given by

$$\big|x[n]-x[n-1]\big|\le 2A\sin\left(\frac{W}{2}\right)\tag{2}$$

This bound is achieved with equality for the signals

$$x[n]=A\sin\left(nW+\frac{(2l+1)W}{2}\right),\qquad l\in\mathbb{Z}\tag{3}$$

Note that the constant $A$ does not generally equal the maximum amplitude $B=\max |x[n]|$ of $x[n]$. Depending on the sampling phase, the maximum amplitude $B$ lies in the following interval:

$$A\cos\left(\frac{W}{2}\right)\le B\le A\tag{4}$$

Consequently, we have

$$A\le\frac{B}{\cos\left(\frac{W}{2}\right)},\qquad 0<W<\pi\tag{5}$$

Combining $(2)$ and $(5)$ we get

$$\big|x[n]-x[n-1]\big|\le 2B\tan\left(\frac{W}{2}\right),\qquad B=\max_n\big|x[n]\big|\tag{6}$$

Note, however, that $(6)$ is only useful for $\tan(W/2)<1$, i.e., for $W<\pi/2$ because for any $x[n]$ with $\max|x[n]|=B$ we must have

$$\big|x[n]-x[n-1]\big|\le 2B\tag{7}$$

I believe that the bound $(6)$ holds for all discrete-time band-limited signals with a maximum frequency $W$ (i.e., with $X(e^{j\omega})=0$ for $|\omega|\in (W,\pi]$), but I don't know how to show it.

$\endgroup$
  • $\begingroup$ Hi! What do you mean by discrete-time band-limited signals ? Are there non band-limited discrete-time signals as well ? $\endgroup$ – Fat32 Oct 31 '18 at 10:21
  • 1
    $\begingroup$ Consider $x[n] = \frac{2}{\sqrt{2}}\sin\left(\frac{\pi n}{2}+\frac{\pi}{4}\right) = [1, 1, -1, -1, 1, 1, -1, -1, \ldots].$ Eq. 2 gives $\left|x[n] - x[n-1]\right| \le \sqrt{2}A, $ which is correct if $A = \frac{2}{\sqrt{2}}$ (see my comment to the question) but incorrect if $A = \max|x[n]| = 1.$ $\endgroup$ – Olli Niemitalo Oct 31 '18 at 11:33
  • $\begingroup$ @OlliNiemitalo: Yes, I need to clarify the definition of $A$. $\endgroup$ – Matt L. Oct 31 '18 at 11:46
  • 1
    $\begingroup$ @OlliNiemitalo: Fixed, kind of ... $\endgroup$ – Matt L. Oct 31 '18 at 15:51
  • 2
    $\begingroup$ That can be a useful result. It may well be a tight bound in cases that band limit $W = \frac{\pi}{N},$ where $N$ is an integer, because then each extrema of a sinusoid of frequency $W$ can be located just between the samples. With other band limit values, things may get complicated and the "worst case" sinusoid may have a frequency lower than the band limit, or perhaps the worst case is not a sinusoid at all. $\endgroup$ – Olli Niemitalo Oct 31 '18 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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