@LSpice, looking at a polynomial as an element of $\mathcal{C}[0, 1]$, we can represent it in a given (different) basis (as series). By finite rank I mean finite series expansion in that basis.

@NateEldredge, thanks for pointing out. I'll update the question.

@AmirSagiv, I'm interested in either and the relationship to the basis choice.

Thanks. In fact, there are matrix-matrix multiplications ($p \times r$ and $q \times r$ with $r \times r$) that are necessary to construct new orthonormal subspace matrices. If one wants to update singular values only, you are right, the time complexity would be $O(r(p+q+r))$.

Thanks for spotting this. I double checked and it's indeed $O(r^2 + p + q)$ given that all the data is already in memory. The $O(p + q)$ term comes from a couple of vector-to-matrix multiplications.