Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?

Cameron Musco, David P. Woodruff

Type: Article

Publication Date: 2017-11-01

Citations: 5

Locations

Neural Information Processing Systems - View

Similar Works

Action	Title	Year	Authors
+	Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?	2017	Cameron Musco David P. Woodruff
+	An $N \log N$ Parallel Fast Direct Solver for Kernel Matrices	2017	Chenhan D. Yu William B. March George Biros
+	An $N \log N$ Parallel Fast Direct Solver for Kernel Matrices	2017	Chenhan D. Yu William B. March George Biros
+	Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach	2022	Difeng Cai Edmond Chow Yuanzhe Xi
+	Structured Block Basis Factorization for Scalable Kernel Matrix Evaluation.	2015	Ruoxi Wang Yingzhou Li Michael W. Mahoney Eric Darve
+	Linear Time Kernel Matrix Approximation via Hyperspherical Harmonics	2022	John Paul Ryan Anil Damle
+ PDF Chat	An N log N Parallel Fast Direct Solver for Kernel Matrices	2017	Chenhan D. Yu William B. March George Biros
+ PDF Chat	On the Numerical Rank of Radial Basis Function Kernels in High Dimensions	2018	Ruoxi Wang Yingzhou Li Eric Darve
+ PDF Chat	Kernel Approximation on Algebraic Varieties	2023	Jason M. Altschuler Pablo A. Parrilo
+	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices	2017	Cameron Musco David P. Woodruff
+	Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices	2017	Cameron Musco David P. Woodruff
+	Kernel approximation on algebraic varieties	2021	Jason M. Altschuler Pablo A. Parrilo
+	Improved Algorithms for Low Rank Approximation from Sparsity	2021	David P. Woodruff Taisuke Yasuda
+ PDF Chat	Parametric kernel low-rank approximations using tensor train decomposition	2024	Abraham Khan Arvind K. Saibaba
+	Input-Sparsity Low Rank Approximation in Schatten Norm	2020	Yi Li David P. Woodruff
+	Input-Sparsity Low Rank Approximation in Schatten Norm	2020	Yi Li David P. Woodruff
+ PDF Chat	Data‐driven linear complexity low‐rank approximation of general kernel matrices: A geometric approach	2023	Difeng Cai Edmond Chow Yuanzhe Xi
+	Provably Useful Kernel Matrix Approximation in Linear Time.	2016	Cameron Musco Christopher Musco
+	Sublinear Time Numerical Linear Algebra for Structured Matrices	2019	Xiaofei Shi David P. Woodruff
+	Faster Kernel Matrix Algebra via Density Estimation	2021	Artūrs Bačkurs Piotr Indyk Cameron Musco Tal Wagner

Works That Cite This (5)

Action	Title	Year	Authors
+	The GaussianSketch for Almost Relative Error Kernel Distance	2018	Jeff M. Phillips Wai Ming Tai
+ PDF Chat	Retraining-free methods for fast on-the-fly pruning of convolutional neural networks	2019	Amir H. Ashouri Tarek S. Abdelrahman Alwyn Dos Remedios
+	Statistical and Computational Trade-Offs in Kernel K-Means	2019	Daniele Calandriello Lorenzo Rosasco
+	Impossibility Results for Grammar-Compressed Linear Algebra	2020	Amir Abboud Artūrs Bačkurs Karl Bringmann Marvin Künnemann
+ PDF Chat	Generalized Leverage Score Sampling for Neural Networks	2020	Jason D. Lee Ruoqi Shen Zhao Song Mengdi Wang Zheng Yu

Works Cited by This (0)

Action	Title	Year	Authors