REVIEW 17 cited by
Randomized algorithms for low-rank matrix approximation: Design, analysis, and applications
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
read the original abstract
This survey explores modern approaches for computing low-rank approximations of high-dimensional matrices by means of the randomized SVD, randomized subspace iteration, and randomized block Krylov iteration. The paper compares the procedures via theoretical analyses and numerical studies to highlight how the best choice of algorithm depends on spectral properties of the matrix and the computational resources available. Despite superior performance for many problems, randomized block Krylov iteration has not been widely adopted in computational science. The paper strengthens the case for this method in three ways. First, it presents new pseudocode that can significantly reduce computational costs. Second, it provides a new analysis that yields simple, precise, and informative error bounds. Last, it showcases applications to challenging scientific problems, including principal component analysis for genetic data and spectral clustering for molecular dynamics data.
Forward citations
Cited by 17 Pith papers
-
GPTQ-intrinsic LoRA: A Near-optimal Algorithm for Low-precision Quantization with Low-rank Adaptation
GPTQ-intrinsic LoRA augments GPTQ with intrinsic low-rank compensation via Hessian modification to achieve layer-wise reconstruction bounds that match information-theoretic lower bounds under structural assumptions.
-
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.
-
Transpose-free linear algebra
Establishes non-identifiability results and query lower bounds showing transpose-free matvec access provides limited information for core linear algebra tasks.
-
Random Matrix Spectra from Boltzmann-Weighted Lattice Ensembles
A framework maps Boltzmann-weighted lattice configurations to correlated random matrix ensembles via real-space to momentum-space variance profiles, deriving spectral moments and resolvent densities benchmarked on Isi...
-
Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace
Nyström's method always yields higher-accuracy leading eigenvalues than Rayleigh-Ritz for positive semi-definite matrices given a subspace approximation, with improvements that can be arbitrarily large.
-
CSULoRA: Closest Safe Update Low-Rank Adaptation
CSULoRA decomposes LoRA updates into fully aligned, partially aligned, and off-subspace components and solves a closed-form penalized minimum-change problem to preserve safe parts while attenuating unsafe directions.
-
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
Accelerates the power method for extracting top principal components using fast sketching and regularized spectral approximation for stronger low-rank guarantees.
-
Fast and accurate conditioning for large-scale Gaussian process prediction problems
A linear-combination conditioning strategy for GPs achieves exponential convergence to machine precision with r≈100 combinations at O(Tr²) cost for smooth kernels and simple domains.
-
Fast and accurate conditioning for large-scale Gaussian process prediction problems
Conditioning GPs on designed linear combinations of data yields exponentially convergent predictions in r for smooth kernels on simple domains, at near-linear cost with structured covariances.
-
Approximate full conformal prediction in an RKHS
For RKHS/Tikhonov predictors, computable approximations to the full conformal region contain it (hence cover at level 1−α) with explicit thickness rates, improved from O(1/(λn)) to O(1/(λ³n²)) via influence functions.
-
The Filter Echo: A General Tool for Filter Visualisation
The filter echo generalizes diffusion echoes for visualizing nonlinear filters beyond adaptive smoothing and adds a compression method that cuts storage needs by a factor of 20 to 100.
-
Intrinsic Low-Tucker-Rank Theory and Unified Tensor CUR Decomposition for High-Dimensional Hyperinterpolation
The paper asserts low-epsilon-Tucker-rank compressibility of hyperinterpolation coefficient tensors and gives unified TCUR error bounds, but the central rank formula exceeds the tensor dimensions and the advertised pr...
-
Fast and accurate conditioning for large-scale Gaussian process prediction problems
Conditioning on a small number of carefully designed linear combinations of data enables machine-precision accurate Gaussian process predictions at low cost for large-scale and online problems.
-
Low-Rank Compression of Pretrained Models via Randomized Subspace Iteration
Randomized subspace iteration improves low-rank approximation quality over randomized SVD for pretrained models by using power iterations to enhance spectral separation, preserving predictive accuracy better under agg...
-
How many integrals should be evaluated at least in two-dimensional hyperinterpolation?
The paper presents adaptive CUR-based algorithms that evaluate only a subset of Fourier integrals for 2D hyperinterpolation, but the central error bound is invalid because it confuses max-norm and Frobenius-norm of th...
-
Randomized coupled decompositions
Direct SVD solves coupled decompositions; randomized versions with novel balanced subspace selection improve efficiency and apply to face recognition.
-
Tomography-assisted noisy quantum circuit simulator using matrix product density operators
A simulator that inserts quantum-process-tomography noise data into a matrix-product density operator reproduces a five-qubit Quafu circuit with fidelity 0.999, versus 0.945 for a fitted standard noise model.
Discussion (0). Sign in to comment.