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

Improve this question
$\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$
    – Iosif Pinelis
    Commented Dec 14, 2020 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
    Commented Dec 14, 2020 at 14:49

1 Answer 1

Reset to default
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$.

Improve this answer
$\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
    Commented Dec 15, 2020 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$
    – Iosif Pinelis
    Commented Dec 15, 2020 at 16:02
  • 1
    $\begingroup$ +1. Would you be so kind as to reveal how you discovered the counterexample? $\endgroup$
    – Hans
    Commented Sep 11, 2021 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$
    – Iosif Pinelis
    Commented Sep 12, 2021 at 1:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .