Row-Aware Randomized SVD With Applications

The randomized singular value decomposition proposed in [28] has certainly become one of the most well-established randomization-based algorithms in numerical linear algebra. The key ingredient of the entire procedure is the computation of a subspace which is close to the column space of the target matrix (Formula presented.), (Formula presented.), up to a certain probabilistic confidence. In this paper, we employ a modification to the standard randomized SVD procedure, which leads, in general, to better approximations to (Formula presented.) at the same computational cost. To this end, we explicitly construct information from the row space of (Formula presented.), enhancing the quality of the approximation for which we derive novel error bounds that improve over existing results. We also observe that very few pieces of information from (Formula presented.) may be necessary. We thus design a variant of this algorithm equipped with a subsampling step, which increases the efficiency of the procedure while often attaining competitive accuracy records. Our findings are supported by both theoretical analysis and numerical results.