The spectral norm error of the naive Nystrom extension

Abstract

The naive Nystrom extension forms a low-rank approximation to a positive-semidefinite matrix by uniformly randomly sampling from its columns. This paper provides the first relative-error bound on the spectral norm error incurred in this process. This bound follows from a natural connection between the Nystrom extension and the column subset selection problem. The main tool is a matrix Chernoff bound for sampling without replacement.

1 figure

References in corpus (2)

• Sparsity and Incoherence in Compressive Sampling
• Spectral approximations in machine learning

Cited by in corpus (21)

• Recursive Sampling for the Nyström Method
• Sharp analysis of low-rank kernel matrix approximations
• Matrix concentration inequalities via the method of exchangeable pairs
• Revisiting the Nystrom Method for Improved Large-Scale Machine Learning
• A Practical Guide to Randomized Matrix Computations with MATLAB Implementations
• On the Power of Adaptivity in Matrix Completion and Approximation
• Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
• Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
• Fast and stable randomized low-rank matrix approximation
• Scalable Kernel Clustering: Approximate Kernel k-means
• Massively scalable Sinkhorn distances via the Nyström method
• An Explicit Sampling Dependent Spectral Error Bound for Column Subset Selection
• Efficient Algorithms and Error Analysis for the Modified Nystrom Method
• Improved matrix algorithms via the Subsampled Randomized Hadamard Transform
• On Column Selection in Approximate Kernel Canonical Correlation Analysis
• Faster Subset Selection for Matrices and Applications
• SketchyCoreSVD: SketchySVD from Random Subsampling of the Data Matrix
• Concentration for matrix martingales in continuous time and microscopic activity of social networks
• Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
• Active Algorithms For Preference Learning Problems with Multiple Populations
• Stability of Sampling for CUR Decompositions