SPSD Matrix Approximation vis Column Selection: Theories, Algorithms, and Extensions

Abstract

Symmetric positive semidefinite (SPSD) matrix approximation is an important problem with applications in kernel methods. However, existing SPSD matrix approximation methods such as the Nyström method only have weak error bounds. In this paper we conduct in-depth studies of an SPSD matrix approximation model and establish strong relative-error bounds. We call it the prototype model for it has more efficient and effective extensions, and some of its extensions have high scalability. Though the prototype model itself is not suitable for large-scale data, it is still useful to study its properties, on which the analysis of its extensions relies. This paper offers novel theoretical analysis, efficient algorithms, and a highly accurate extension. First, we establish a lower error bound for the prototype model and improve the error bound of an existing column selection algorithm to match the lower bound. In this way, we obtain the first optimal column selection algorithm for the prototype model. We also prove that the prototype model is exact under certain conditions. Second, we develop a simple column selection algorithm with a provable error bound. Third, we propose a so-called spectral shifting model to make the approximation more accurate when the eigenvalues of the matrix decay slowly, and the improvement is theoretically quantified. The spectral shifting method can also be applied to improve other SPSD matrix approximation models.

Journal of Machine Learning Research, 2016

References in corpus (2)

• Randomized Nonlinear Component Analysis
• Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition

Cited by in corpus (12)

• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• GIANT: Globally Improved Approximate Newton Method for Distributed Optimization
• Ultra-Fast Accurate AoA Estimation via Automotive Massive-MIMO Radar
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
• Robust Frequent Directions with Application in Online Learning
• Communication-Efficient Distributed SVD via Local Power Iterations
• Sketchy Empirical Natural Gradient Methods for Deep Learning
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• Fast Generalized Matrix Regression with Applications in Machine Learning
• Learning Data-adaptive Nonparametric Kernels