2
$\begingroup$

Let $f : [0,2\pi] \to \mathbb{R}$ be some function. Then 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: What conditions are sufficient on $f$ such that there exists a convex function $G : [0,1] \to \mathbb{R}$ with $G(n/N) = X_n$? That is, when is the DFT a discrete convex function with respect to $n$?

  • In the references post above it was shown that $f(x) = |\pi-x|$ defies this claim.

Notes: This question is related to the recent post: Convexity of discrete Fourier transform

$\endgroup$
2
  • 1
    $\begingroup$ In view of the previous answer, the smoothness of $f$ will not be enough, because on any finite subset of $[0,2\pi]$ any given function coincides with a smooth function. Also, do you really want necessary (rather than sufficient) conditions on $f$? $\endgroup$ Dec 14 '20 at 14:05
  • $\begingroup$ @IosifPinelis Thank you, yes, I assume then, some condition on the second derivative would do the job. It seems possibly that the function $|\pi - x|$ flips too quickly at $\pi$ and a slower transition from $ f' < 0 $ to $ f' > 0 $ may be necessary. Also, right now, a sufficient condition would be interesting, I will update the question accordingly. $\endgroup$
    – spaceman
    Dec 14 '20 at 14:49
2
$\begingroup$

Here is an answer taking into account your comment:

Even if you assume that $f$ is a convex function symmetric about $\pi$ and having a convex second derivative, it is still not enough for there to exist a convex function $G\colon[0,1]\to\mathbb{R}$ with $G(n/N)=X_n$ for $n=1,\dots,N-1$.

For instance, let $$f(x):=\frac{(a-x)_+^3+(x-2\pi+a)_+^3}{(2\pi/N)^3}$$ for $x\in[0,2\pi]$, where $a\in\mathbb R$ and $u_+:=\max(0,u)$. Then $f$ is a convex function symmetric about $\pi$ and having a convex second derivative. However, if $N=10$, $a=2\pi l/N$, and $l=2$, then $$X_n=16 + 2\cos\frac{\pi n}5,$$ which is not convex in $n=1,\dots,10-1$, as seen from this (connected) graph $\{(n,X_n)\colon n=1,\dotsc,9\}$:

enter image description here

More specifically, here $X_2\not\le(X_1+X_3)/2$.

$\endgroup$
4
  • $\begingroup$ Excellent, this is very interesting. It seems that the convexity of $X_n$ is broken by $X_1$ and $X_N$, or terms nearby, possibly due to insufficient blow up of the function $f$ near $0$ and $2\pi$. You can see that if $f(x) = \begin{cases}\frac{1}{\sin(x/2)} & 0 < x < 2\pi \\ c & x = 0,2\pi \end{cases}$ for some constant $c\in\mathbb{R}$, then one obtains that the DFT is convex. I am wondering what would be sufficient for a general $f$ to have a convex DFT. $\endgroup$
    – spaceman
    Dec 15 '20 at 9:27
  • 2
    $\begingroup$ @Orbital : I think you would likely get more informative answers if you could tell us what kind of functions $f$ are of interest to you, rather than going backwards. BTW, as explained in my previous answer, no blowup conditions for $f$ near $0$ and $2\pi$ can suffice by themselves. $\endgroup$ Dec 15 '20 at 16:02
  • 1
    $\begingroup$ +1. Would you be so kind as to reveal how you discovered the counterexample? $\endgroup$
    – Hans
    Sep 11 at 0:18
  • 1
    $\begingroup$ @Hans : One can see that any smooth convex function symmetric about $\pi$ and having a convex second derivative is a mixture of the constant function $1$, the function $u\mapsto(u-\pi)^2$, and functions $f$ as in the first display in the answer; cf. e.g. formula (3.2) in projecteuclid.org/journals/annals-of-statistics/volume-22/… $\endgroup$ Sep 12 at 1:10

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.