5
$\begingroup$

I would like to maximize $$ \int_0^{2\pi} \frac{(f'(x))^2}{f(x)}dx $$ subject to $f(x)\leq 1$ for all $x$ over the space of nonnegative trigonometric polynomials of degree smaller or equal to $n$.

The application would be to design a (theoretically) optimal 1d-image for position tracking via template matching.

Here is short explanation why the maximum of this interval gives the (theoretical) optimal image. The values of $f$ correspond to the intensity of the image, this is why it must be positive. The image is assumed to be periodic for simplification and because of practical reasons. The optics acts as a low-pass filter cutting of completely all frequencies above some threshold. Hence the image will be a trigonometric polynomial. With one measurement at $x$ we can determine the position with an std of $\sigma /f'(x)$. If the noise is dominated by shot noise we will have $\sigma=\sqrt{f(x)}$. The variance therefore is $f(x)/(f'(x))^2$. Combining a series of independent measurement at positions $x_1, \dots, x_n$ with corresponding weights $w_1, \dots, w_n$ with $\sum_{i=1}^n w_i=1$ the variance of the estimated position becomes $$ \sum_i w^2_i \frac{f(x_i)}{(f'(x_i))^2}\geq \frac{\left(\sum_i w_i \right)^2}{\left(\sum_i \frac{(f'(x_i))^2}{f(x_i)},\right)}=\left(\sum_i \frac{(f'(x_i))^2}{f(x_i)}\right)^{-1} $$ where we used Cauchy-Schwarz. Hence in order to minimize the variance/std we need to maximize $\sum_i \frac{(f'(x_i))^2}{f(x_i)}$. In the limit this becomes the integral.

As an extension it would also be interesting to solve a similar problem in two-dimensions where we need to track position (2dof's) and rotation (1 dof). I will think about a problem formulation in this case.

$\endgroup$
  • 2
    $\begingroup$ Trigonometric polynomial $f(x)=1$ gives you the minimum. $\endgroup$ – Alexandre Eremenko May 6 at 12:13
  • $\begingroup$ Did you try it for some small values of $n$? $\endgroup$ – Daniel McLaury May 6 at 12:59
  • $\begingroup$ Intuitively, I would try $f(x)=\frac12 (\sin(nx)+1)$. $\endgroup$ – Jean Duchon May 6 at 14:45
  • $\begingroup$ For $n=1$, W.L.O.G. $f(x)=c+(1-c)\sin(x)$ with $c\geq \frac{1}{2},$ $\int_0^{2\pi}\frac{(f'(x))^2}{f(x)} =\int_0^{2\pi}(1-c)^2\cos^2(x)c^{-1} \left(1-\frac{1-c}{c}\sin(x)+\left(\frac{1-c}{c}\right)^2\sin^2(x)-\dots \right) =(1-c)^2c^{-1}\sum_{k=0}^\infty\left(\frac{1-c}{c}\right)^{2k} \int_0^{2\pi} cos^2(x)\sin^{2k}(x)$ which is maximal for $c=\frac{1}{2}$, i.e. Jean's proposal is optimal in the case $n=1$. $\endgroup$ – user100927 May 7 at 6:47
  • $\begingroup$ nice question. can you explain why maximizing this integral gives optimal position tracking? or point to a reference? $\endgroup$ – kodlu May 11 at 0:24
5
$\begingroup$

$f(x)=\frac 12(1+\sin nx)$ is, indeed, the optimal choice. To see it, let's normalize a bit differently by $0\le f\le 2$. Then $f=1+g$ where $g$ is a real trigonometric polynomial of degree $n$ bounded by $1$. We need the following classical

Lemma. $g^2+n^{-2}(g')^2\le 1$

(I learned it from Alexandre Eremenko when we were discussing another MO question).

Assume the lemma. Then $g$ has at most $2n$ intervals of monotonicity. Let $I$ be one such interval on which $g$ changes between $a$ and $b$, say. Then $$ \int_I \frac{g'(x)^2}{1+g(x)}\,dx=\int_a^b \frac{|g'\circ g^{-1}(y)|}{1+y}\,dy\le n\int_a^b\frac{\sqrt{1-y^2}}{1+y}\le n\int_{-1}^1\frac{\sqrt{1-y^2}}{1+y} $$ and for $g=\sin nx$ we have equalities everywhere.

There are many proofs of the lemma, which is actually just Bernstein's inequality in disguise. I'll present one that derives it directly from the classical Bernstein inequality. Let $N>n$ be any real number. Consider the function $G=g^2+N^{-2}(g')^2$. At the point of maximum, we must have $(g+N^{-2}g'')g'=0$. If $g'=0$, we are done. Otherwise $g=-N^{-2}g''$ and, thereby, $G_1=N^{-2}((g')^2+N^{-2}(g'')^2)$ has a not smaller maximum. Continuing this way and recalling that, by the classical Bernstein inequality, $\max|g^{(m)}|\le n^m\max|g|=n^m$, we conclude that either we stop at some point and get $\max G_m\le (n^2N^{-2})^m\le 1$ because $g^{(m+1)}=0$ at the point of maximum of $G_m$, or go so far that $\max G_m\le (n^2N^{-2})^m+(n^2N^{-2})^{m+1}<1$ by the Bernstein bound and the observation that a decreasing geometric progression tends to $0$.

$\endgroup$
  • $\begingroup$ The reference for the Lemma is: R. Duffin and A. Schaeffer, Some inequalities concerning functions of exponential type. Bull. Amer. Math. Soc. 43 (1937), no. 8, 554–556, Theorem 2. $\endgroup$ – Alexandre Eremenko May 11 at 23:59

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.