# The maximum of a real trigonometric polynomial

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?

-
wa always have:$f(x)<=|a_0|+|a_1|+...+|a_N|+|b_1|+...|b_N|$ – Hashem sazegar Aug 13 '10 at 21:05
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$. – Vincenzo Aug 13 '10 at 23:13

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.

-
See also A. Nemirovski's lecture notes on convex programming www2.isye.gatech.edu/~nemirovs/Lect_ModConvOpt.pdf (section 3.2, examples 21a-21c) for a more elementary exposition. – Vincenzo Aug 20 '10 at 19:01

This was just asked (modulo a minus sign):

Minimizing the modulus of a polynomial around a circle

-
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? – Yemon Choi Aug 13 '10 at 20:59
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. – J. M. Aug 13 '10 at 23:20
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. – Yemon Choi Aug 14 '10 at 4:53
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? – J. M. Aug 14 '10 at 5:55
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$. – Yemon Choi Aug 14 '10 at 6:01

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).

-
I had already appreciated that the solution for this problem had to be iterative in some way, but thanks for crystallizing the idea. :) – J. M. Aug 17 '10 at 1:53

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.

-
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. – Vincenzo Aug 20 '10 at 18:51