Orthonormal basis and decay

Question

Edit: I added smoothness, hoping to simplify the problem with this additional assumption.

Let me motivate this question first: In signal analysis it is often of interest to understand when a certain function has a fast decaying representation with respect to some basis. I encountered an example where I expected such a fast decaying representation but was unable to show it myself:

The situation is that one is given a sequence of functions whose supports are only overlapping with their nearest neighbors. Intuitively, I expected that if I would write any of those function in terms of the Gram-Schmidt orthonormalized sequence of all functions, then the expansion coefficients should decay fast.

Let me now make this more precise:

Take a family of intervals $I_{2i}:=(i,i+1)$ and $I_{2i+1}=(\frac{1}{2}+i,\frac{1}{2}+i+1)$ with $i \ge 0$ Those intervals are almost disjoint in the sense that $I_i \cap I_j=\emptyset$ if and only if $\left\lvert i-j \right\rvert >1,$ so we only have a nearest neighbor overlap.

We consider a family of smooth functions $h_i:I_i \rightarrow \mathbb{R}$ that are $L^2$ normalized (but not orthogonal) where $h_{i+1}$ is just a translate of $h_i$ by $\frac{1}{2}$ to the right.

We assume that $\langle h_0,h_1 \rangle \neq 0$ and $\langle h_1,h_2 \rangle \neq 0$ to avoid trivialities. Due to the condition on the domain, all other $h_i$ however (besides $h_0$, $h_1,$ and $h_2$) have zero overlap with $h_1$.

We now consider the Gram-Schmidt orthonormalized sequence $(g_i)$ of the $h_i$, i.e. $g_0:=h_0$ and $g_1:=\frac{h_1-\langle h_1,g_0\rangle g_0}{\left\lVert h_1-\langle h_1,g_0\rangle g_0 \right\rVert}$ and so on. Note that also $g_2,g_3,...$ and so on may now have non-vanishing overlap with $h_1$, although this one should intuitively still be small.

Clearly, $h_1=\sum_{n=0}^{\infty} a_n g_n$ for some $a_n$.

I would like to know: How rapidly do the coefficients $a_n$ decay? In particular, is it true that (the following notation means up to a constant) $\left\lvert a_n \right\rvert \lesssim L^n$ for some $L\in (0,1)$?

Answer 1

Think in the opposite direction: start with an orthonormal sequence $g_n$ and try to find appropriate $h_n$. The conditions on $h_n$ are: $h_n$ is a linear combination of $g_0, g_1, \ldots, g_n$, $\|h_n\| = 1$, $\langle h_n, h_{n-1}\rangle = \alpha_n$ for a given $\alpha_n$ (in your question $\alpha_n$ is in fact constant), and $\langle h_n, h_j \rangle = 0$ for $j \leqslant n - 2$.

Clearly, $h_0, h_1, \ldots, h_n$ span the same subspace as $g_0, g_1, \ldots, g_n$, for we assume that $|\alpha_n| < 1$ (in fact if $\alpha_n$ is constant, then necessarily $|\alpha_n| \leqslant 1/2$). Since $h_n$ is orthogonal to $h_0, h_1, \ldots, h_{n-2}$, it follows that $h_n$ is orthogonal to $g_0, g_1, \ldots, g_{n-2}$. Therefore, $h_n$ is a linear combination of $g_n$ and $g_{n-1}$.

This already answers your question: the decay is super-fast, all but two coefficients are zero! However you might be interested in a different thing: what is the coefficient at, say, $h_0$ in the expansion of $g_n$ in terms of $h_0, h_1, \ldots, h_n$. This is a much more interesting problem.

Write $h_n = \beta_n g_{n - 1} + \sqrt{1 - |\beta_n|^2} g_n$. (We could arbitrarily change the sign of the coefficient at $g_n$, but the above choice corresponds to the Gram–Schmidt process). Then it is easy to see that $\beta_0 = 0$ and $$\beta_n = \alpha_n \sqrt{1 - |\beta_{n-1}|^2} .$$ If $\alpha_n$ is a constant, say $\alpha$, this leads to $$\beta_n = \alpha \sqrt{\frac{i}{x} \, \frac{F_{n-1}(i/\alpha)}{F_n(i/\alpha)}},$$ where $F_n$ is the Fibonacci polynomial. (To be honest, I found that empirically, but writing up a recurrence equation for $F_n$ using the one for $\beta_n$ seems straightforward).

Now write the matrix $B$ of coefficients of the expansion of $h_n$ in terms of $g_n$; that is, $B_{n,n-1} = \beta_n$, $B_{n,n} = \sqrt{1 - |\beta_n|^2}$ and $B_{n,m} = 0$ if $m \geqslant n + 1$ or $m \leqslant n - 2$. In order to express $g_n$ as a linear combination of $h_0, h_1, \ldots, h_n$, one needs to invert this matrix.

In the "naively worst case scenario" $\alpha_n \equiv 1/2$ or $\alpha_n \equiv -1/2$, one can find $\beta_n$ and the first column of $B^{-1}$ explicitly: $B^{-1}_{0,n} = \pm((n + 1)(n + 2)/2)^{-1/2} = O(n^{-1})$. It should be possible to prove that this is indeed the worst case, but I did not attempt to do that.