For cubic SKI the inducing-point count should grow as n^{d/3}; the advertised linear-time regime d≤3 is incorrect because at d=3 the paper's own inequality forces error to grow with n.
Entrywise error bounds for low-rank approximations of kernel matrices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
In this paper, we derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition (or singular value decomposition). While this approximation is well-known to be optimal with respect to the spectral and Frobenius norm error, little is known about the statistical behaviour of individual entries. Our error bounds fill this gap. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues, which takes inspiration from the field of Random Matrix Theory. Finally, we validate our theory with an empirical study of a collection of synthetic and real-world datasets.
citation-role summary
background 1
citation-polarity summary
fields
cs.LG 1years
2025 1verdicts
REJECT 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
The Price of Linear Time: Error Analysis of Structured Kernel Interpolation
For cubic SKI the inducing-point count should grow as n^{d/3}; the advertised linear-time regime d≤3 is incorrect because at d=3 the paper's own inequality forces error to grow with n.