Find difference of product of binary vector to binary matrix after fliping one bit in the vector.

Question

We have: $E1=x*W*x^{T}\\ Delta = E1 - x_{new} * W * x_{new}^{T}$ where $x_{new}$ is the $x$ vector with 1 bit flipped from 1 to -1 or the other way. Is there a way to find $Delta$ without having to recalculate the matrix multiplications? All the values in $W$ and $x$ are either 1 or -1 and the diagonal of $W$ is zero.

Answer 1

Assuming $W$ symmetic:

Let $x$ and $y$ denote the vectors you've called $x$ and $x_{new}$. Let $u$ denote $x - y$, which is all zeros except a single $\pm 2$ in some location $j$. Use primes to denote transposes.

$$ u' A u = x'Ax - 2x' A y + y' A y $$ The left hand side is just $4 \cdot a_{jj}$. The first term on the RHS is known. Let's continue $$ u' A u = x'Ax - 2x' A y + y' A y\\ u'Au - x'Ax + 2x' A y = y' A y\\ u'Au + x'Ax - 2x'Ax + 2x' A y = y' A y\\ u'Au + x'Ax + 2x'A(y-2x) = y' A y $$ The first term is easy, as noted; the second is known. Half the third is $$ x' A (y - 2x) = x'A (u-x) = x'Au - x'Ax $$ so we can write $$ u'Au + x'Ax + 2x'A(y-2x) = y' A y\\ u'Au + x'Ax + 2x'Au - 2x'A'x = y' A y\\ u'Au - x'Ax + 2x'Au = y' A y\\ $$ Now the third term is $2x'$ times the product of $A$ with $\pm 2 e_j$, i.e., it's just $\pm 4 x' c$, where $c$ is the $j$th column of $A$.

For an $n \times n$ matrix $A$, this saves you a factor of $n$ in computation.

(I'm sure there's a simpler algebraic way to get here, but I leave that to you.)