0
$\begingroup$

Let $H$ be a symmetric matrix over $\mathbb R^n$. Given some vector $u$, I would like to express $u$ in the eigenbasis for $H$. Can this be done efficiently, perhaps using some kind of iterative method? I know there are iterative methods for computing the eigenbasis itself, but computing the entire eigenbasis would represent quadratically more data than I actually need ($n^2$ reals rather than only $n$), so I was hoping I might be able to get a speed up by using a more targeted method.

I only have implicit access to $H$ - i.e. I can compute matrix-vector products $Hx$. I would like to avoid having to actually compute $H$ if possible, although I would be happy with anything faster than computing $H$ and then diagonalizing it directly.

Improve this question
$\endgroup$
6
  • $\begingroup$ Of course, having access to matrix–vector products $H x$ gives access to the entries of $H$ via $H_{i j} = \langle e_i, H e_j\rangle$. (It's needless to say in this audience, but I do wonder what limitation is expressed by requiring that you access $H$ only in this way.) $\endgroup$
    – LSpice
    Commented Sep 1, 2021 at 23:28
  • 1
    $\begingroup$ @LSpice Yes. I suppose "avoiding computing $H$" means something like computing only sub-linearly many matrix-vector products, which does seem like quite a big ask. $\endgroup$
    – Jack M
    Commented Sep 1, 2021 at 23:29
  • $\begingroup$ The eigenvalues are not given? Can there be multiple eigenvalues? $\endgroup$
    – markvs
    Commented Sep 2, 2021 at 2:58
  • $\begingroup$ @MarkSapir $H$ is positive semi-definite, is the only information we have about the eigenvalues. $\endgroup$
    – Jack M
    Commented Sep 2, 2021 at 10:36
  • $\begingroup$ so is it symmetric of positive semidef? $\endgroup$
    – markvs
    Commented Sep 2, 2021 at 17:58

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .