1
$\begingroup$

Let $f : [0,2\pi] \to \mathbb{R}$ be a continuous convex function on $(0,2\pi)$ which is singular about $0$ and $2\pi$ but finite when evaluated at the boundaries. Assume also that $f$ is symmetric about $\pi$. The discrete Fourier transform of $f$ when sampled at $2\pi i/N$ is then given by $$ X_n := \sum_{i=0}^{N-1}\cos\left(\frac{2\pi n i}{N}\right)f\left(\frac{2\pi i}{N}\right), \quad n = 1,\ldots,N-1. $$

Question: Given the convexity of $f$, does there exist a convex function $G : [0,1] \to \mathbb{R}$ such that $G(n/N) = X_n$? That is, when the DFT is plotted against $n = 1,\ldots,N-1$, does it agree with a convex function. Is the DFT a discrete convex function with respect to $n$?

$\endgroup$

1 Answer 1

2
$\begingroup$

The answer is no, there need not exist a convex function $G$ such that $X_n = G(n/N)$. For instance, let $N=6$ and $f(x)\equiv\lvert x-\pi\rvert$ (your condition that $f$ be singular near $0$ and $2\pi$ is inessential, since the summand for $i=0$ in the expression for $X_n$ does not depend on $n$, whereas the values of the other summands there do not depend on values of $f$ very near $0$ or $2\pi$.) Then $$X_n=\frac{1}{3} \pi \left(2 \cos \left(\frac{\pi n}{3}\right)+\cos \left(\frac{2 \pi n}{3}\right)+\cos \left(\frac{4 \pi n}{3}\right)+2 \cos \left(\frac{5 \pi n}{3}\right)+3\right),$$ which is not convex in $n$, as seen from this (connected) graph $\{(n,X_n)\colon n=1,\dotsc,5\}$:

Graph of (n, X_n) for n = 1, …, 5

More specifically, here $X_2=X_4=0$ and $X_3=\pi/3$, so that $X_3\not\le(X_2+X_4)/2$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer, that makes sense. Would you know what conditions of $f$ are necessary for the DFT output to be convex? $\endgroup$
    – spaceman
    Dec 11, 2020 at 17:04
  • $\begingroup$ @Orbital : I don't know such necessary conditions right away. I think it would be better in more ways than one to ask such additional questions in separate posts. $\endgroup$ Dec 11, 2020 at 17:28
  • $\begingroup$ Thank you for your help though, much appreciated. I shall ask an additional question. $\endgroup$
    – spaceman
    Dec 14, 2020 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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