/SVDUpdate.jl

Primary LanguageJuliaMIT LicenseMIT

SVDUpdate

Stable Dev Build Status Coverage Code Style: Blue

#Overview This is a package based on the algorithm/identities created by Brand in the paper "Fast Low Rank Modifications of the Thin Singular Value Decomposition," accessible by the following link: https://www.sciencedirect.com/science/article/pii/S0024379505003812

The outline is as follows:

Given some matrix $X\in R^{mxn}$, computing the svd of the matrix is an expensive, an $O(n^3)$ operation for an n by n matrix. Suppose we already have the singular value decomposition $X=U\Sigma V^{H}$. Suppose we make some additive modification to the original matrix X, such as: $$X+AB^{H}$$ Here, $A\in R^{mxq}$, and $B\in^{nxq}$ If we wish to compute the svd of this new matrix, Brand's paper gives an identity/formula to compute the $U,\Sigma, V$ matrices without actually having to use the svd function on the matrix $X+AB^H$. Our function svdupdate() uses Brand's formula/algorithm to approximate the svd of the new matrix $X+AB^H$, given the svd of $X$.

#How to use the Function Given three matrices $X\in R^{mxn}$, $A\in R^{mxq}$, $B\in^{nxq}$, the following operation will return an SVD object of $X+AB^H$

svdupdate(svd(X),A,B)