Fast monte-carlo algorithms for finding low-rank approximations
From MaRDI portal
Publication:5435673
DOI10.1145/1039488.1039494zbMath1125.65005OpenAlexW1979750072WikidataQ57401514 ScholiaQ57401514MaRDI QIDQ5435673
Santosh Vempala, Alan M. Frieze, Ravindran Kannan
Publication date: 14 January 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1039488.1039494
Analysis of algorithms (68W40) Monte Carlo methods (65C05) Information storage and retrieval of data (68P20) Randomized algorithms (68W20)
Related Items
Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture, Randomized Quasi-Optimal Local Approximation Spaces in Time, Optimal sampling algorithms for block matrix multiplication, Solution of the EEG inverse problem by random dipole sampling, Unnamed Item, Web document clustering using hyperlink structures, Randomized numerical linear algebra: Foundations and algorithms, Fast low-rank modifications of the thin singular value decomposition, A fast block low-rank dense solver with applications to finite-element matrices, Randomized Local Model Order Reduction, Territorial design optimization for business sales plan, Column subset selection problem is UG-hard, A spectral method to find communities in bipartite networks, Quantum machine learning: a classical perspective, A Nonlinear Matrix Decomposition for Mining the Zeros of Sparse Data, A randomized algorithm for a tensor-based generalization of the singular value decomposition, Far-field compression for fast kernel summation methods in high dimensions, Large-scale stochastic linear inversion using hierarchical matrices. Illustrated with an application to crosswell tomography in seismic imaging, How to get close to the median shape, A spectral algorithm for learning mixture models, On the low-rank approximation arising in the generalized Karhunen-Loeve transform, Enhanced image approximation using shifted rank-1 reconstruction, Finding metastabilities in reversible Markov chains based on incomplete sampling, Fast Randomized Iteration: Diffusion Monte Carlo through the Lens of Numerical Linear Algebra, One-pass additive-error subset selection for \(\ell_p\) subspace approximation and \((k, p)\)-clustering, A compact heart iteration for low-rank approximations of large matrices, A fast, memory efficient and robust sparse preconditioner based on a multifrontal approach with applications to finite‐element matrices, SVD, discrepancy, and regular structure of contingency tables, Randomized algorithms in numerical linear algebra, Randomized LU decomposition, Optimal subsampling for softmax regression, Sparsified randomization algorithms for low rank approximations and applications to integral equations and inhomogeneous random field simulation, Practical Sketching Algorithms for Low-Rank Matrix Approximation, Multigrid with Rough Coefficients and Multiresolution Operator Decomposition from Hierarchical Information Games, Unnamed Item, Literature survey on low rank approximation of matrices, Dimensional reduction in vector space methods for natural language processing: products and projections, Optimal CUR Matrix Decompositions, Regularized Linear Inversion with Randomized Singular Value Decomposition, Second order accurate distributed eigenvector computation for extremely large matrices, Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decomposition, An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation, Regularized greedy column subset selection, Random Sampling and Efficient Algorithms for Multiscale PDEs, Sampling-based dimension reduction for subspace approximation with outliers, Sampling based succinct matrix approximation, Non-Negative Sparse Regression and Column Subset Selection with L1 Error, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Approximating Spectral Clustering via Sampling: A Review, Efficient subspace approximation algorithms, Effective implementation to reduce execution time of a low-rank matrix approximation problem, Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection, The Fourier approximation of smooth but non-periodic functions from unevenly spaced data, Generalized low rank approximations of matrices, Forecasting using random subspace methods, Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices, Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices, A Nyström spectral clustering algorithm based on probability incremental sampling, Randomized model order reduction, Approximation error in regularized SVD-based Fourier continuations, Householder QR Factorization With Randomization for Column Pivoting (HQRRP), Generalized low rank approximations of matrices, Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions, Sublinear-time Algorithms, A two-stage surrogate model for neo-Hookean problems based on adaptive proper orthogonal decomposition and hierarchical tensor approximation, Unnamed Item, Unnamed Item, Unnamed Item, Random matrices: The distribution of the smallest singular values, Fast randomized matrix and tensor interpolative decomposition using countsketch, Randomized interpolative decomposition of separated representations, Geometric component analysis and its applications to data analysis, Stochastic iterative projection methods for large linear systems, CUR matrix decompositions for improved data analysis, Towards theory of generic principal component analysis, Randomized Dynamic Mode Decomposition, Stochastic Algorithms in Linear Algebra - beyond the Markov Chains and von Neumann - Ulam Scheme, Summarization and Search Over Geometric Spaces, A cross-product approach for low-rank approximations of large matrices, Stochastic boundary methods of fundamental solutions for solving PDEs, Unnamed Item, Multiplicative Approximations of Random Walk Transition Probabilities, Frequent Directions: Simple and Deterministic Matrix Sketching, A Computationally Efficient Projection-Based Approach for Spatial Generalized Linear Mixed Models, ALORA: affine low-rank approximations, A randomized Kaczmarz algorithm with exponential convergence, Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation, ASKIT: An Efficient, Parallel Library for High-Dimensional Kernel Summations, Fiber Sampling Approach to Canonical Polyadic Decomposition and Application to Tensor Completion, Column subset selection via sparse approximation of SVD, Randomized block Krylov methods for approximating extreme eigenvalues, On selecting a maximum volume sub-matrix of a matrix and related problems, Optimal Column-Based Low-Rank Matrix Reconstruction, Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method, Unnamed Item, Subsampling Algorithms for Semidefinite Programming, Fast dimension reduction using Rademacher series on dual BCH codes, Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds, Subspace Iteration Randomization and Singular Value Problems, Unnamed Item, Unnamed Item, Perfect $L_p$ Sampling in a Data Stream, Fast and Accurate Proper Orthogonal Decomposition using Efficient Sampling and Iterative Techniques for Singular Value Decomposition, Estimating a Few Extreme Singular Values and Vectors for Large-Scale Matrices in Tensor Train Format
