On randomized sketching algorithms and the Tracy-Widom law
From MaRDI portal
(Redirected from On randomized sketching algorithms and the Tracy-Widom law)
Abstract: There is an increasing body of work exploring the integration of random projection into algorithms for numerical linear algebra. The primary motivation is to reduce the overall computational cost of processing large datasets. A suitably chosen random projection can be used to embed the original dataset in a lower-dimensional space such that key properties of the original dataset are retained. These algorithms are often referred to as sketching algorithms, as the projected dataset can be used as a compressed representation of the full dataset. We show that random matrix theory, in particular the Tracy-Widom law, is useful for describing the operating characteristics of sketching algorithms in the tall-data regime when . Asymptotic large sample results are of particular interest as this is the regime where sketching is most useful for data compression. In particular, we develop asymptotic approximations for the success rate in generating random subspace embeddings and the convergence probability of iterative sketching algorithms. We test a number of sketching algorithms on real large high-dimensional datasets and find that the asymptotic expressions give accurate predictions of the empirical performance.
Recommendations
- Statistical properties of sketching algorithms
- Randomized sketching algorithms for low-memory dynamic optimization
- scientific article; zbMATH DE number 1566488
- scientific article; zbMATH DE number 742952
- Tight lower bound for linear sketches of moments
- scientific article; zbMATH DE number 1775407
- On the power of randomization in on-line algorithms
- On the exact space complexity of sketching and streaming small norms
- On the search path length of random binary skip graphs
- On the power of random greedy algorithms
Cites work
- A statistical perspective on algorithmic leveraging
- Accuracy of the Tracy-Widom limits for the extreme eigenvalues in white Wishart matrices
- ARPACK Users' Guide
- Asymptotic Statistics
- Eigenvalues and Condition Numbers of Random Matrices
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Improved analysis of the subsampled randomized Hadamard transform
- Iterative Hessian sketch: fast and accurate solution approximation for constrained least-squares
- Level-spacing distributions and the Airy kernel
- Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression
- LSRN: A parallel iterative solver for strongly over- or underdetermined systems
- On the distribution of the largest eigenvalue in principal components analysis
- On the Probability That All Eigenvalues of Gaussian, Wishart, and Double Wishart Random Matrices Lie Within an Interval
- Random projections for Bayesian regression
- Randomized Algorithms for Matrices and Data
- Robust regression: Asymptotics, conjectures and Monte Carlo
- Sampling algorithms for l₂ regression and applications
- Sketching as a tool for numerical linear algebra
- Spectral analysis of large dimensional random matrices
- Statistical properties of sketching algorithms
- Subsampling MCMC -- an introduction for the survey statistician
- The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
- The Johnson-Lindenstrauss Transform: An Empirical Study
- Universality for the largest eigenvalue of sample covariance matrices with general population
Cited in
(3)
This page was built for publication: On randomized sketching algorithms and the Tracy-Widom law
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163409)
