Speaker
Description
In this talk we discuss various computational aspects of determining all singular triplets $\{\sigma_j, u_j, v_j\}$ corresponding to singular values of $A$ above a user-specified threshold parameter $sigma$, or in other words, determining a $k$-PSVD of $A$ such that $\sigma_k \geq sigma$ and $\sigma_{k+1} < sigma$. While various numerical schemes with publicly available software have been developed for finding an approximate $k$–PSVD of a large sparse matrix, e.g., PROPACK, ${\tt irlba}$, ${\tt primme\_svds}$, ${\tt rsvd}$, and MATLAB’s ${\tt svds}$, their use is somewhat limited in this context as they all require knowing the number of desired singular triplets, $k$, in advance.
We propose a hybrid algorithm that works directly on $A$ and is based on the explicit deflation procedure applied to Golub-Kahan-Lanczos Bidiagonalization (GKLB)-based methods. An important feature of GKLB-methods that is relevant here is that they can be thought of as a one–sided PSVD approximations of $A$ -- this allows for the explicit deflation technique to be applied only to either the left or right singular vectors of $A$, depending on its dimensions, and thus significantly reducing the overall computational cost. Due to iterative deflation process, a modest non–zero error is added to the side in the GKLB method that had theoretically zero error. Although this error growth is theoretically manageable, our numerical experiments showed that at times one has to restore the one–sided GKLB structure which we have achieved by combining the GKLB-based method with a variant of the block SVD power method. Implementations of this algorithm are provided in MATLAB and a widely used statistical software ${\sf R}$ along with alternative thresholding criteria based on the notions of energy and the normalized root mean squared error.