# Computing the norm of the columns of an implicitly defined matrix

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?

-
Do you actually have $\Sigma$? –  Felix Goldberg May 10 '12 at 17:57
You want to compute $n$ quantities $\|M^i\|$, and you can only perform matrix-vector products. Would this mean, in principle, you cannot reduce the work significantly? –  timur May 10 '12 at 18:03
@felix yes, $\Sigma$ is explicit –  Giuseppe Ottaviano May 10 '12 at 18:52
So, if $y=Wx$ (which is available), then $Mx=\Sigma y$ and you can estimate $Mx$ directly. Too simple, right? What am I missing? –  Felix Goldberg May 10 '12 at 21:00
Ciao Giuseppe! Can you be more specific on the kind of bound that you are looking for? It can't be a bound of the kind $\leq C\left\Vert x \right\Vert$, otherwise you can forget about the orthogonal $W$ and focus on $\Sigma$ only. Right? –  Federico Poloni May 10 '12 at 21:46