2
$\begingroup$

Given the coefficients $a_0,\ldots,a_N$, $b_1,\ldots,b_N$ of a real trigonometric polynomial:

$ f(x) = a_0 + \sum_{n=1}^N a_n \cos(nx) + \sum_{n=1}^N b_n \sin(nx) $

is there any efficient way to approximately determine $\max_{x \in R} f(x)$? If so, what is the accuracy versus efficiency tradeoff?

$\endgroup$
2
  • $\begingroup$ wa always have:$f(x)<=|a_0|+|a_1|+...+|a_N|+|b_1|+...|b_N|$ $\endgroup$ Aug 13 '10 at 21:05
  • $\begingroup$ That is only a crude upper bound. I was asking for a two-sided estimate such as $F \le \max_x f(x) \le (1+\epsilon) F$, or $F \le \max_x f(x) \le F+\epsilon$, for some arbitrary $\epsilon>0$. $\endgroup$
    – Vincenzo
    Aug 13 '10 at 23:13
5
$\begingroup$

It turns out that it is possible to achieve an arbitrarily small additive error using semidefinite programming. This is from the paper:

J.W. McLean, H.J. Woerdeman. Spectral factorizations and sums of squares representations via semidefinite programming. SIAM J. Matrix Anal. Appl., 23(3):646--655, 2001. (link)

The result can be rephrased as follows. Let $f(x)=F(e^{ix})$ where $F(z)= \sum_{n=-N}^N c_n z^n$, with $c_n=\frac{1}{2}(a_n-i\ b_n)$ and $c_{-n}=\bar{c}_n$. Then $\min_x f(x)$ is equal to $c_0$ minus the value of the following semidefinite program: $ min_F\ tr(F) $ such that $F \succeq 0$, and $\sum_{p=k}^N F_{p,p-k} = c_k$ for $k=1,\ldots,N$.

Since semidefinite programming can achieve an arbitrarily small additive error, we can approximate the minimum (and thus, the maximum) of $f$ within the same bound.

$\endgroup$
1
2
$\begingroup$

This was just asked (modulo a minus sign):

Minimizing the modulus of a polynomial around a circle

$\endgroup$
5
  • $\begingroup$ I don't follow your comment. How does knowing how to find the minimum of the modulus of a polynomial help you to find the maximum modulus of a possibly (different) polynomial? $\endgroup$
    – Yemon Choi
    Aug 13 '10 at 20:59
  • $\begingroup$ No Yemon, he's right; $|p(\rho\exp(i\theta))|^2$ is a trigonometric polynomial; one's minimization of an objective function f can be another's maximization of -f. $\endgroup$ Aug 13 '10 at 23:20
  • $\begingroup$ I deleted an ill-thought out comment. But, in view of the question and answer which John refers to above, is Fejer-Riesz really a good way of calculating/estimating the max. modulus of a real trig. polynomial in terms of its coefficients? Given the well-known problems in comparing the "Wiener algebra" norm with the "disc algebra" norm, this would surprise me slightly, though as I've not given it much thought I perhaps shouldn't be so surprised. $\endgroup$
    – Yemon Choi
    Aug 14 '10 at 4:53
  • $\begingroup$ I don't really know either how much of something practical can I get out of Fejer-Riesz (I've only spent a few hours poring over the paper John pointed me to), but Yemon, you might have something else in mind? $\endgroup$ Aug 14 '10 at 5:55
  • $\begingroup$ Not at the moment, I'm afraid, and I'm away from the relevant books right now where I might try to look things up. Parseval's formula will give a lower bound of the maximum modulus in terms of some $\ell^2$-combination of the coefficients; and the triangle inequality gives an upper bound for the modulus in terms of the moduli of the coefficients; but beyond that I'm not aware of any other bounds which don't use auxiliary information about the function $f$. $\endgroup$
    – Yemon Choi
    Aug 14 '10 at 6:01
2
$\begingroup$

