REVIEW 8 cited by
Fast and stable randomized low-rank matrix approximation
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
Randomized SVD has become an extremely successful approach for efficiently computing a low-rank approximation of matrices. In particular the paper by Halko, Martinsson, and Tropp (SIREV 2011) contains extensive analysis, and has made it a very popular method. The typical complexity for a rank-$r$ approximation of $m\times n$ matrices is $O(mn\log n+(m+n)r^2)$ for dense matrices. The classical Nystr{\"o}m method is much faster, but applicable only to positive semidefinite matrices. This work studies a generalization of Nystr{\"o}m method applicable to general matrices, and shows that (i) it has near-optimal approximation quality comparable to competing methods, (ii) the computational cost is the near-optimal $O(mn\log n+r^3)$ for dense matrices, with small hidden constants, and (iii) crucially, it can be implemented in a numerically stable fashion despite the presence of an ill-conditioned pseudoinverse. Numerical experiments illustrate that generalized Nystr{\"o}m can significantly outperform state-of-the-art methods, especially when $r\gg 1$, achieving up to a 10-fold speedup. The method is also well suited to updating and downdating the matrix.
Forward citations
Cited by 8 Pith papers
-
Sublinear Time Eigenvector Approximation via Column Sampling
A small random column sample of a symmetric matrix yields all outlying approximate eigenvectors with small residual error and entrywise query time poly(log n, 1/epsilon).
-
Faster Linear Algebra Algorithms with Structured Random Matrices
Randomized sketching needs only the new OSI property, not the full subspace embedding, and multiple structured matrices satisfy it with near-optimal cost.
-
Quasi-optimal hierarchically semi-separable matrix approximation
A randomized algorithm produces an HSS approximation with expected error at most O(log(N/k)) times optimal, using O(k log(N/k)) matrix-vector products.
-
A recursive butterfly factorization with optimality guarantees
A recursive butterfly representation leads to entry-access and matrix-free butterfly approximations with provably near-optimal error guarantees.
-
Linear-Scaling Tensor Train Sketching
TTStack achieves oblivious subspace embedding and injection for tensor trains with sample complexity linear in order d and subspace dimension r, yielding quasi-optimal randomized TT rounding.
-
Fast two-dimensional tensor-network contraction via subspace iteration
A new CTMRG variant, SI-CTMRG, substitutes QR-based subspace iteration for the dominant large SVD, shifting cost to tensor contractions and enabling state-of-the-art iPEPS calculations on a single H100 GPU.
-
Superfast 1-Norm Estimation
Randomized sparsification of the vectors in LAPACK's 1-norm estimator produces sublinear-cost estimates whose mean errors are small on the paper's test suite.
-
Adaptive, Matrix-Free Low-Rank Approximation
Adaptive matrix-free randomized QB algorithms determine rank on the fly via sketched residual indicators and pruning, meeting Frobenius or spectral tolerances to machine precision with near-optimal ranks.
Discussion (0). Continue with ORCID to comment.