Approximating $v^TH^{-1}v$ by assuming $v$ is an eigenvector

Question

I have to compute $v^TH^{-1}v$ where $H$ is a very big matrix (which is a Hessian, thus symmetric and positive-definite). It occurred to me that I can do an approximation by assuming $v$ is an eigenvector of $H$ and then $v^TH^{-1}v\approx\frac{|v|^4}{v^THv}$, bypassing the matrix inversion. This uses the fact that if $v$ has eigenvalue $\lambda$ for $H$ it has eigenvalue $1/\lambda$ for $H^{-1}$, then: $v^TH^{-1}v=\frac{|v|^2}{\lambda}=\frac{|v|^2}{(v/|v|)^TH(v/|v|)}=\frac{|v|^4}{v^THv}$.

Is this approximation reasonable? If so, does it have a name? When is it good/bad compared to assuming a diagonal H?

Answer 1

You can write $v=\sum_{i} a_i v_i$ where $v_i$ are eigenvector of $H$ (and in particular orthonormal) with corresponding eigenvalue $\lambda_i$. It is known that $Hv_i=\lambda_i v_i$ and $H^{-1}v_i= H^{-1} \frac{H v_i}{\lambda_i}=\frac 1 {\lambda_i} H^{-1}H v_i=\frac{1}{\lambda_i} v_i$. We also know that $v_i^T v_j=1(i=j)$. Putting all that thogether \begin{align*} v^T H^{-1} v &=\sum_j\sum_i a_i a_j v_j^TH^{-1} v_i\\ &=\sum_j\sum_i \frac{a_i a_j}{\lambda_i} v_j^T v_i\\ &=\sum_i \frac{a_i^2}{\lambda_i}\\ \end{align*} which may help you do your estimation. In particular if you keep only eigen vector, you will keep exactly one term of this sum, you may want to keep the one for which $\frac{a_i^2}{\lambda_i}$ is the biggest (this is in the spirit of what @user619894 is suggesting but puts a value on the notion of being "close"). The more terms you include the better it gets.

Answer 2

[Building on a comment by @user619894 and especially on @P.Quinton's answer].

TLDR: it is a well-defined estimate in the sense that it correlates with the true answer in an understandable way. It also never over-estimates the result. Its error will be big when the vector has significant components in directions of widely different eigenvalues.

Derivation Because $H$ is symmetric and positive definite we know that it decomposes in an orthonormal basis $v_i$ with eigenvalues $\lambda_i>0$; i.e. $Hv_i=\lambda_i,H^{-1}v_i=\frac{1}{\lambda_i}, v_i^Tv_j=1(i=j)$.

Let's express $v=\sum_ia_iv_i$. Then the true answer is: $$\text{Answer} = v^THv = \sum_{i,j}a_ia_jv_j^TH^{-1}v_i = \sum_{i,j} \frac{a_ia_j}{\lambda_i} v_j^Tv_i = \sum_i \frac{a_i^2}{\lambda_i}.$$ Of course, we don't know the true answer because we don't know $\lambda_i$nor $a_i$. But we can look at the estimate as a function of both and see how they differ:

$$\text{Estimate} = \frac{|v|^4}{v^THv} = \frac{\left(\sum_ia_i^2\right)^2}{\sum_ia_i^2\lambda_i}.$$

Now we can look at the ratio: $$\frac{\text{Estimate}}{\text{Answer}} = \frac{\left(\sum_ia_i^2\right)^2}{\left(\sum_ia_i^2\lambda_i\right)\left(\sum_i \frac{a_i^2}{\lambda_i}\right)} = \frac{\sum_i a_i^2}{\sum_ia_i^2\lambda_i}\cdot\frac{\sum_i a_i^2}{\sum_i a_i^2\frac{1}{\lambda_i}} = \frac{\text{ Harmonic average of $\lambda_i$ weighted by }a_i^2}{\text{Arithmetic average of $\lambda_i$ weighted by }a_i^2}.$$

It is well-known that for $\lambda_i>0$ the harmonic mean is always less than or equal to the arithmetic mean. Thefore, the estimate will always be an under-estimate. Furthermore, the approximation will be worse the more diverse the $\lambda_i$ are (with significant $a_i$ component for $v$). Intuitively, the inverse cares more about the smallest eigenvalues.