The HRT Conjecture

A couple of weeks ago, I attended a workshop hosted by Darrin Speegle on the HRT Conjecture. First posed twenty years ago by Chris Heil, Jay Ramanathan, and Pankaj Topiwala in this paper, the conjecture states that every finite collection of time-frequency shifts of any nonzero function in $L^2(\mathbb{R})$ is linearly independent. In this post, I will discuss some of the key ideas behind some of the various attempts at chipping away at HRT, and I’ll describe what appear to be fundamental barriers to a complete solution. For more information, see these survey papers: one and two.

First, some notation: Denote the translation-by- $a$ and modulation-by- $b$ operators by

$(T_af)(x):=f(x-a),\qquad (M_bf)(x)=e^{2\pi i bx}f(x),$

respectively. Then the formal conjecture statement is as follows:

The HRT Conjecture. For every $0\neq f\in L^2(\mathbb{R})$ and every finite $\Lambda\subset\mathbb{R}^2$ , the collection $\{M_bT_af\}_{(a,b)\in\Lambda}$ is linearly independent.

What follows are some of the popular methods for tackling HRT:

— Transform methods —

Consider the set of nonzero-scaled time-frequency shift operators $S:=\{cM_bT_a:(a,b,c)\in\mathbb{R}^3,~c\neq0\}$ . Now consider the group of linear transformations $U$ such that $S=USU^{-1}$ , that is, conjugating with $U$ permutes the members of $S$ . These are called metaplectic transforms. Trivial examples include translation and modulation operators. Then for any counterexample to HRT

$\displaystyle\sum_{(a,b)\in\Lambda} c_{(a,b)}M_bT_af=0,$

one may apply $U$ to both sides to get another counterexample:

$\displaystyle\sum_{(a',b')\in\Lambda'} c'_{(a',b')} M_{b'}T_{a'} Uf=0.$

As such, applying $U$ will modify the function $f\mapsto Uf$ , the time-frequency shifts $\Lambda\mapsto\Lambda'$ , as well as the scalar multiples in the combination $\{c_{(a,b)}\}\mapsto\{c'_{(a',b')}\}$ . It is helpful to visualize $\Lambda\mapsto\Lambda'$ as an operation on the plane of pairs $(a,b)$ , called phase space. Here, $T_a$ shifts the plane to the right by $a$ , whereas $M_b$ shifts the plane up by $b$ . Considering the Fourier transform converts modulations to translations (and translations to inverse modulations), it is also an example of a metaplectic transform, and it acts on phase space by a 90-degree rotation. In fact, any rotation can be achieved by a fractional Fourier transform. Also, dilation will stretch phase space along the translation axis, and produce the inverse stretch along the modulation axis. Finally, chirp modulation shears phase space. Overall, metaplectic transforms can be leveraged to apply any area-preserving affine transformation of phase space.

As an example application of metaplectic transforms, we will show that translations of any nonzero function in $L^2(\mathbb{R})$ are linearly independent. Suppose

$\displaystyle\sum_{a\in K}c_a T_af=0.$

Then applying the Fourier transform gives

$\displaystyle\sum_{a\in\Lambda}c_ae^{-2\pi ia\xi}\hat{f}(\xi)=0\qquad\text{a.e.}$

At this point, we can factor out $\hat{f}(\xi)$ and restrict our attention to the support of $\hat{f}$ , which has positive measure since $\hat{f}\neq0$ . As such, the trigonometric polynomial $\sum_{a\in\Lambda}c_ae^{-2\pi ia\xi}$ must be zero on a set of positive measure, which is only possible if the trigonometric polynomial is trivial.

Metaplectic transforms are also useful for making “without loss of generality” statements. For example, if you want to prove HRT for any configuration $\Lambda$ of four points in phase space, you may apply metaplectic transforms to have $(0,0), (1,0), (0,b)\in\Lambda$ without loss of generality.

Before moving on to the next section, I want to discuss two proofs that are related to the above proof. First, it is known that HRT holds whenever $\Lambda$ is a subset of a lattice in $\mathbb{R}^2$ . (In particular, HRT holds for any three points.) In the special case where the lattice is the integer lattice, one may apply the Zac transform to convert time-frequency shifts into two-dimensional modulations. In fact, the proof of this case is nearly identical to the above proof that pure translations are independent.

We’ve been restricting the set of time-frequency shifts in a couple of ways in order to chip away at HRT, but you can also restrict the function class instead. For example, suppose $f$ has compact support and

$\displaystyle\sum_{(a,b)\in\Lambda}c_{(a,b)}M_bT_af=0.$

If the translations are all the same in $\Lambda$ , then we are done by the previous analysis. Otherwise, let $a_1$ and $a_2$ be the two largest distinct translations in $\Lambda$ , and let $r$ denote the essential supremum of the support of $T_{a_1}f$ . Then we can isolate the terms of the form $(a_1,b)\in\Lambda$ by restricting the support to $(r-(a_1-a_2),r]$ . These terms are all modulations of $T_{a_1}f$ , and so the scalars $c_{(a_1,b)}$ are all zero. Repeating inductively then gives that HRT holds for functions of compact support.

