# Nonlinear Matrix Approximation with Radial Basis Function Components

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 3 Jun 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [The Marginal Value of Adaptive Gradient Methods in Machine Learning](https://mlsanity.com/paper/1705.08292/) (2017)
- [Structure Discovery in Nonparametric Regression through Compositional Kernel Search](https://mlsanity.com/paper/1302.4922/) (2013)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration](https://mlsanity.com/paper/1807.06766/) (2018)
- [Beyond Lazy Training for Over-parameterized Tensor Decomposition](https://mlsanity.com/paper/2010.11356/) (2020)
- [Behavior of Accelerated Gradient Methods Near Critical Points of Nonconvex Functions](https://mlsanity.com/paper/1706.07993/) (2017)
- [Prediction of Atomization Energy Using Graph Kernel and Active Learning](https://mlsanity.com/paper/1810.07310/) (2018)

## Abstract (arXiv)

We introduce and investigate matrix approximation by decomposition into a sum of radial basis function (RBF) components. An RBF component is a generalization of the outer product between a pair of vectors, where an RBF function replaces the scalar multiplication between individual vector elements. Even though the RBF functions are positive definite, the summation across components is not restricted to convex combinations and allows us to compute the decomposition for any real matrix that is not necessarily symmetric or positive definite. We formulate the problem of seeking such a decomposition as an optimization problem with a nonlinear and non-convex loss function. Several modern versions of the gradient descent method, including their scalable stochastic counterparts, are used to solve this problem. We provide extensive empirical evidence of the effectiveness of the RBF decomposition and that of the gradient-based fitting algorithm. While being conceptually motivated by singular value decomposition (SVD), our proposed nonlinear counterpart outperforms SVD by drastically reducing the memory required to approximate a data matrix with the same L2 error for a wide range of matrix types. For example, it leads to 2 to 6 times memory save for Gaussian noise, graph adjacency matrices, and kernel matrices. Moreover, this proximity-based decomposition can offer additional interpretability in applications that involve, e.g., capturing the inner low-dimensional structure of the data, retaining graph connectivity structure, and preserving the acutance of images.