Lange Nacht der Forschung

As PhD Candidates in Mathematics at the University of Vienna, Beatrice Andreolli, Steffen Plunder, Michael Fischer, Hannah Götsch and I took part in the Lange Nacht der Forschung (Long Night of Science). It was a fantastic experience to participate in a nation-wide event dedicated to making science more approachable to everyone and highlighting its importance for modern life.

We each presented our current work at various levels, starting with games for the youngest to detailed explanations for the hobby-mathematicians.

Gabor frame bound optimizations

We consider Gabor systems on rectangular lattices generated by a function g\in L^2(\mathbb{R}) and lattice parameters a,b>0:

\mathcal{G}(g, a\mathbb{Z}\times b \mathbb{Z}): = \lbrace M_{bl}\,T_{ak} g\mid k,l\in\mathbb{Z}\rbrace.

Here the time-frequency shift M_\omega\,T_x is an operator acting on fuctions as

M_\omega\,T_x\, f(t) = e^{2\pi i \omega\cdot t}\, f(t-x).

A Gabor system is a frame if and only if there are constants 0<A\leq B<\infty satisfying

A\, \lvert\lvert f \rvert\rvert_{{}_2}^{{}^2} \leq \sum\limits_{l,k\in\mathbb{Z}} \big\lvert \langle f, M_{bl} T_{ak} g\rangle\big\rvert^{{}^2} \leq B\,\lvert\lvert f \rvert\rvert_{{}_2}^{{}^2} \qquad \forall f\in  L^2(\mathbb{R}).

We call A,\, B lower and upper frame bound, respectively. The supremum over all such A is also a lower frame bound, referred to as the optimal lower frame bound. Similarly, the infimum over all upper frame bounds is an upper bound – the optimal lower frame bound. In the following, A,\,B always the denote the optimal frame bounds.

The existence of the frame bounds is equivalent to the stability of the reconstruction of f from the samples \langle f, M_{bl} T_{ak} g\rangle, i.e., the frame operator

S: L^2(\mathbb{R})\longrightarrow \ell^2(\mathbb{Z}\times\mathbb{Z}),\quad f \mapsto \sum\limits_{l,k\in\mathbb{Z}} \langle f, M_{bl} T_{ak} g\rangle\, M_{bl} T_{ak} g

is a bounded bijective operator with a bounded inverse. Moreover, the associated operator norms give the optimal frame bounds.

The volume of the fundamental domain a[0,1]\times b[0,1] is called the volume of the lattice, vol(a\mathbb{Z}\times b\mathbb{Z}) = ab, whereas the density of the lattice is \delta = (ab)^{-1}.

Optimization problem

Given a window function g\in L^2(\mathbb{R}) and density \delta  = n\in\mathbb{N}, determine the pairs (a,b) such that

  1. (ab)^{-1} = n;
  2. \mathcal{G}(g, a\mathbb{Z}\times b\mathbb{Z}) is a frame;
  3. (a,b) is optimal under all pairs (\widetilde{a},\widetilde{b}) which satisfy (a) and (b). Optimality is considered in three versions, namely, with respect to
    • the lower frame bound A;
    • the upper frame bound B;
    • the condition number \kappa= \frac{B}{A}.

The first condition turns the problem into a univariate optimization problem, where we are free to choose the parametarization. For instance, one option is to use (a,\frac{1}{na}), which explains the optimality with respect to time. Another possibility is (\frac{\eta}{n},\frac{1}{\eta}), which reflects the symmetry of the parameters a,\,b with respect to \sqrt{\delta}. In this case, the square lattice corresponds to \eta = \sqrt{n}.

Problems

  1. What is the set of admissible parameters (a,b)?
  2. Are there closed forms for A and B with respect to the lattice parameters?
  3. Is there an optimizer? If yes, is it unique?
  4. Do the optimizers of A, \,B and \kappa coincide?

The investigated functions are the hyperbolic secant, cut-off exponentials, one-sided and two-sided exponentials. For these functions, the first two problems were already resolved satisfactorily in [1]. The rest of the questions were answered in [2].

Parameter transformations and dilations

By the symplectic invariance of Gabor frames, a Gabor system \mathcal{G}(g, a\mathbb{Z}\times b \mathbb{Z}) is a frame if and only if \mathcal{G}(D_\gamma g, a\mathbb{Z}\times b \mathbb{Z}) is a frame, with same bounds. In particular, dilations D_\gamma f(t) = \gamma^{1/2} f\left(\gamma t\right) as metaplectic operators correspond to dilation matrices

