# Revisiting Memory Efficient Kernel Approximation: An Indefinite Learning Perspective

arXiv: https://arxiv.org/abs/2112.09893 · HTML: https://mlsanity.com/paper/2112.09893/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 56 references that are in the map.
- First posted on arXiv 18 Dec 2021.

## Builds on (most cited first, 5 of 5)

- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Metric and non-metric proximity transformations at linear costs](https://mlsanity.com/paper/1411.1646/) (2014)
- [TrIK-SVM : an alternative decomposition for kernel methods in Krein spaces](https://mlsanity.com/paper/1902.10569/) (2019)

## Abstract (arXiv)

Matrix approximations are a key element in large-scale algebraic machine learning approaches. The recently proposed method MEKA (Si et al., 2014) effectively employs two common assumptions in Hilbert spaces: the low-rank property of an inner product matrix obtained from a shift-invariant kernel function and a data compactness hypothesis by means of an inherent block-cluster structure. In this work, we extend MEKA to be applicable not only for shift-invariant kernels but also for non-stationary kernels like polynomial kernels and an extreme learning kernel. We also address in detail how to handle non-positive semi-definite kernel functions within MEKA, either caused by the approximation itself or by the intentional use of general kernel functions. We present a Lanczos-based estimation of a spectrum shift to develop a stable positive semi-definite MEKA approximation, also usable in classical convex optimization frameworks. Furthermore, we support our findings with theoretical considerations and a variety of experiments on synthetic and real-world data.