Intuitively, the proof for compactly supported functions has the look and feel of row operations of a matrix, and as such, the proof is very much married to the time domain. Perhaps not surprisingly, this proof does not generalize to much broader classes of functions, but there are other time-domain methods that have found substantial success.

— Time-domain methods —

To illustrate the main idea here, let’s prove that two translations are linearly independent, but let’s do so without appealing to the Fourier transform. For simplicity (and without loss of generality), we consider translation by -1:

$f(x+1)=cf(x) \qquad\text{a.e.}$

Intuitively, this means that for each $x\in[0,1)$ , the samples $f(x+n)=c^nf(x)$ with $n\in\mathbb{Z}$ form an exponential. As such, $f$ either blows up to the left or to the right, or has constant modulus, but it’s certainly not in $L^2(\mathbb{R})$ in any case.

Perhaps surprisingly, slight generalizations of this particular analysis seem rather difficult: Take two parallel lines in phase space, and consider two points on each line. Then you can write a similar recurrence relation to the above, but instead of $c$ , you get a quotient of trigonometric polynomials. It turns out that this quotient is sufficiently well behaved that you can consider it to be “essentially constant” in an ergodic sense, and so the desired conclusion can be made. See this paper for the (rather technical) details.

In general, it is difficult to analyze the exact recurrence relations that come from a dependency between time-frequency shifts. It is often much easier to analyze a “recurrence inequality” that comes from taking absolute values of both sides of the recurrence relation, and then passing through the triangle inequality. The following argument serves as a helpful example:

Suppose $f$ has the property that for each $c>0$ , $e^{cx}|f(x)|$ is ultimately decreasing (examples include Gaussians and other Hermite functions). Importantly, this implies that whenever $a<b$ , then $e^{c(x-a)}|f(x-a)|<e^{c(x-b)}|f(x-b)|$ for all sufficiently large $x$ , and so

$\displaystyle\frac{|f(x-a)|}{|f(x-b)|}<\frac{e^{c(x-b)}}{e^{c(x-a)}}=e^{-c(b-a)}$

for all sufficiently large $x$ . In fact, since $c>0$ is arbitrary, we may conclude that

$\displaystyle\lim_{x\rightarrow\infty}\frac{|f(x-a)|}{|f(x-b)|}=0. \qquad(*)$

Now that we understand the function class that $f$ belongs to, suppose

$\displaystyle\sum_{(a,b)\in\Lambda}c_{(a,b)}M_bT_af=0,$

and let $a_1>\cdots>a_k$ be the distinct translations in $\Lambda$ . Then there exist trigonometric polynomials $p_1(x),\ldots,p_k(x)$ such that

$\displaystyle p_1(x)f(x-a_1)=-\sum_{i=2}^kp_i(x)f(x-a_i) \quad\text{a.e.}$

Since $f(x)$ is ultimately nonzero, we may divide and take absolute values to get a “recurrence inequality”:

$\displaystyle |p_1(x)|=\bigg|\sum_{i=2}^kp_i(x)\frac{f(x-a_i)}{f(x-a_1)}\bigg|\leq\sum_{i=2}^k|p_i(x)|\frac{|f(x-a_i)|}{|f(x-a_1)|}$

for almost every sufficiently large $x$ . By $(*)$ , and since the trigonometric polynomials $p_2(x),\ldots,p_k(x)$ are bounded, we see that the right-hand side goes to zero on a set of full measure as $x$ gets large, which is not the sort of behavior exhibited by a nontrivial trigonometric polynomial. As such, we conclude that $p_1(x)=0$ , and applying this argument inductively then gives that the entire linear combination is trivial.

Analyzing a recurrence inequality is fundamentally different from analyzing recurrence relations, since the analysis is inherently one-sided: we only take $x$ to be large (due to the inequality going one way) instead of also seeing what happens when $-x$ gets large. As such, instead of identifying that $f$ must exhibit some sort of exponential blowup in one direction or another, we are forced to merely establish that at best, $f$ decays exponentially. This would be fine if we were to assume that $f$ belongs to a function class with faster-than-exponential decay, since this would allow us to derive a contradiction. However, this appears to be a fundamental barrier with this proof technique. I don’t think it will enable us to tackle all of $L^2(\mathbb{R})$ , or even Schwartz space.

To be clear, we don’t yet have a proof that HRT holds for all functions of faster-than-exponential decay. Above, we showed that HRT holds for the monotone functions of such decay, and this paper tackles all functions $f$ with slightly faster decay: for every $c>0$ , $e^{cx\log x}|f(x)|\rightarrow0$ as $x\rightarrow\infty$ .

— Other methods —

In this section, we discuss a few other methods that have been used to tackle HRT, and could very well lead to a full proof of HRT.