\begin{pmatrix} \gamma^{-1} & 0 \\ 0 & \gamma\end{pmatrix},

so the pair (a,b) is optimal (in any of the optimality versions) for fixed g and n if and only if (\gamma^{-1}\, a, \gamma\, b) is optimal for D_\gamma\, g and n. In the following we will mostly set additional function parameters to 1, since we can recover the optimal frames through dilations, anyway.

Coinciding optimizers

If A and B are continuously differentiable and have unique critical points t_A and t_B, then this already implies something for the condition number.

  • If A tends to 0 or B Is unbounded, then \kappa has an optimizer. Hence, we only look at the critical points.
  • 0 = \frac{\partial}{\partial t}\left( \frac{A}{B} \right)= B^{-2}\cdot\left(A^\prime\,B -A\,B^\prime\right), or equivalently,

\frac{A^\prime}{A} = \frac{B^\prime}{B}.

  • The frame bounds are not negative. But this means that the sign of A^\prime and B^\prime is the same at the critical points. Why is this interesting? This simply tells us that the minimum is attained at some t_\kappa is between t_A and t_B. This is a trivial observation if t_A = t_B, but otherwise, t_\kappa is strictly between t_A and t_B!

Determining the optimal frame bounds

Janssen’s representation of the frame operator reads

Sf = (ab)^{-1}\sum\limits_{l,k\in\mathbb{Z}} \langle g, M_{l/a} T_{k/b} g\rangle\, M_{l/a} T_{k/b} f,

expressing explicitly the dependence on the shifts of f. This already motivated the first examples, where the sum is reduced to one and three time-shifts, respectively.


Cut-off exponentials

By cut-off exponentials we mean g_{\gamma}(t)=C_{1/\sigma, \gamma}\, e^{-\gamma t}\,\chi_{[0, \sigma]} where C_{1/\sigma,\gamma} is a normalizing constant. In order to simplify Jannsen’s representation, we can consider the cut-offs \sigma = 1/b and \sigma = 2/b. Yet, the slight support change results in completely different situations. Letting \gamma\to 0, we get the well-known box function, whereas the degenerate b\to 0 corresponds to the one-sided exponential explored below.

Support 1/b

The frame bounds are

A = n \, \frac{2 \gamma a}{1 - e^{-2 \gamma a}} \, e^{- 2 \gamma a}, \qquad B = n \, \frac{2 \gamma a}{1 - e^{-2 \gamma a}},

resulting in the condition number \kappa = e^{2\gamma a}. Notice that all expressions depend on the product \gamma \, a, so we can optimise interchangeably, by fixing one or the other. Either way, there is no optimal lattice.

The left plot shows the lower bound (red), the upper bound (blue) and the condition number (purple). There is clearly no optimal lattice for any of the optimization problems.

Support 2/b

In this case, the frame operator (in Janssen’s representation) depends on three shifts and everything changes.

A = \frac{2 \gamma a (1-e^{-2\gamma n a})(1-e^{-\gamma n a})^2}{(1-e^{-2 \gamma a})(1-e^{-4\gamma n a})} \, e^{-2 a \gamma}

B = \frac{2 \gamma a (1-e^{-2\gamma n a})(1+e^{-\gamma n a})^2}{(1-e^{-2 \gamma a}) (1- e^{-4\gamma n a})}.

This time, the limiting cases do not result in frames. Notice that the optimality depends on the product \gamma\, a, again. Optimizers exists, but the uniqueness is an issue. The lower frame bound has a unique global maximum. It is attained at the unique positive solution of the equation
-1 + \frac{1}{\gamma a}- \mathrm{coth}(\gamma a) = n \, \mathrm{coth}\left( \frac{\gamma n a}{2}\right) \mathrm{sech}(\gamma n a).

The graph shows lower frame bound depending on the lattice parameter a.

The upper frame bound is strictly monotonically increasing when n=1 or n=2. For all other n\geq 3, B has a local maximum and a local minimum, which may or may not be global. If its value at the local minimum is strictly less than 2, then it is a unique minimizer.

The graph shows upper frame bound depending on the lattice parameter a.


The hyperbolic secant

