Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
This interesting paper studies robust blockwise random pivoting. More precisely, it focuses on fast and accurate adaptive interpolative decomposition (ID). Mathematically ID can be described as follows. Let us be given a set \(X:=[x_1,...,x_n]^{T}\in\mathbb R^{n\times d}\) consisting of \(n\geq 1\) data points say \(\left\{x_i\in \mathbb R^d\right\}_{i\in [n]}\), \(\varepsilon>0\) small enough and a target rank \(r\in \mathcal{N}\). The aim is to construct an \((r,\varepsilon)\) ID of the set \(X\) so the following holds: \(X\approx WX_{S}\) where \(||X-WX_S||_F^2\leq (1+\varepsilon)||X-<X>_r||_F^2\) where: \(k\) is an unknown target rank, \(<X>_r\) is the optimal rank-\(r\) approximation of the set \(X\), \(S=\left\{s_1,...,s_k\right\}\subset[n]\) are the skeleton indices corresponding to the row skeleton \(k\times d\) submatrix \(X_S:=[x_{s_1},...,x_{s_k}]^T\in\mathbb R^{k\times d}\) and \(W\in \mathbb R^{n\times k}\) is an interpolation matrix that (nearly) minimizes \(||X-WX_S||_F^2\). Here, \(||.||_F\) is the Frobenius matrix norm. \N\NID has many applications, for example in numerical analysis, data compression, machine learning and many others. Essentially, ID constructs a low-rank approximation formed by a basis consisting of row/column skeletons in the original matrix and a corresponding interpolation matrix.\N\NIn this paper, the authors study accurate and fast ID algorithms for empirical performance, including accuracy in both skeleton selection and interpolation matrix construction, efficiency in terms of asymptotic complexity and hardware efficiency, as well as rank-adaptiveness.\N\NThe paper is very well written and has a very good set of references.
- A BLAS-3 Version of the QR Factorization with Column Pivoting
- A DEIM induced CUR factorization
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A fast direct solver for boundary integral equations in two dimensions
- A fast direct solver for structured linear systems by recursive skeletonization
- A recursive skeletonization factorization based on strong admissibility
- A statistical perspective on randomized sketching for ordinary least-squares
- Accelerating numerical dense linear algebra calculations with GPUs
- Adaptive Sampling and Fast Low-Rank Matrix Approximation
- An \(O(N)\) direct solver for integral equations on the plane
- An updated set of basic linear algebra subprograms (BLAS)
- Average-Case Stability of Gaussian Elimination
- CUR matrix decompositions for improved data analysis
- Determinantal point processes in randomized numerical linear algebra
- Determinantal processes and independence
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient algorithms for CUR and interpolative matrix decompositions
- Fast approximation of matrix coherence and statistical leverage
- Fast monte-carlo algorithms for finding low-rank approximations
- Faster subset selection for matrices and applications
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Householder QR factorization with randomization for column pivoting (HQRRP)
- scientific article; zbMATH DE number 6381735 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 4189084 (Why is no real title available?)
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Matrix approximation and projective clustering via volume sampling
- Nearly tight oblivious subspace embeddings by trace inequalities
- Numerical Linear Algebra
- On the Compression of Low Rank Matrices
- Optimal column-based low-rank matrix reconstruction
- Optimal Design of Experiments
- Randomized numerical linear algebra: Foundations and algorithms
- Randomized QR with column pivoting
- Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- Sketching as a tool for numerical linear algebra
- Sublinear time low-rank approximation of positive semidefinite matrices
- Uniform sampling for matrix approximation
This page was built for publication: Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6936081)
