Sketched Column-based Matrix Approximation

A new, practical algorithm, fast Sketched Column-based Matrix Approximation (fSCMA), is proposed for low-rankmatrix approximation. fSCMA leverages randomly, but fullysampled columns combined with structural side information, toachieve efficient and accurate approximations. The algorithmleverages both matrix sketching and side information to reducecomplexity. A theoretical spectral bound on the reconstructionerror is derived, improving the error bound by a factor of n(in terms of key parameters) compared to state-of-the-art algo-rithms (SoTA). Experimental results on synthetic data demon-strate that fSCMA achieves competitive performance relative toSoTA, validating theoretical bounds, while significantly reducingcomputational complexity. Additionally, fSCMA shows strongimprovement over prior methods when applied to real data.