Input sparsity time low-rank approximation via ridge leverage score sampling
From MaRDI portal
Abstract: We present a new algorithm for finding a near optimal low-rank approximation of a matrix in time. Our method is based on a recursive sampling scheme for computing a representative subset of 's columns, which is then used to find a low-rank approximation. This approach differs substantially from prior time algorithms, which are all based on fast Johnson-Lindenstrauss random projections. It matches the guarantees of these methods while offering a number of advantages. Not only are sampling algorithms faster for sparse and structured data, but they can also be applied in settings where random projections cannot. For example, we give new single-pass streaming algorithms for the column subset selection and projection-cost preserving sample problems. Our method has also been used to give the fastest algorithms for provably approximating kernel matrices [MM16].
Recommendations
Cited in
(32)- Quick-means: accelerating inference for K-means by learning fast transforms
- Isolation kernel: the X factor in efficient and effective large scale online kernel learning
- Nyström landmark sampling and regularized Christoffel functions
- Structural conditions for projection-cost preservation via randomized matrix multiplication
- Approximating spectral clustering via sampling: a review
- Weighted SGD for _p regression with randomized preconditioning
- Low-Rank PSD Approximation in Input-Sparsity Time
- Randomized algorithms in numerical linear algebra
- Scalable kernel \(k\)-means clustering with Nyström approximation: relative-error bounds
- scientific article; zbMATH DE number 7049775 (Why is no real title available?)
- Online row sampling
- Communication-efficient distributed covariance sketch, with application to distributed PCA
- Diversity sampling is an implicit regularization for kernel methods
- Density independent algorithms for sparsifying k-step random walks
- Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
- Estimating Leverage Scores via Rank Revealing Methods and Randomization
- Semi-Infinite Linear Regression and Its Applications
- Allocation Strategies for High Fidelity Models in the Multifidelity Regime
- Tighter low-rank approximation via sampling the leveraged element
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- Online row sampling
- Randomized numerical linear algebra: Foundations and algorithms
- One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering
- New subset selection algorithms for low rank approximation: offline and online
- \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
- Online randomized interpolative decomposition with \textit{a posteriori} error estimator for temporal PDE data reduction
- Fine-grained analysis and faster algorithms for iteratively solving linear systems
- A fast Bregman projection method for linearly constrained optimization problems
- A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
- Algorithm-agnostic low-rank approximation of operator monotone matrix functions
- Residual-Christoffel Sampling for Random Feature Collocation of Linear PDEs
- A class of improved randomized Gauss-Seidel methods based on the leverage scores for the parameter estimation of TAR model
This page was built for publication: Input sparsity time low-rank approximation via ridge leverage score sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575860)
