Sketched Column-based Matrix Approximation

A new, practical algorithm, fast Sketched Columnbased Matrix Approximation (fSCMA), is proposed for low–rank matrix approximation. fSCMA leverages randomly, but fully sampled columns combined with structural side information, to achieve efficient and accurate approximations. The algorithm leverages both matrix sketching and side information to reduce complexity. A theoretical spectral bound on the reconstruction error is derived, improving the error bound by a factor of <italic xmlns:mml="http:/