2
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Your formula for $g_2$ does not seem right. $\endgroup$ – Dirk Aug 10 '17 at 8:02
  • $\begingroup$ If I understand correctly, you do not really need $f$ and the projection: you ask how fast do the inner products $\langle h_0, g_n\rangle$ go to zero, right? $\endgroup$ – Mateusz Kwaśnicki Aug 10 '17 at 12:55
  • $\begingroup$ @MateuszKwaśnicki not quite, since $\langle h_0,g_n\rangle =\delta_{0,n}$ but if we answer this question for $h_1$ as well, then I think we have it. Thank you for your remark, I will adapt the question accordingly. $\endgroup$ – Zinkin Aug 10 '17 at 14:31
  • $\begingroup$ @Zinkin: Although $\langle h_0, g_1\rangle$ is non-zero, $h_0$ is indeed not interesting. But so is $h_1$! I will write up an answer in a couple of minutes. By the way, $\langle h_0, h_1\rangle = \langle h_1, h_2\rangle$, if I understand correctly. $\endgroup$ – Mateusz Kwaśnicki Aug 10 '17 at 20:08
  • $\begingroup$ Of course I messed this up again, $\langle h_0, g_1\rangle = 0$. I was thinking about $\langle h_1, g_0\rangle$. Sorry. $\endgroup$ – Mateusz Kwaśnicki Aug 10 '17 at 20:19
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.