  Low-rank approximations are popular methods to reduce the high computational
cost of algorithms involving large-scale kernel matrices. The success of
low-rank methods hinges on the matrix rank of the kernel matrix, and in
practice, these methods are effective even for high-dimensional datasets. Their
practical success motivates our analysis of the function rank, an upper bound
of the matrix rank. In this paper, we consider radial basis functions (RBF),
approximate the RBF kernel with a low-rank representation that is a finite sum
of separate products and provide explicit upper bounds on the function rank and
the $L_\infty$ error for such approximations. Our three main results are as
follows. First, for a fixed precision, the function rank of RBFs, in the worst
case, grows polynomially with the data dimension. Second, precise error bounds
for the low-rank approximations in the $L_\infty$ norm are derived in terms of
the function smoothness and the domain diameters. Finally, a group pattern in
the magnitude of singular values for RBF kernel matrices is observed and
analyzed, and is explained by a grouping of the expansion terms in the kernel's
low-rank representation. Empirical results verify the theoretical results.