1. Spectral methods. Notice that HRT is a statement about the kernels of finite linear combinations of time-frequency shift operators, since

$\displaystyle\sum_{(a,b)\in\Lambda}c_{(a,b)}M_bT_af=0$

precisely when $f$ is in the kernel of $\sum_{(a,b)\in\Lambda}c_{(a,b)}M_bT_a$ . But suppose this combination of operators exhibits another eigenvalue $\lambda$ . Then

$\displaystyle\sum_{(a,b)\in\Lambda}c_{(a,b)}M_bT_af=\lambda f,$

meaning the time-frequency shifts $\Lambda\cup\{(0,0)\}$ produce an HRT counterexample. As such, HRT is equivalent to every finite linear combination of time-shift operators having an empty point spectrum. This suggests an operator-theoretic approach to HRT. Some results along these lines are available here and there.

2. Perturbation methods. Suppose HRT holds for a given $f\in L^2(\mathbb{R})$ and for a given collection $\Lambda$ of points in phase space. Then it is known that sufficiently small $L^2$ perturbations of $f$ also satisfy HRT with $\Lambda$ , and furthermore, sufficiently small Euclidean perturbations of $\Lambda$ satisfy HRT with $f$ . As such, one could conceivably prove HRT by establishing explicit bounds on the sizes of allowable perturbations. For example, when perturbing $\Lambda$ , it would help to have control of the lower Riesz bound of $\{M_bT_af\}_{(a,b)\in\Lambda}$ .

3. Passing to $L^2(\mathbb{H})$ . Let $\mathbb{H}$ denote the multiplicative group

$\{zM_bT_a:a,b\in\mathbb{R},~z\in\mathbb{C},~|z|=1\}.$

It is helpful to identify $\mathbb{H}=\mathbb{T}\times\mathbb{R}\times\mathbb{R}$ . Consider functions in $L^2(\mathbb{H})$ and translation operator $T_x$ given by $(T_xf)(y)=f(x^{-1}y)$ for every $x,y\in\mathbb{H}$ . It is a folklore theorem that HRT is equivalent to translations of nonzero functions in $L^2(\mathbb{H})$ being linearly independent. As part of the workshop, we ironed out the extent to which these statements are equivalent (they are “nearly equivalent”), and passing to $L^2(\mathbb{H})$ appears to be a reasonable strategy to tackle HRT. Considering the role that the Fourier transform plays in demonstrating the linear independence of pure translations over $L^2(\mathbb{H})$ , this suggests that one ought to study a Fourier transform over $L^2(\mathbb{H})$ .

— HRT subproblems —

To help illustrate the current boundary of modern techniques, this section provides a few subproblems, each of which are implied by HRT.

Problem 1. Is HRT true for $\Lambda=\{(0,0),(1,0),(0,1),(\sqrt{2},\sqrt{2})\}$ ?

This problem highlights the fact that we don’t yet have a proof of HRT for the special case where $|\Lambda|=4$ . The cases where $|\Lambda|<4$ can be handled by the fact that HRT holds whenever $\Lambda$ is a finite subset of a lattice in $\mathbb{R}^2$ . By contrast, when $|\Lambda|=4$ , we only have results for very specific (and notably non-generic) configurations.

Problem 2. Is HRT true for every finite $\Lambda\subset\mathbb{Z}\times\mathbb{R}$ ?

To solve this problem, one is inclined to exploit time-domain techniques, specifically recurrence relations (not recurrence inequalities!). By dilation tricks, this would imply HRT for arbitrary rectangular lattices (which is a known result, but not particularly easy to prove).

Problem 3. Is HRT true for functions with faster-than-exponential decay?

Recall that recurrence inequalities appear to be incapable of proving HRT for functions of exponential-or-slower decay. It would be nice to know if these techniques can “live up to their potential.”

Problem 4. Is HRT true for hyperbolic secant?

Recall that $\mathrm{sech}(x)=2/(e^x+e^{-x})$ . Interestingly, the Fourier transform of hyperbolic secant is a dilated version of itself. As such, this function has exponential decay in both time and frequency, and is therefore a natural candidate to illustrate the boundary of the time-domain methods.

3 thoughts on “The HRT Conjecture”

Abdelkrim Bourouihiya says:

November 22, 2016 at 6:55 pm

Hi,
HRT is actually true for the hyperbolic secant function. The paper “Linear Independence of Finite Gabor Systems Determined by Behavior at Infinity” proves that HRT holds for any logarithmo-exponential function. Greeting,

Abdel

1. Dustin G. Mixon says:
  
  November 26, 2016 at 11:02 pm
  
  Thanks for the pointer, Abdel. I like your proof!
  
Pingback: Tight Frames and Approximation 2018 – Short, Fat Matrices

	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Jaan Parts on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…
	Tom Sirgedas on Polymath16, seventeenth thread…

Share this:

Like this:

Related

3 thoughts on “The HRT Conjecture”

Leave a Reply Cancel reply