The (scaled) hyperbolic secant g_\gamma(t) =\mathrm{ sech}(\gamma \pi t) = \frac{1}{\cosh(\gamma\pi t)} = \frac{2}{e^{\gamma\pi t}+e^{-\gamma\pi t}} is a totally positive function in Feichtiger’s algebra, so the lower frame bound vanishes at the critical density n=1. For all higher integer densities n\in\mathbb{N}_{\geq 2}, all pairs (\frac{\eta}{n}, \frac{1}{\eta}) are admissible, i.e., we are optimizing over (0,\infty). From now on, we only investigate for \gamma =1 (see above for the general solution). The optimal frame bounds are given by

A(\eta) = n\pi\sum\limits_{k=0}^{\infty} \frac{\eta}{n}\, \mathrm{ sech}(\pi(k+\frac{1}{2})\frac{\eta}{n})^2 +n\pi \sum\limits_{k=0}^{\infty} \frac{1}{\eta}\,\mathrm{ sech}(\pi(k+\frac{1}{2})\frac{1}{\eta})^2 - n = n\pi f_A(\frac{\eta}{n}) +n\pi f_A(\frac{1}{\eta})-n

and

B(\eta) = n\pi\sum\limits_{k=0}^{\infty} \frac{\eta}{n}\, \mathrm{ csch}(\pi(k+\frac{1}{2})\frac{\eta}{n})^2 +n\pi \sum\limits_{k=0}^{\infty} \frac{1}{\eta}\,\mathrm{ csch}(\pi(k+\frac{1}{2})\frac{1}{\eta})^2 + n = n\pi f_B(\frac{\eta}{n}) +n\pi f_B(\frac{1}{\eta})-n

where

f_A(t) = t\sum\limits_{k=0}^{\infty} \,\mathrm{ sech}(\pi(k+\frac{1}{2}))^2\qquad\text{and}\qquad f_B(t) = t\sum\limits_{k=0}^{\infty} \,\mathrm{ csch}(\pi(k+\frac{1}{2}))^2.

The left plot shows the lower bound (red), the upper bound (blue) and the condition number (purple) with their extremal points. The right plot shows their logarithmic counterparts.

Key observations:

  • the series converge locally uniformly, hence, are uniformly differentiable;
  • \lim\limits_{\eta\rightarrow 0}A(\eta) = \lim\limits_{\eta\rightarrow \infty}A(\eta) = 0;
  • \lim\limits_{\eta\rightarrow 0}B(\eta) = \lim\limits_{\eta\rightarrow \infty}B(\eta) = \infty.

Therefore, optimal points with respect to A,\, B,\,\kappa exist. All that is left to do is to determine the critical points and compare the values. It would be quite easy if there is only one critical point, then no comparison is needed 😊

For both bounds, we are solving

0 = \frac{1}{n}f_{\star}'(\frac{\eta}{n}) - \frac{1}{\eta^2}f_{\star}'(\frac{1}{\eta}) = \frac{1}{\eta}\left(\frac{\eta}{n}f_{\star}'(\frac{\eta}{n}) - \frac{1}{\eta}f_{\star}'(\frac{1}{\eta}) \right).

The next goal is to determine all pairs (x,y)\in (0,\infty)^2 which solve x\cdot f_*'(x) =y f_*'(y).

The lower bound

Since the lower bound vanishes for all (\eta,\frac{1}{\eta}), the pairs (x,x),\,(x,\frac{1}{x}) definitely solve the problem. By examining the derivatives of h_A(t) = t\cdot f_A'(t), we showed that there are no further solutions.

Hence, the only critical points are the solutions of \frac{\eta}{n} = \frac{1}{\eta} and \frac{\eta}{n} = \eta. The second one has no solution when n\geq 2, so we are indeed left with only one critical point, \eta=\sqrt{n}! This means that the square lattice is the best one for the lower bound for any fixed integer density.

The above plots show h_A(t)= t\cdot f_A'(t) (top plot) and h_B(t) = t\cdot f_B'(t) plot (bottom plot). The evaluations are at the points x_0 and x_0^{-1} for h_A and x_0 for h_B.

The upper bound

Clearly, (x,x) is a solution. We showed that the objective function h_B(t)=t\cdot f_B'(t) is strictly monotonically increasing, so again, a critical point of the upper bound B has to satisfy \frac{\eta}{n} = \frac{1}{\eta} , i.e., the square lattice is again the optimal one.

Condition number

When the same lattice maximizes the lower and minimizes the upper bound, this is also the unique optimizer of the condition number.


One-sided exponentials

