A geometric note on subspace updates and orthogonal matrix decompositions under rank-one modifications

Abstract

In this work, we consider rank-one adaptations $X_{new}=X+a{b}^T$ of a given matrix $X\in {\mathbb{R}}^{n\times p}$ with known matrix factorization $X=UW$, where $U\in {\mathbb{R}}^{n\times p}$ is column-orthogonal, i.e. $U^{T}U=I$. Arguably the most important methods that produce such factorizations are the singular value decomposition (SVD), where $X=UW=U\Sigma V^T$, and the QR-decomposition, where $X=UW=QR$. An elementary approach to produce a column-orthogonal matrix $U_{new}$, whose columns span the same subspace as the columns of the rank-one modified $X_{new}=X+a{b}^T$ is via applying a suitable coordinate change such that in the new coordinates, the update affects a single column and subsequently performing a Gram-Schmidt step for reorthogonalization. This may be interpreted as a rank-one adaptation of the $U$-factor in the SVD or a rank-one adaptation of the $Q$-factor in the QR-decomposition, respectively, and leads to a decomposition for the adapted matrix $X_{new}=U_{new}{W}_{new}$. By using a geometric approach, we show that this operation is equivalent to traveling from the subspace $\mathcal{S}=\text{ran}(X)$ to the subspace ${\mathcal{S}}_{new}=\text{ran}(X_{new})$ on a geodesic line on the Grassmann manifold and we derive a closed-form expression for this geodesic. In addition, this allows us to determine the subspace distance between the subspaces $\mathcal{S}$ and ${\mathcal{S}}_{new}$ without additional computational effort. Both $U_{new}$ and $W_{new}$ are obtained via elementary rank-one matrix updates in $\mathcal{O}(np)$ time for $n\gg p$.

15 pages, 1 figure, MATLAB code

Cited by in corpus (3)

• On the Adversarial Robustness of Subspace Learning
• Error Analysis of an Incremental POD Algorithm for PDE Simulation Data
• A note on incremental POD algorithms for continuous time data