Efficiently compute matrix vector product $\mathbf{A} \mathbf{b}$ given product $\mathbf{A} \mathbf{c}$ with same matrix but different vector

Question

Suppose I have a matrix $\mathbf{A}$, and a vector $\mathbf{b}$, and wish to compute the matrix-vector product $\mathbf{A} \mathbf{b}$.

If I have already previously computed the product $\mathbf{A} \mathbf{c}$ between the same matrix $\mathbf{A}$, but a different vector $\mathbf{c}$, is it possible to use that already-computed result $\mathbf{A} \mathbf{c}$ in some way to make the computation of $\mathbf{A} \mathbf{b}$ more efficient?

---

In my specific case, the matrix $\mathbf{A}$ happens to have the following special properties, which I suppose may or may not help:

• $\mathbf{A}$ is a square matrix.
• $\mathbf{A}$ itself is constructed in a special way: it is the product of the differences between the identity matrix $\mathbf{I}$ and multiple other matrices, e.g. $\mathbf{A} = (\mathbf{I} - \mathbf{X})(\mathbf{I} - \mathbf{Y})(\mathbf{I} - \mathbf{Z}) \dots$ for a sequence of (square) matrices $\mathbf{X}$, $\mathbf{Y}$, $\mathbf{Z}$, $\dots$.
• The matrices mentioned above ($\mathbf{X}$, $\mathbf{Y}$, $\mathbf{Z}$, $\dots$) are symmetric matrices (each of those is constructed as the outer product of an arbitrary vector with itself).

Answer 1

Depends on whether you have a fast way of computing $\mathbf A (\mathbf c - \mathbf b)$. For instance, if $\mathbf b$ and $\mathbf c$ only differ in a few elements, computing an update would be cheaper. Or if $\mathbf c - \mathbf b$ lies in the null space of $\mathbf A$. In general, this is not necessarily the case and $\mathbf A \mathbf c$ might as well help you nothing.

That said, your special structure in $\mathbf A$ might help to come up with a fast multiplier. You write that your $\mathbf A$ is a product of terms like $\mathbf I - \mathbf u \mathbf u^{\rm T}$. Note that $$\left(\mathbf I - \mathbf u \mathbf u^{\rm T}\right) \cdot \mathbf c = \mathbf c - \mathbf u (\mathbf u^{\rm T} \mathbf c),$$ which requires only one (inner) vector product. For two terms, you get $$\left(\mathbf I - \mathbf v \mathbf v^{\rm T}\right)\left(\mathbf I - \mathbf u \mathbf u^{\rm T}\right) \cdot \mathbf c = \left(\mathbf I - \mathbf v \mathbf v^{\rm T}\right)\left(\mathbf c - \mathbf u \mathbf u^{\rm T} \mathbf c\right) = \mathbf c - \mathbf v (\mathbf v^{\rm T} \mathbf c - \mathbf v^{\rm T} \mathbf u \mathbf u^{\rm T} \mathbf c) - \mathbf u (\mathbf u^{\rm T} \mathbf c),$$ which requires only the inner products between $\mathbf v, \mathbf u$, and $\mathbf c$ (where $\mathbf v^{\rm T} \mathbf u$ can be precalculcated). So if your $M \times M$ matrix is comprised of the product of $L < M$ of these terms, you get away with $L$ inner products instead of $M$ that the full matrix would require.