I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).

I need to compute the norms $\|M^i\|$ of the columns of $M$ so that I can use them to find an upper bound on $\|Mx\|$ for a given vector $x$.

Of course I can compute $\|M e_i\|$ for all $i$, but this would require $n$ matrix-vector products.

An alternative would be to compute the diagonal of $M^T M = W^T \Sigma^2 W$. I found this paper which shows how to estimate the diagonal of a matrix using only a small number of matrix-vector products with random vectors, but it is still in the order of hundreds, if not worse (and the result is approximate).

Is there a way to exploit the structure of my matrix to obtain a more efficient solution?