Abstract
Given \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and a finite set \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) we demonstrate the linear independence of the set of time-frequency translates \(\mathcal {G}(f, \Lambda ) = \{\pi (\lambda )f\}_{\lambda \in \Lambda }\) when the time coordinates of points in \(\Lambda \) are far apart relative to the decay of f. As a corollary, we prove that for any \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and finite \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) there exist infinitely many dilations \(D_r\) such that \(\mathcal {G}(D_rf, \Lambda )\) is linearly independent. Furthermore, we prove that \(\mathcal {G}(f, \Lambda )\) is linearly independent for functions like \(f(t) = \frac{cos(t)}{|t|}\) which have a singularity and are bounded away from any neighborhood of the singularity.
Avoid common mistakes on your manuscript.
1 Introduction
Consider the translation operator \(T_x f = f(t-x)\) and the modulation operator \(M_\omega f = e^{2 \pi i \omega \cdot t} f(t)\) acting on \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n).\) For \(\lambda = (x, \omega ) \in {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) we define the time-frequency shift \(\pi (\lambda )f = M_\omega T_x f.\) The Heil–Ramanathan–Topiwala (HRT) Conjecture [8] states
Conjecture 1
Suppose \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}})\) is nonzero and \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2}\) is a finite set. Then the collection of functions \(\mathcal {G}(f, \Lambda ) = \{\pi (\lambda )f\}_{\lambda \in \Lambda }\) is linearly independent.
The HRT Conjecture is still open in its most general form, but it has been proven under various additional assumptions on the function f and the point set \(\Lambda \) [1,2,3,4,5, 8,9,10,11].
In this paper we will prove Conjecture 1 in cases where the distance between points in \(\Lambda \) is large relative to the decay of f.
Theorem 1
Let \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n),\) let \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) be a finite set, and fix R so that \(|f(t)| < \frac{|f(0)|}{N-1}\) for all t outside of the ball of radius R around the origin. If \(||x_i - x_j|| > R\) whenever \( i \ne j\) then \(\mathcal {G}(f,\Lambda )\) is linearly independent.
The intuition for Theorem 1 is that if the points in \(\Lambda \) are spaced far apart then in any linear dependence the tails of translates of f must combine to cancel the peaks of f. This requires putting large coefficients on the translates of f. However by putting large coefficients on the translates of f, we make the peaks of the translates more difficult to cancel, leading to a contradiction.
Theorem 1 is most effective when |f| drops off steeply near the origin. Given any \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) we can engineer such a steep descent by applying a sufficiently large dilation, assuming \(f(0) \ne 0.\) We denote by \(D_r\) the unitary operator which dilates a function f uniformly along all the coordinate axes.
Corollary 1
Suppose \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and \(f(0) \ne 0.\) Given \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) there exists \(r > 0\) such that \(\mathcal {G}(D_{r'}f, \Lambda )\) is linearly independent for all \(0< r' < r.\)
Similarly, if f has a singularity away from which it is bounded then we can find translates of f which have an arbitrarily steep drop off. Thus we can prove Conjecture 1 for such functions.
Theorem 2
Let f be continuous except at a point p where \(\lim _{t \rightarrow p} |f(t)| = \infty .\) Assume that f is bounded away from any neighborhood of p. Then \(\mathcal {G}(f, \Lambda )\) is linearly independent for any finite \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}.\)
2 Proofs, Examples, and Extensions
The following lemma captures the intuition for Theorem 1 described above.
Lemma 1
Let \(S = \{x_i\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^n, f \in C({{\,\mathrm{\mathbb {R}}\,}}^n),\) and \(E = \{e_i\}_{i=1}^N \subset C({{\,\mathrm{\mathbb {R}}\,}}^n)\) such that \(|e_i(t)| = 1\) for all \(t \in {{\,\mathrm{\mathbb {R}}\,}}^n.\) Furthermore, suppose that \(|f(x_i - x_j)| < \frac{|f(0)|}{N-1}\) whenever \(x_i, x_j\) are distinct points in S. Then the collection of functions \(\{e_i(t)f(t-x_i)\}_{i=1}^N\) is linearly independent.
Proof
Assume that the functions \(\{e_i(t)f(t-x_i)\}_{i=1}^N\) are linearly dependent, so that for some coefficients \(\{c_i\}_{i=1}^N\) we have
Since f is continuous this equality holds for all \(t \in {{\,\mathrm{\mathbb {R}}\,}}^n.\) If we evaluate the left hand side at the point \(x_j\) we can rearrange to get the following inequality
After summing all these inequalities and canceling |f(0)| from each side, we see that
which is a contradiction. The last equality follows since each term \(|c_i|\) appears in exactly \(N-1\) of the inner sums in the second expression. \(\square \)
Now we can prove our first theorem.
Proof of Theorem 1
We can apply Lemma 1 with \(S=\{x_i\}_{i=1}^N\) and \(E = \{e^{2\pi i \omega _i \cdot t}\}_{i=1}^N.\) Since the points \(x_i-x_j\) all lie outside the ball of radius R around the origin, \(|f(x_i - x_j)| < \frac{|f(0)|}{N-1}\) as required. \(\square \)
Note that we only need to assume that the time coordinates of the points in \(\Lambda \) are spaced far apart for Theorem 1 to hold. Although the specific value f(0) suspiciously appears in our hypothesis, \(\mathcal {G}(f, \Lambda )\) is linearly independent if and only if \(\mathcal {G}(T_xf, \Lambda )\) is linearly independent for all \(x \in {{\,\mathrm{\mathbb {R}}\,}}^n,\) so we can always translate f to put the most advantageous value at the origin.
Given Theorem 1, it is straightforward to deduce Corollary 1.
Proof of Corollary 1
Since \(f \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and \(f(0) \ne 0,\) we can find a value \(R>0\) such that \(|f(t)| < \frac{|f(0)|}{N-1}\) for all t outside of a ball of radius R around 0. Applying a dilation \(D_r,\) we see that \(|D_rf(t)| < \frac{|D_rf(0)|}{N-1}\) whenever t lies outside a ball of radius rR. Let \(M = \min _{i,j}||x_i-x_j||\) be the minimum distance between any two points in \(\Lambda .\) Then whenever \(0< r < \frac{M}{R}\) we can apply Theorem 1 to show that \(\mathcal {G}(D_rf, \Lambda )\) is linearly independent. \(\square \)
Since translations and modulations are exchanged under the Fourier transform, we get an analogous result in the frequency domain.
Corollary 2
Let \(f \in L^1({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \({\hat{f}} \in C_0({{\,\mathrm{\mathbb {R}}\,}}^n)\) and let \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}.\) Then there exists a value \(r > 0\) such that \(\mathcal {G}(D_{r'}f, \Lambda )\) is linearly independent whenever \(r' > r.\)
Example 1
Consider the family of functions
The functions \(f_{C, \omega }\) are in \(L^2({{\,\mathrm{\mathbb {R}}\,}}) \cap C_0({{\,\mathrm{\mathbb {R}}\,}}).\) Nonetheless they decay slowly at infinity and oscillate in the tail. To the author’s knowledge, such functions are not covered by the results of [1, 2], or [11] which assume fast decay at infinity or ultimate positivity. Given \(\Lambda = \{(x_i,\omega _i)\}_{i=1}^N\) let \(M = \min _{i,j}|x_i-x_j|.\) Then by applying Theorem 1, we can see that \(\mathcal {G}(f_{C, \omega }, \Lambda )\) is linearly independent whenever \(C > \frac{N-1}{M}.\) For the four point set \(\Lambda ' = \{(0,0), (1,0), (0,1), (\sqrt{2}, \sqrt{2})\}\) we have \(\mathcal {G}(f_{\omega , C}, \Lambda ')\) linearly independent whenever \(C > \frac{3}{\sqrt{2} - 1}.\)
Example 1 suggests that the function \(f(t) = \frac{\cos (\omega t)}{|t|}\) should satisfy Conjecture 1 in full, as it is the pointwise limit of \(f_{C,\omega }\) as \(C \rightarrow \infty .\) This is true, and is implied by Theorem 2 which we are now ready to prove.
Proof of Theorem 2
Without loss of generality we may assume that \(p=0.\) If we fix \(\Lambda \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) of size N such that the minimum distance between the x-coordinates in \(\Lambda \) is R, we would like to find a translate of f which satisfies \(|f(t+x)| < \frac{|f(x)|}{N-1}\) outside the ball of radius R around x. If we can find such an x then the argument in the proof of Lemma 1 applies to show \(\mathcal {G}(f, \Lambda )\) is linearly independent. To find such an x, we first note that since f is bounded away from 0 we can find A such that \(|f(t)| < A\) outside a ball of radius \(\frac{R}{2}\) around 0. Since \(\lim _{t \rightarrow 0} |f(t)| = \infty ,\) we can find an x less than \(\frac{R}{2}\) such that \(|f(x)| > A(N-1),\) and this x satisfies the criteria described above. \(\square \)
Example 2
We can adapt the examples above to find functions in \(L^2({{\,\mathrm{\mathbb {R}}\,}})\) satisfying Conjecture 1. Consider the family of functions
The functions \(g_\omega (t)\) are in \(L^2({{\,\mathrm{\mathbb {R}}\,}}) \cap C_0({{\,\mathrm{\mathbb {R}}\,}}).\) By Theorem 2, they satisfy Conjecture 1.
By applying the Short Time Fourier Transform (STFT) we can demonstrate linear independence when the points in \(\Lambda \) are sufficiently far apart in the time-frequency plane. For \(f,g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) the STFT of f with respect to g is given by
It is easy to see [7] that \(V_gf \in C_0({{\,\mathrm{\mathbb {R}}\,}}^{2n})\) and satisfies the identity
Theorem 3
Suppose \(f,g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \(V_gf \in C_0({{\,\mathrm{\mathbb {R}}\,}}^{2n}).\) Let \(\Lambda = \{\lambda _i\}_{i=1}^N \subset {{\,\mathrm{\mathbb {R}}\,}}^{2n}\) and fix R so that \(|V_gf(\lambda )| < \frac{|V_gf(0)|}{N-1} = \frac{|\langle f, g \rangle |}{N-1}\) for all \(\lambda \) outside of the ball of radius R around the origin. If \(||\lambda _i - \lambda _j|| > R\) whenever \( i \ne j\) then \(\mathcal {G}(f,\Lambda )\) is linearly independent.
Proof
Suppose \(\mathcal {G}(f, \Lambda )\) is linearly dependent so that for some coefficients \(c_i\) we have
Then by applying the STFT with respect to g we have
where \(u_i\) denotes the time coordinate of \(\lambda _i\) and \(c_i' = e^{-2\pi i x_i \omega _i}c_i.\) However we can apply Lemma 1 to \(V_gf\) with \(S = \{\lambda _i\}_{i=1}^N\) and \(E = \{e^{-2 \pi i u_i \cdot \omega }\}_{i=1}^N\) to show that the functions \(\{e^{-2 \pi i u_i \cdot \omega }V_gf(\lambda - \lambda _i)\}_{i=1}^N\) must be linearly independent, which is a contradiction. \(\square \)
3 Discussion
Our Lemma 1 and Theorem 1 demonstrate that \(\mathcal {G}(f, \Lambda )\) is linearly independent when the points of \(\Lambda \) are far apart relative to the decay in f. However our proofs use no properties specific to the modulations \(e^{2 \pi i \omega t},\) and apply just as well to functions in \(L^p({{\,\mathrm{\mathbb {R}}\,}}^n)\) when \(n>1\) and \(p>2.\) Given the generality of Theorem 1 and in light of the following example, we can see that Theorem 1 alone provides only loose evidence for Conjecture 1.
Example 3
In [6] the authors demonstrate that the function
is in \(C_0({{\,\mathrm{\mathbb {R}}\,}}^2) \cap L^p({{\,\mathrm{\mathbb {R}}\,}}^2)\) for \(p > 4\) and satisfies the dependence
Nonetheless, our Theorem 1 and Corollary 1 can be applied to f, though Theorem 1 clearly does not rule out the dependence above.
One could try to expand the utility of Theorem 3 by leveraging the choice of window function as a free variable. One could leave f and \(\Lambda \) fixed but vary the window function g in an attempt to satisfy the hypotheses. This leads naturally to the following question.
Question 1
Given \(f \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n), R> 0, N > 0\) can we design a window \(g \in L^2({{\,\mathrm{\mathbb {R}}\,}}^n)\) so that \(|V_gf| < \frac{|\langle f, g \rangle |}{N}\) outside the ball of radius R around the origin?
A positive answer to Question 1 would prove the HRT conjecture. We would want to design g so that \(V_gf\) decreases sharply near the origin and then has a fat tail, since we know that the probability mass of \(V_gf\) cannot be too heavily concentrated near the origin due to various uncertainty principles for the STFT. Alternatively, it may be possible to develop a kind of uncertainty principle which answers Question 1 negatively.
References
Benedetto, J.J., Bourouihiya, A.: Linear independence of finite gabor systems determined by behavior at infinity. J. Geom. Anal. 25, 226–254 (2015)
Bownik, M., Speegle, D.: Linear independence of time-frequency translates of functions with faster than exponential decay. Bull. Lond. Math. Soc. 45, 554–566 (2013)
Bownik, M., Speegle, D.: Linear independence of time-frequency translates in \(\mathbb{R}^d\). J. Geom. Anal., pp. 1678–1692 (2016)
Demeter, C.: Linear independence of time frequency translates for special configurations. Math. Res. Lett. 17, 761–779 (2010)
Demeter, C., Zaharescu, A.: Proof of the HRT conjecture for (2,2) configurations. J. Math. Anal. Appl. 388, 151–159 (2012)
Edgar, G., Rosenblatt, J.: Difference equations over locally compact abelian groups. Trans. Am. Math. Soc. 253, 273–289 (1979)
Gröchenig, K.: Foundations of Time-Frequency Analysis. Birkhäuser, Boston (2001)
Heil, C., Ramanathan, J., Topiwala, P.: Linear independence of time-frequency translates. Proc. Am. Math Soc. 124, 2787–2795 (1996)
Linnell, P.A.: von Neumann algebras and linear independence of translates. Proc. Am. Math. Soc. 127, 3269–3277 (1999)
Liu, W.: Letter to the Editor: Proof of the HRT conjecture for almost every (1,3) configuration. J. Fourier Anal. Appl. 25, 1350–1360 (2019)
Okoudjou, K.A.: Extension and restriction principles for the HRT conjecture. J. Fourier Anal. Appl. 25, 1874–1901 (2019)
Acknowledgements
The author thanks Radu Balan and Kasso Okoudjou for introducing him to the HRT Conjecture and for helpful discussions about this work. The author also thanks an anonymous reviewer for encouraging him to expand the results contained in earlier drafts.
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
Kreisel, M. Letter to the Editor: Linear Independence of Time-Frequency Shifts Up To Extreme Dilations. J Fourier Anal Appl 25, 3214–3219 (2019). https://doi.org/10.1007/s00041-019-09699-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00041-019-09699-5