Efficient Estimation of Kernel Matrix Spectral Norm using Random Features

This paper proposes a new approach to accelerate spectral norm estimation for a kernel matrix of n data points. Our key intuition is that, by applying the seminal random feature technique, we can well estimate the norm without computing or operating on the n-by-n kernel matrix but only an n-by-q random feature matrix with q ≪ n features, thereby significantly reducing the estimation time from O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>) to O(nq).Technically, our analysis suggests the spectral norm of a kernel matrix can be approximated by that of its corresponding random feature matrix with an $\tilde O\left( {\ln n/\sqrt q } \right)$ relative norm approximation error. This is comparable to the relative norm estimation error of power iteration (PI), a popular efficient norm estimation method, and suggests our method can be integrated with PI to further accelerate norm estimation without deteriorating the estimation accuracy. Based on these insights, we design a random feature-based power iteration (RFPI) estimator for the kernel matrix spectral norm. Experimental results on two real-world datat sets show RFPI has significantly less estimation time than PI while maintaining competitive estimation accuracy.