A Singular Value Decomposition Updating Algorithm for Subspace Tracking

In this paper, the well-known QR updating scheme is extended to a similar but more versatile and generally applicable scheme for updating the singular value decomposition (SVD). This is done by supplementing the QR updating with a Jacobi-type SVD procedure, where apparently only a few SVD steps after each QR update suffice in order to restore an acceptable approximation for the SVD. This then results in a reduced computational cost, comparable to the cost for merely QR updating.The usefulness of such an approximate updating scheme when applied to subspace tracking is examined. It is shown how an $\mathcal{O}(n^2 )$ SVD updating algorithm can restore an acceptable approximation at every stage, with a fairly small tracking error of approximately the time variation in $\mathcal{O}(n)$ time steps.Finally, an error analysis is performed, proving that the algorithm is stable, when supplemented with a Jacobi-type reorthogonalization procedure, which can easily be incorporated into the updating scheme. In this paper, the well-known QR updating scheme is extended to a similar but more versatile and generally applicable scheme for updating the singular value decomposition (SVD). This is done by supplementing the QR updating with a Jacobi-type SVD procedure, where apparently only a few SVD steps after each QR update suffice in order to restore an acceptable approximation for the SVD. This then results in a reduced computational cost, comparable to the cost for merely QR updating.The usefulness of such an approximate updating scheme when applied to subspace tracking is examined. It is shown how an $\mathcal{O}(n^2 )$ SVD updating algorithm can restore an acceptable approximation at every stage, with a fairly small tracking error of approximately the time variation in $\mathcal{O}(n)$ time steps.Finally, an error analysis is performed, proving that the algorithm is stable, when supplemented with a Jacobi-type reorthogonalization procedure, which can easily be incorporated into the updating scheme.