Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition

Abstract

Symmetric positive semi-definite (SPSD) matrix approximation methods have been extensively used to speed up large-scale eigenvalue computation and kernel learning methods. The standard sketch based method, which we call the prototype model, produces relatively accurate approximations, but is inefficient on large square matrices. The Nyström method is highly efficient, but can only achieve low accuracy. In this paper we propose a novel model that we call the {\it fast SPSD matrix approximation model}. The fast model is nearly as efficient as the Nyström method and as accurate as the prototype model. We show that the fast model can potentially solve eigenvalue problems and kernel learning problems in linear time with respect to the matrix size $n$ to achieve $1+\epsilon$ relative-error, whereas both the prototype model and the Nyström method cost at least quadratic time to attain comparable error bound. Empirical comparisons among the prototype model, the Nyström method, and our fast model demonstrate the superiority of the fast model. We also contribute new understandings of the Nyström method. The Nyström method is a special instance of our fast model and is approximation to the prototype model. Our technique can be straightforwardly applied to make the CUR matrix decomposition more efficiently computed without much affecting the accuracy.

Journal of Machine Learning Research 2016

References in corpus (3)

• SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions
• OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings
• Multi-Scale Link Prediction

Cited by in corpus (10)

• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Randomized Nonnegative Matrix Factorization
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
• SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions
• Efficient Data-Driven Geologic Feature Detection from Pre-stack Seismic Measurements using Randomized Machine-Learning Algorithm
• Fast Generalized Matrix Regression with Applications in Machine Learning
• Quantum Machine Learning For Classical Data
• NoisyCUR: An algorithm for two-cost budgeted matrix completion