Analytical low-rank compression via proxy point selection
From MaRDI portal
Abstract: It has been known in potential theory that, for some kernels matrices corresponding to well-separated point sets, fast analytical low-rank approximation can be achieved via the use of proxy points. This proxy point method gives a surprisingly convenient way of explicitly writing out approximate basis matrices for a kernel matrix. However, this elegant strategy is rarely known or used in the numerical linear algebra community. It still needs clear algebraic understanding of the theoretical background. Moreover, rigorous quantifications of the approximation errors and reliable criteria for the selection of the proxy points are still missing. In this work, we use contour integration to clearly justify the idea in terms of a class of important kernels. We further provide comprehensive accuracy analysis for the analytical compression and show how to choose nearly optimal proxy points. The analytical compression is then combined with fast rank-revealing factorizations to get compact low-rank approximations and also to select certain representative points. We provide the error bounds for the resulting overall low-rank approximation. This work thus gives a fast and reliable strategy for compressing those kernel matrices. Furthermore, it provides an intuitive way of understanding the proxy point method and bridges the gap between this useful analytical strategy and practical low-rank approximations. Some numerical examples help to further illustrate the ideas.
Recommendations
- Interpolative decomposition via proxy points for kernel matrices
- Far-field compression for fast kernel summation methods in high dimensions
- An O(N N) hierarchical random compression method for kernel matrices by sampling partial matrix entries
- Compression, inversion, and approximate PCA of dense kernel matrices at near-linear computational complexity
- On the Compression of Low Rank Matrices
Cites work
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A Divide-and-Conquer Algorithm for the Bidiagonal SVD
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- A fast algorithm for the inversion of general Toeplitz matrices
- A fast contour-integral eigensolver for non-Hermitian matrices
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for structured linear systems by recursive skeletonization
- A kernel independent fast multipole algorithm for radial basis functions
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- A matrix version of the fast multipole method
- A recursive skeletonization factorization based on strong admissibility
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- A Superfast Algorithm for Toeplitz Systems of Linear Equations
- A superfast structured solver for Toeplitz linear systems via randomized sampling
- An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
- An Implementation of the Fast Multipole Method without Multipoles
- Cauchy fast multipole method for general analytic kernels
- CUR matrix decompositions for improved data analysis
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Fast algorithms for hierarchically semiseparable matrices
- Feast eigensolver for non-Hermitian problems
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Householder QR factorization with randomization for column pivoting (HQRRP)
- scientific article; zbMATH DE number 1531793 (Why is no real title available?)
- scientific article; zbMATH DE number 1889799 (Why is no real title available?)
- scientific article; zbMATH DE number 6276143 (Why is no real title available?)
- Linear integral equations
- Literature survey on low rank approximation of matrices
- Mosaic-skeleton approximations
- On the Compression of Low Rank Matrices
- On the Nyström method for approximating a gram matrix for improved kernel-based learning
- Parallel randomized and matrix-free direct solvers for large structured dense linear systems
- Randomized sparse direct solvers
- Revisiting the Nyström method for improved large-scale machine learning
- Strong rank revealing LU factorizations
- Subspace Iteration Randomization and Singular Value Problems
- Superfast divide-and-conquer method and perturbation analysis for structured eigenvalue solutions
- The black-box fast multipole method
- The exponentially convergent trapezoidal rule
- The maximal-volume concept in approximation by low-rank matrices
- Transformations of matrix structures work again
- Yet another fast multipole method without multipoles -- pseudoparticle multipole method
Cited in
(11)- A stable matrix version of the fast multipole method: stabilization strategies and examples
- Efficient randomized tensor-based algorithms for function approximation and low-rank kernel interactions
- SuperDC: superfast divide-and-conquer eigenvalue decomposition with improved stability for rank-structured matrices
- Interpolative decomposition via proxy points for kernel matrices
- FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
- A fast direct solver for boundary integral equations using quadrature by expansion
- The Helmholtz Dirichlet and Neumann problems on piecewise smooth open curves
- Multi-layer hierarchical structures
- Parametric kernel low-rank approximations using tensor train decomposition
- A simplified fast multipole method based on strong recursive skeletonization
- LoCCA: Localized Chebyshev Cross Approximation for Kernel Matrix Factorization via Nodal Perturbation Stability
This page was built for publication: Analytical low-rank compression via proxy point selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5146610)
