How to 'easily' obtain the quadratic form of an inverse?
x = $v^TA^{-1}\,v$
- $A$ is a symmetric invertible matrix of real numbers, it is also positive-definite and sparse.
- $v$ is a vector with few non-zero values.
-- It is too expensive to find the inverse.
-- To solve a single linear system is ok, but I need to find $x$ for many different vectors $v$, so solving $A\,y=v$ is not a viable solution.
-- Since there are few non-zero values in $v$: $A\,v$ , $v^Tv$ and $v^TA\,v$ can be obtained very easily.
In the specific situation where
$[\,v\,v^T]\,A = A\,[\,v\,v^T]$
we would have:
$x\,v^TA\,v = v^TA^{-1}\,v\,v^TA\,v = v^TA^{-1}A\,v\,v^Tv = v^Tv\,v^Tv \Rightarrow \boxed{x = \frac{(v^Tv)^2}{v^TA\,v}}$
This made me think that maybe there is some similar expression for a general case (without the commutative property).
Question: Is there a better way to write $x$?
Suppose you want to compute $x_i$ for each of $n$ different vectors $v_i$. If $A$ is $m \times m$, the naive apprach would take $O(n m^3)$ time. However, you can compute the Cholesky decomposition $A=LL^T$ in $O(m^3)$ time once, then solve the triangular system $L^T y_i = v_i$ in $O(m^2)$ time, then compute $x_i = y_i^T y_i$ in $O(m)$ time, for a total running time of $O(n m^2 + m^3)$; this is significant when $n$ is large.
If $A$ is sparse, good Cholesky solvers will give sparse factors, and this computation can be quite fast: on my laptop, using cholmod through python I can compute the cholesky decomposition of a random one million by one million matrix with ~two million nonzero entries in just under a second, and given the factorization can compute $x$ for a dense vector $v$ in about 20 ms. If $n$ is large enough, you probably won't beat this approach for speed.
There are other decompositions you could use (an LDL decomposition often has better numerical stability, and the SVD might make sense if your matrix is low rank), but in general you cannot compute $v^T A^{-1} v$ without computing some kind of decomposition.