Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

4 Answers 4

up vote 3 down vote accepted

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.

share|improve this answer
    
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

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

share|improve this answer
    
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

This was just asked (modulo a minus sign):

Minimizing the modulus of a polynomial around a circle

share|improve this answer
    
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

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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