Tighter low-rank approximation via sampling the leveraged element

摘要: In this work, we propose a new randomized algorithm for computing low-rank approximation to given matrix. Taking an approach different from existing literature, our method first involves specific biased sampling, with element being chosen based on the leverage scores of its row and column, then weighted alternating minimization over factored form intended matrix, minimize error only these samples. Our can input sparsity, yet produce approximations in spectral (as opposed weaker Frobenius) norm; combines best aspects otherwise disparate current results, but dependence condition number κ = σ1/σr. particular require O(nnz(M)+nκ2r5/e2) computations generate rank-r M norm. contrast, requires O(nnz(M)+nr2/e4) time compute Frobenius Besides tightness norm, have better e. is naturally highly parallelizable.Our enables two extensions that are interesting their own. The directly (in efficient form) product matrices; it computes small random set entries product, executes before) these. sampling strategy because now cannot access matrix (but instead work matrices). second extension improved smaller communication complexity distributed PCA setting (where each server has rows want low rank amount other servers).