# Bounding the decrease after applying a contraction operator $n$ vs $n+1$ times

Can we upper bound the convergence rate of $$\max_{\textbf{v}: \left\Vert \textbf{v}\right\Vert_2=1} \left\{ \left\Vert \textbf{T}^n \textbf{v}\right\Vert^2_2 - \left\Vert \textbf{T}^{n+1} \textbf{v}\right\Vert^2_2 \right\}~,$$ where $$\textbf{T}\in \mathbb{R}^{d \times d}$$ is a contraction operator ($$\left\Vert\textbf{T}\right\Vert_2\le1$$) of rank $$r?

For example, $$\textbf{T}$$ can be nilpotent with index $$q$$ (e.g., $$\left[\begin{array}{cc} 0 & 1\\ 0 & 0 \end{array}\right]$$) and then the maximal decrease can be fixed as long as $$n, and afterwards it is $$0$$.

I found a Toeplitz operator whose rate is $$d/en$$: $$\boldsymbol{T}=\left[\begin{array}{ccccc} & 1\\ & & \ddots\\ & & & 1\\ 1-\epsilon \end{array}\right]$$ and I have an intuition this should be the upper bound, but I was not able to prove that this is indeed the worst case.

• I'll just say it's a simplification of another question I asked a few days ago which probably was too complicated. In essence, it's related to alternating projections but still different because, e.g., eigenvalues of $1$ do not make the objective here stay stuck on $1$.
– Itay
Nov 14, 2021 at 5:49
• Contraction means $\|T\|<1$? Which type of result do you need? Nov 14, 2021 at 7:54
• Added a clarification that I mean that the spectral norm <= 1. An example of a result that can be helpful is an upper bound of $r/n$.
– Itay
Nov 14, 2021 at 8:20
• I don't think that your result for nilpotent operators holds. For instance, $T = \begin{bmatrix}0 & 1/2\\ 0 & 0\end{bmatrix}$ is index-2 nilpotent, but the maximal decrease for $n=1$ is $1/2$, not $1$. Or do you want a maximum over all possible operators $T$ as well? Nov 14, 2021 at 11:39
• (As to k<r: then an orthogonal projector with v in its image). Nov 14, 2021 at 16:09

You can easily get a slightly cruder bound $$d/n$$ (or, if you want, $$r/n$$) as follows.
Let $$A_n=(T^*)^nT^n$$ and $$B_n=A_n-A_{n+1}$$. Then $$(B_nv,v)=\|T^nv\|^2-\|T^{n+1}v\|^2\ge 0$$, so $$B_n$$ is positive definite. Also $$B_{n+1}=T^*B_nT$$, so, since $$T$$ is a contraction, $$Tr B_{n+1}\le Tr B_n$$ (this is obvious if $$T$$ is diagonal but in general $$T=R_1DR_2$$ where $$R_j$$ are orthogonal and $$D$$ is a diagonal contraction and conjugation by an orthogonal matrix doesn't change either trace, or positive definiteness).
So, $$n\, Tr B_n\le \sum_{k=1}^n Tr B_k=Tr A_1-Tr A_{n+1}\le Tr A_1\le r$$ and we are done because the trace dominates the norm for positive definite matrices.