Abstract
In this note we provide a negative answer to a question raised by Kreisel concerning a condition on the short-time Fourier transform that would imply the HRT conjecture. In particular we provide a new type of uncertainty principle for the short-time Fourier transform which forbids the arrangement of an arbitrary “bump with fat tail” profile.
Avoid common mistakes on your manuscript.
1 Introduction
A famous open problem in Gabor analysis is the so-called HRT conjecture, concerning the linear independence of finitely many time-frequency shifts of a non-trivial square-integrable function [13]. To be precise, for \(x,\omega \in \mathbb {R}^{d}\) consider the translation and modulation operators acting on \(f \in L^2(\mathbb {R}^{d})\):
For \(z=(x,\omega )\in \mathbb {R}^{2d}\) we say that \(\pi (z)f = M_\omega T_x f\) is a time-frequency shift of f along z. The HRT conjecture can thus be stated as follows:
Conjecture
Given \(g \in L^2(\mathbb {R}^{d})\setminus \{0\}\) and a set \(\Lambda \) of finitely many distinct points \(z_1,\ldots ,z_N \in \mathbb {R}^{2d}\), the set \(G(g,\Lambda )= \{\pi (z_k)g \}_{k=1}^N\) is a linearly independent set of functions in \(L^2(\mathbb {R}^{d})\).
As of today this somewhat basic question is still unanswered. Nevertheless, the conjecture has been proved for certain classes of functions or for special arrangements of points. We address the reader to the surveys [14,15,16, Sect. 11.9] and the paper [22] for a detailed and updated state of the art on the issue. As a general remark we mention that the difficulty of the problem is witnessed by the variety of techniques involved in the known partial results, and also the surprising gap between the latter and the contexts for which nothing is known. For example, a celebrated result by Linnell [28] states that the conjecture is true for arbitrary \(g \in L^2(\mathbb {R}^{d})\) and for \(\Lambda \) being a finite subset of a full-rank lattice in \(\mathbb {R}^{2d}\) and the proof is based on von Neumann algebras arguments. In spite of the wide range of this partial result, a solution is still lacking for smooth functions with fast decay (e.g., \(g \in \mathcal {S}(\mathbb {R}^d)\)) or for general configurations of just four points. The problem is further complicated by numerical evidence in conflict with analytic conclusions [10].
A recent contribution by Kreisel [19] proves the HRT conjecture under the assumption that the distance between points in \(\Lambda \) is large compared to the decay of g. The class of functions g which are best suited for this perspective include functions with sharp descent near the origin or having a singularity away from which g is bounded. It should be highlighted that reconstruction and interpolation problems in the same spirit (i.e., involving sufficiently separated atoms) were already considered in more general settings such as coorbit theory: see for instance the “piano reconstruction theorem” [6, Thm. 25] and [7, Prop. 8.2].
Kreisel’s paper ends with a question on the short-time Fourier transform (STFT). Recall that this is defined as
for given \(f,g \in L^2(\mathbb {R}^{d})\), where \(\langle \cdot ,\cdot \rangle \) denotes the inner product on \(L^2(\mathbb {R}^{d})\). The STFT plays a central role in modern time-frequency analysis [12].
Question 1
Given \(f \in L^2(\mathbb {R}^{d})\) and \(R,N>0\), is there a way to design a window \(g \in L^2(\mathbb {R}^{d})\) such that the “bump with fat tail” condition
holds?
From a heuristic point of view this would amount to determine a window g such that \(V_gf\) shows a bump near the origin and a mild decay at infinity; that is, the energy of the signal accumulates a little near the origin and then spreads on the tail (hence a fat tail). This balance is unavoidable in view of the uncertainty principle, which forbids an arbitrary accumulation near the origin [11, 23]. The design of waveforms associated with peaky phase-space representations is a relevant problem in radar signal analysis. We cannot frame here the huge engineering literature on the issue; we just mention the comprehensive monograph [24] and the papers [1, 17, 18, 25] for various aspects of this topic.
A positive answer to Question 1 would prove the HRT conjecture by [19, Thm. 3]. In fact we prove that the answer is negative as a consequence of the following result, which can be interpreted as a form of the uncertainty principle for the STFT [2, 8, 9, 20].
Theorem 1.1
Let \(g(t) = e^{-\pi t^2}\) and assume that there exist \(R >0\), \(N>1\) and \(f \in L^2(\mathbb {R}^{d})\setminus \{0\}\) such that
Then
This result is indeed a negative answer to Question 1 since \(|V_gf (x,\omega )| = |V_f g(-x,-\omega )|\). In fact, a stronger result can be proved in the case where the cylinder in (2) is replaced by a sphere.
Theorem 1.2
Let \(g(t) = e^{-\pi t^2}\) and assume that there exists \(R>0\), \(N>1\) and \(f \in L^2(\mathbb {R}^{d})\setminus \{0\}\) such that
Then
Moreover, (4) holds with \(R=\sqrt{2\log N / \pi }\) if and only if \(f(t)= ce^{-\pi t^2}\) for some \(c \in \mathbb {C}\setminus \{0\}\).
We conjecture that these results extend, in some form, to general \(f,g\in L^2(\mathbb {R}^{d})\). For example, we expect that in general \(V_g f\) cannot descend in the frequency direction more quickly than the Fourier transform of g. However a precise formulation seems not trivial to state and prove.
2 Proof of the Main Results and Remarks
Proof of Theorem 1.1
An explicit computation shows that
where we set
Notice that \(\Phi f\) is an entire function on \(\mathbb {C}^d\), since differentiation under the integral sign is allowed. Define
where \(a>0\) will be fixed in a moment. The maximum principle [21] implies that \(|\Phi f|\) takes the value \(M_{a,R}\) at some point of the boundary of \(Q_{a,R}\). Since \(f,g\in L^2(\mathbb {R}^d)\), \(V_gf\) vanishes at infinity (e.g. [4, Corollary 3.10]), so that \(V_g f(x,-\omega ) \rightarrow 0\) for \(|x|\rightarrow + \infty \), uniformly with respect to \(\omega \in \mathbb {R}^d\). Therefore \(\Phi f(x+i\omega ) \rightarrow 0\) for \(|x| \rightarrow +\infty \), uniformly with respect to \(\omega \) over compact subsets of \(\mathbb {R}^{d}\). This shows that for sufficiently large \(a>0\) we have \(|\Phi f(z_0)|=M_{a,R}\) for some point \(z_0=(x_0,\omega _0)\) with \(|\omega _0|= R\).
In view of assumption (2) the following estimate holds:
where we used the identity \(\langle f,g\rangle = V_gf(0) = \Phi f(0)\); therefore
Assume now that \(R \le \sqrt{\log N / \pi }\); this would imply \(M_{a,R} \le |\Phi f(0)|\) and thus \(\Phi f\) would be constant on \(Q_{a,R}\), hence on \(\mathbb {C}^d\) by analytic continuation [21]. Since \(\Phi f(x+i\omega ) \rightarrow 0\) for \(|x| \rightarrow +\infty \) as already showed above, we could conclude that \(\Phi f \equiv 0\), hence \(V_gf \equiv 0\) and then \(f\equiv 0\), which is a contradiction. \(\square \)
Remark 2.1
Notice that Theorem 1.1 still holds in the case where the cylinder in (2) is replaced by any other cylinder obtained from the previous one by a symplectic rotation (cf. [5, Sect. 2.3.2]). Indeed, if \(\widehat{S}\) denotes a metaplectic operator [5] corresponding to \(S \in \mathrm {Sp}(d,\mathbb {R}) \cap \mathrm {O}(2d,\mathbb {R})\), condition (2) with \(z=(x,\omega )\) replaced by \(S^{-1}z\) is equivalent to
This can be easily seen by using the covariance property [12, Lemma 9.4.3]
the fact that \(\widehat{S}\) is unitary on \(L^2(\mathbb {R}^{d})\) and that \(\widehat{S}g = cg\) for some \(c \in \mathbb {C}\), \(|c|=1\), if \(g(t)=e^{-\pi t^2}\) [5, Prop. 252].
Remark 2.2
The estimate for R in (3) is sharp. Consider indeed a dilated Gaussian function \(f_\lambda (t) = e^{-\pi \lambda ^2 t^2}\), \(0 < \lambda \le 1\); a straightforward computation (see for instance [3, Lemma 3.1]) shows that
Condition (2) is thus satisfied if and only if
and letting \(\lambda \rightarrow 0^+\) yields the bound in (3).
It is worth emphasizing that there is no non-zero \(f \in L^2(\mathbb {R}^{d})\) such that the optimal bound in (3) can be attained, in contrast to other uncertainty principles for the STFT.
Proof of Theorem 1.2
Recall the connection between the STFT and the Bargmann transform of a function \(f \in L^2(\mathbb {R}^{d})\) [12, Prop. 3.4.1]:
where the Bargmann transform is defined by
(here \(g(t) = e^{-\pi t^2}\) as in the statement). This correspondence is indeed a unitary operator from \(L^2(\mathbb {R}^{d})\) onto the Bargmann-Fock space \(\mathcal {F}^2(\mathbb {C}^d)\), i.e. the Hilbert space of all entire functions F on \(\mathbb {C}^d\) such that \(e^{-\pi |\cdot |^2/2}F \in L^2(\mathbb {C}^d)\), cf. [12, Sect. 3.4] (see also [26, 27]).
We now argue as in the proof of Theorem 1.1. After setting
the maximum principle implies that \(|\mathcal {B}f|\) takes the value \(M_R\) on some point z with \(|z|=R\) and moreover \(M_R>0\) (otherwise by analytic continuation we would have \(\mathcal {B}f=0\) and therefore \(f=0\)). Condition (4) then implies
If \(R < \sqrt{2 \log N/\pi }\) we obtain \(M_R < |\mathcal {B}f(0)|\), which is a contradiction. If \(R = \sqrt{2 \log N/\pi }\) then \(M_R = |\mathcal {B}f(0)|\) and therefore \(\mathcal {B}f(z)= C\), \(z \in \mathbb {C}^d\), again by the maximum principle and analytic continuation, with \(C\ne 0\). On the other hand, a direct computation and the injectivity of the Bargmann transform show that \(\mathcal {B}f(z)=1\) (hence \(|V_g f (z)| = 2^{-d/4} e^{-\pi |z|^2/2}\)) if and only if \(f(t)= 2^{d/4}e^{-\pi t^2}\). This gives the last part of the claim. \(\square \)
References
Benedetto, J.J., Benedetto, R.L., Woodworth, J.T.: Optimal ambiguity functions and Weil’s exponential sum bound. J. Fourier Anal. Appl. 18(3), 471–487 (2012)
Bonami, A., Demange, B., Jaming, P.: Hermite functions and uncertainty principles for the Fourier and the windowed Fourier transforms. Rev. Mat. Iberoam. 19(1), 23–55 (2003)
Cordero, E., Nicola, F.: Metaplectic representation on Wiener amalgam spaces and applications to the Schrödinger equation. J. Funct. Anal. 254(2), 506–534 (2008)
Cordero, E., Trapasso, S.I.: Linear perturbations of the Wigner distribution and the Cohen class. Anal. Appl. 18(3), 385–422 (2020)
de Gosson M.: Symplectic Methods in Harmonic Analysis and in Mathematical Physics. Pseudo-Differential Operators Theory and Applications, Birkhäuser (2011)
Feichtinger, H.G., Gröchenig, K.: Gabor wavelets and the Heisenberg group: Gabor expansions and short time Fourier transform from the group theoretical point of view. In: Wavelets, 359–397, Wavelet Anal. Appl., 2, Academic Press, Boston, MA, (1992)
Feichtinger, H.G., Gröchenig, Karlheinz: Banach spaces related to integrable group representations and their atomic decompositions. II. Monatsh. Math. 108(2–3), 129–148 (1989)
Fernández, C., Galbis, A.: Annihilating sets for the short time Fourier transform. Adv. Math. 224(5), 1904–1926 (2010)
Gröchenig, K., Zimmermann, G.: Hardy’s theorem and the short-time Fourier transform of Schwartz functions. J. Lond. Math. Soc. 63(1), 205–214 (2001)
Gröchenig, K.: Linear independence of time-frequency shifts? Monatsh. Math. 177(1), 67–77 (2015)
Gröchenig, K.: Uncertainty principles for time-frequency representations. In: Advances in Gabor analysis, 11–30, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Boston, MA (2003)
Gröchenig, K.: Foundations of Time-frequency Analysis, Applied and Numerical Harmonic Analysis. Birkhäuser Boston, Boston, MA (2001)
Heil, C., Ramanathan, J., Topiwala, P.: Linear independence of time-frequency translates. Proc. Am. Math. Soc. 124(9), 2787–2795 (1996)
Heil, C., Speegle, D.: The HRT conjecture and the zero divisor conjecture for the Heisenberg group. In: Excursions in harmonic analysis. Vol. 3, 159–176, Applied and Numerical Harmonic Analysis, Birkhäuser/Springer, Cham (2015)
Heil, C.: Linear independence of finite Gabor systems. In: Harmonic analysis and applications, 171–206, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Boston, MA, (2006)
Heil, C.: A Basis Theory Primer, Expanded Edition, Applied and Numerical Harmonic Analysis, Birkhäuser Basel (2011)
Herman, M.A., Strohmer, T.: High-resolution radar via compressed sensing. IEEE Trans. Signal Process 57(6), 2275–2284 (2009)
Howard, S.D., Calderbank, A.R., Moran, W.: The finite Heisenberg-Weyl groups in radar and communications. EURASIP J. Appl. Signal Process. 2006, Art. ID 85685, 1–12
Kreisel, M.: Letter to the Editor: Linear independence of time-frequency shifts up to extreme dilations. J. Fourier Anal. Appl. 25(6), 3214–3219 (2019)
Lieb, E.H.: Integral bounds for radar ambiguity functions and Wigner distributions. J. Math. Phys. 31(3), 594–599 (1990)
Narasimhan, R.: Several Complex Variables. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, IL (1971)
Okoudjou, K.A.: Extension and restriction principles for the HRT conjecture. J. Fourier Anal. Appl. 25(4), 1874–1901 (2019)
Ricaud, B., Torrésani, B.: A survey of uncertainty principles and some signal processing applications. Adv. Comput. Math. 40(3), 629–650 (2014)
Rihaczek, A.W.: Principles of High-Resolution Radar. Artech House, Boston (1996)
Song, X., Zhou, S., Willett, P.: The role of the ambiguity function in compressed sensing radar. In: 2010 IEEE International Conference on Acoustics, Speech and Signal Processing, Dallas, TX, (2010), pp. 2758–2761
Toft, J.: The Bargmann transform on modulation and Gelfand–Shilov spaces, with applications to Toeplitz and pseudo-differential operators. J. Pseudo-Differ. Oper. Appl. 3, 145–227 (2012)
Toft, J.: Images of function and distribution spaces under the Bargmann transform. J. Pseudo-Differ. Oper. Appl. 8, 83–139 (2017)
von Linnell, P.A.: Neumann algebras and linear independence of translates. Proc. Am. Math. Soc. 127(11), 3269–3277 (1999)
Acknowledgements
The authors wish to thank Professor Elena Cordero for fruitful discussions and the referees for pointing out relevant references. The present research was partially supported by MIUR Grant Dipartimenti di Eccellenza 20182022, CUP: E11G18000350001, DISMA, Politecnico di Torino.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Chris Heil.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Nicola, F., Trapasso, S.I. A Note on the HRT Conjecture and a New Uncertainty Principle for the Short-Time Fourier Transform. J Fourier Anal Appl 26, 68 (2020). https://doi.org/10.1007/s00041-020-09769-z
Received:
Revised:
Published:
DOI: https://doi.org/10.1007/s00041-020-09769-z