7
$\begingroup$

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


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<q$, 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.

$\endgroup$
13
  • $\begingroup$ 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$. $\endgroup$
    – Itay
    Nov 14, 2021 at 5:49
  • 2
    $\begingroup$ Contraction means $\|T\|<1$? Which type of result do you need? $\endgroup$ Nov 14, 2021 at 7:54
  • $\begingroup$ 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$. $\endgroup$
    – Itay
    Nov 14, 2021 at 8:20
  • 1
    $\begingroup$ 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? $\endgroup$ Nov 14, 2021 at 11:39
  • 1
    $\begingroup$ (As to k<r: then an orthogonal projector with v in its image). $\endgroup$ Nov 14, 2021 at 16:09

1 Answer 1

5
+50
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Wow! That is a very clean proof. Thank you. $\endgroup$
    – Itay
    Nov 18, 2021 at 11:30

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.