The limiting case of the cut-off exponentials is the one-sided exponential g(t) = C_\gamma e^{-\gamma t}\chi_{[0,\infty}. Due to the dilation invariance, we look at the bounds when \gamma =1. The parameterization of the lattice parameters is (\frac{\eta}{n}, \frac{1}{\eta}), since we initially expected something symmetric.

A(\eta) = 2\eta \, \tanh(\tfrac{\eta}{2})\, \mathrm{csch}( \tfrac{\eta}{n}) \, e^{- \tfrac{\eta}{n}},

B(\eta) = 2\eta \, \coth(\tfrac{\eta}{2})\, \mathrm{csch}( \tfrac{\eta}{n}) \, e^{ \tfrac{\eta}{n}}.

We first look at the condition number:

\kappa(\eta) = \Big( \coth(\tfrac{\eta}{2})\,    e^{ \tfrac{\eta}{n}}\Big)^2.

The left plot shows the lower bound (red), the upper bound (blue) and the condition number (purple) with their extremal points. If the optimizers coincided, the angle would have been 90^\circ.

The unique minimizer is the point \eta_{\kappa} = \mathrm{arcsinh}(n). A not too exhaustive analysis would show that both bounds have unique optimal points, as the critical points are unique and the behaviour in the limiting cases \eta\to 0 and \eta\to \infty guarantees an optimizer. That is not to say that this is \eta_A =\eta_B = \eta_\kappa= \mathrm{arcsinh}(n). Indeed,

\tfrac{\partial}{\partial \eta}\ A(\eta) {\arrowvert}_{\eta = \eta_\kappa }= e^{-\frac{\eta}{n}}\mathrm{csch}(\tfrac{\eta}{n}) \mathrm{tanh}(\tfrac{\eta}{2})\Big( 1+\eta\,\mathrm{csch}(\eta)-\tfrac{\eta}{n}-\tfrac{\eta}{n}\mathrm{coth}(\tfrac{\eta}{n}) \Big){\arrowvert}_{\eta = \eta_\kappa }  =e^{-\frac{\eta_\kappa}{n}}\mathrm{csch}(\tfrac{\eta_\kappa}{n}) \mathrm{tanh}(\tfrac{\eta_\kappa}{2})\Big( 1+\eta_\kappa\cdot\tfrac{1}{n}-\tfrac{\eta_\kappa}{n}-\tfrac{\eta}{n}\mathrm{coth}(\tfrac{\eta_\kappa}{n}) \Big)

=e^{-\frac{\eta_\kappa}{n}}\mathrm{csch}(\tfrac{\eta_\kappa}{n}) \mathrm{tanh}(\tfrac{\eta_\kappa}{2})\Big( 1-\tfrac{\eta}{n}\mathrm{coth}(\tfrac{\eta_\kappa}{n}) \Big)<0.

If the lower bound is first strictly monotonically increasing, then strictly monotonically decreasing, its maximum has to be less than \eta_\kappa>\eta_A. Similarly, \eta_\kappa <\eta_B by evaluating. Or, we recall what we know about coinciding optimizers.


Two-sided exponentials

We finish with the two-sided exponential g(t) = C_\gamma e^{-\lvert t\rvert} (here: \gamma = 1). This is a totally positive function of type 2, so it belongs to Feichtinger’s algebra and cannot admit a frame at the critical density. For all other integer densities, all pairs are admissable and the frame bounds are given by

 A(\eta) = A(\tfrac{\eta}{n},\tfrac{1}{\eta}) = \tanh(\tfrac{\eta}{2})\Big( \tfrac{\eta}{n}\,\mathrm{csch}(\tfrac{\eta}{n})- \eta \, \mathrm{csch}(\eta)\Big) ,

B(\eta)=B (\tfrac{\eta}{n},\tfrac{1}{\eta})  = \coth(\tfrac{\eta}{2})\Big(\tfrac{\eta}{n}\, \coth(\tfrac{\eta}{n})+\eta\,\mathrm{csch}(\eta)\Big).

Simple enough, right? Besides, we had already dealt with similar products with the other windows. Yet, there seems to be something intricately problematic here.

The left plot shows (scaled) the lower bound (red), the upper bound (blue) and the condition number (purple) with their extremal points. As in the one-sided case, If the optimizers coincided, the angle would have been 90^\circ.

Looking at the graphs, one could almost claim the existence of a unique optimizer will be easy to show. However, this one has proven to be the most challenging of all windows. Our analysis indicated that the visual ”obviousness” is due to a very particular balance of the factors of the bounds. A good global estimate is not possible, because each factor has a varying contribution on different intervals, with high dependancy on the lattice density n. Numerical tests hint that the position of the optimizers should be different for each object function A,\, B,\, \kappa and grows logarithmically in n. This motivated the following approach:

  1. Pick a reference point \eta_n: we chose \eta_n = 2\mathrm{arctanh}(n), which worked well with the first factor.
  2. Left cut-off: Compare the exact value of the bound, say A(\eta_n) with a rough estimate for points \eta\leq \frac{\eta_n}{2}:

A({\eta}) <n\, \tanh({\eta_n}/{4})\,\big(1-f({\eta_n}/{2})\big) \overset{?}{<} A(\eta_n).

The first inequality is due to the monotonicity of \tanh and x\cdot\mathrm{csch}(x). To confirm the inequality, one should begin with addition theorems and take it from there.

  1. Right cut-off: Do the same for points \eta\geq 2\eta_n:

A_1({\eta}) <n \cdot \big( \tfrac{2\eta_n}{n} \mathrm{csch}(\tfrac{2\eta_n}{n}) - 0\big)\overset{?}{<}A(\eta_n) .

To sum up, this shows that

  • there is a maximum of A;
  • it has to be in \big[\frac{\eta_n}{2}, 2\eta_n\big].
  1. Show that the bound is strictly logarithmically concave.

Why logarithmically concave? We expect it to be concave. However, the logarithm is a nice thing to have if we are considering the second and higher derivatives of a product of three functions 😄
Also, we need to keep the end goal in mind: we want a unique maximum. Strict concavity is a typical way to argue this in a homework assignment, but the logarithm is a strictly monotonic function, so it would preserve the position of the optimizers.

\ln \big(n^{-1}\,A(\eta)\big) = \ln(\tanh (\frac{\eta}{2})) + \ln\Big( \tfrac{\eta}{n}\,\mathrm{csch}(\tfrac{\eta}{n})- \eta \, \mathrm{csch}(\eta)\Big).

We keep in mind that

  • (Strictly) concave functions are (strictly) logarithmically concave;
  • \tanh is strictly concave;
  • if \tfrac{\eta}{n}\,\mathrm{csch}(\tfrac{\eta}{n})- \eta \, \mathrm{csch}(\eta) is concave, then A is strictly logarithmically concave (on the remaining interval, not everywhere). This is the new task.
  1. Show that B strictly convex and unbounded.
  2. Do the cut-off for B.

At this point, I would like to assure you that we are not overdoing it with the cut-off comparisons. Without it, we run into trouble with the condition number \kappa. This one is the hardest to understand and we would like to only analyse it on the small interval. We can cut-off everything which is not between the optimizers \eta_A and \eta_B. Only then can we focus on the behaviour of \kappa on \big[\frac{\eta_n}{2}, 2\eta_n\big].

  1. Show the logarithmic concavity of \frac{1}{\kappa}.

Again, this is not an overkill! Unlike the other bounds we have encountered, nothing cancelled out here and no one wants to see the second derivative of a product with so many factors. Besides, we like recycling ♻️

\frac{\partial}{\partial \eta}\ \ln\left(\frac{1}{\kappa}\right) =  \frac{\partial}{\partial \eta}\ \ln\left(A(\eta)\right) +\frac{\partial}{\partial \eta}\ \ln\left( \tanh(\eta)\right) - \frac{\partial}{\partial \eta}\ \ln \Big(\tfrac{\eta}{n}\, \coth(\tfrac{\eta}{n})+\eta\,\mathrm{csch}(\eta)\Big).

The good news is that the first two summands are taken care of with the lower bound considerations. The bad news is the logarithmic convexity of

\Big(\tfrac{\eta}{n}\, \coth(\tfrac{\eta}{n})+\eta\,\mathrm{csch}(\eta)\Big).

This is as far as the reduction goes and at this point the true computations begin. In the end, we managed to prove the strict logarithmic concavity. Similarly to the one-sided exponential, there is no common optimal lattice. This time, \eta_B <2 \mathrm{arcsinh}(n)<\eta_A.

For small n, there were a few adjustments, but this is the overall idea.


References

[1] A. J. E. M. Janssen, “Some Weyl-Heisenberg frame bound calculations,” Indagationes
Mathematicae
, vol. 7, no. 2, p. 165–183, 1996.
[2] M. Faulhuber and I. Shafkulovska, “Gabor frame bound optimizations,” arXiv preprint
arXiv:2204.02917
, 2022.