The book I am reading is suggesting the following:
Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(n)} w$ is more complex in terms of space complexity than some trick which they use in order to create an expression of the form $$\sum_{j=1}^{P(n)} \langle v, U_1x_j\rangle \langle v, U_2x_j\rangle, \ldots, \langle v, U_{P(n)}x_j\rangle$$ for some vectors $x_j$.
Basically they say that $\langle v, U_1U_2\ldots U_{P(n)}w\rangle$ is not linear in space, as opposed to the same expression written this way by adding many $x$ vectors which render the expression equal but written differently as above.
How come the latter is better than the former? In both of them you have a vector which has to be stored in memory. They claim that in the latter you just add to the running total. But inside the inner product you still have to store a vector just the size of the first method. What's the difference?
