Name
Abstract | ||
|---|---|---|
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. And last, a group pattern in the magnitu... |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Numerical Analysis | Rank (linear algebra),Kernel (linear algebra),Clustering high-dimensional data,Mathematical optimization,Radial basis function,Radial basis function kernel,Mathematical analysis,Matrix (mathematics),Algorithm,Fourier series,Low-rank approximation,Mathematics |
DocType | Volume | Citations |
Journal | abs/1706.07883 | 1 |
PageRank | References | Authors |
0.36 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ruoxi Wang | 1 | 6 | 3.14 |
| Yingzhou Li | 2 | 2 | 1.04 |
| Eric Darve | 3 | 440 | 44.79 |