Even in the special case where $f(x) \geq 0$ for all $x$, there can't be any simple answer involving the coefficients $(a_n)$, $(b_n)$. You're basically asking to estimate the $L^\infty$ norm of a trigonometric polynomial in terms of the Fourier coefficients, and it's well known that this can't be done in any good way (more generally, the relation between the $L^p$ norm and the coefficients is horribly intractable, for any $p \ne 2$).

EDIT: I suppose it depends what you mean by a "good" way to approximate; this is a bit subjective, but I think "for any reasonable purpose" (any general-purpose programme you would actually run on a computer) no simple theoretical formula exists (which is guaranteed to have good error bounds).

However, if you want a numerical scheme to approximate a specific polynomial, that's a totally different question! You need a good numerical analyst (which I am not, sorry).

$\endgroup$
1
  • $\begingroup$ I had already appreciated that the solution for this problem had to be iterative in some way, but thanks for crystallizing the idea. :) $\endgroup$ Aug 17 '10 at 1:53
1
$\begingroup$

With credits to J.J. Green, I found this paper on finding the maximum modulus of a polynomial on the disk; it might be of help in this case.

$\endgroup$
1
  • $\begingroup$ Thanks. I had also found the paper through the other post. However I was looking for an algorithm with a provable worst-case running time for any arbitrarily small error. Semidefinite programming satisfies this requirement --you can solve a semidefinite program in time polynomial in the input size and log(1/eps) for any error eps-- while it is not clear to me that the algorithm in this paper can achieve that. $\endgroup$
    – Vincenzo
    Aug 20 '10 at 18:51
1
$\begingroup$

I stumbled upon this question and I think I have an interesting answer. I will make use of the FFT, please remark that in this argument I do not deal with the numerical error of the FFT but there are explicit error bounds on the FFT so they may be taken into account (you can find them in Higham, Accuracy and Stability...); moreover I will use the representation of Fourier Series with exponentials because it makes the argument easier.

I suppose we are on $[0,1]$ and I will work with the complex exponential basis. Let $\hat{f}(k)$ be the coefficients of the Fourier series with respect to the exponential basi. Since $f$ is a trigonometric polynomial there exists a $K$ such that $\hat{f}(k)=0$ for $k>K$.

We observe now that $\hat{f'}(k)=2\pi i k \hat{f}(k)$. Therefore,
$$||f'||_{\infty}\leq 2\pi K \sum_{-K}^K |\hat{f}(k)|. $$

We now run the inverse FFT of size M bigger than K on the $\hat{f}(k)$. The inverse Fast Fourier Transform using the Cooley-Tuckey algorithm is fast and numerically well behaved and gives us the value of the trigonometric polynomial at $M$ equispaced points, call them $x_1, \ldots, x_M$.

Then $$ \max_{i=1,\ldots, M} f(x_i)\leq \max f(x)\leq \max_{i=1,\ldots, M} f(x_i)+ 2\pi \frac{K}{M} \sum_{-K}^K |\hat{f}(k)|. $$

There are some normalizations involved in the FFT, but the argument should work.

$\endgroup$
1
  • $\begingroup$ If you're interested, this argument can be easily generalized to higher order $\endgroup$ Nov 2 '20 at 22:34
0
$\begingroup$

The basic approach could also be useful, and it should be compared with more advanced ones.

Note that $f$ is $2\pi$-periodic and Lipschitz of constant $L:= \sum_{n=1}^N n\sqrt{a_n^2+b_n^2}$ because for any $x\in\mathbb{R}$ $$|f'(x)|\le \sum_{n=1}^N n\big| a_n \sin(nx) - b_n \cos(nx)\big|\le \sum_{n=1}^N n\sqrt{a_n^2+b_n^2}. $$

Therefore for all positive integer $m$

$$0\le \max_{x\in\mathbb{R}}f(x)- \max_{1\le k\le m} f\big(\frac{2k\pi}m\big)\le \frac{\pi L}m.$$

$\endgroup$

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.