3
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Do you actually have $\Sigma$? $\endgroup$ May 10, 2012 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – timur
    May 10, 2012 at 18:03
  • $\begingroup$ @felix yes, $\Sigma$ is explicit $\endgroup$ May 10, 2012 at 18:52
  • 1
    $\begingroup$ So, if $y=Wx$ (which is available), then $Mx=\Sigma y$ and you can estimate $Mx$ directly. Too simple, right? What am I missing? $\endgroup$ May 10, 2012 at 21:00
  • $\begingroup$ 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? $\endgroup$ May 10, 2012 at 21:46

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.