On the approximation of a matrix

2021/08/25 by Samriddha Sanyal, Sanyal, Samriddha
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.LG #cs.NA #math.NA #stat.ML

paper · pdf · doi:10.48550/arxiv.2108.13195

arxiv created 2021/08/25 · openalex publication_date 2021/08/25 · arxiv updated 2021/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let F^* be an approximation of a given (a × b) matrix F derived by methods that are not randomized. We prove that for a given F and F^*, H and T can be computed by randomized algorithm such that (HT) is an approximation of F better than F^*.

Citations

• Error Bounds for Random Matrix Approximation Schemes
• Fast monte-carlo algorithms for finding low-rank approximations
• The Approximation of One Matrix by Another of Lower Rank
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

Related

• Analysis of a randomized approximation scheme for matrix multiplication
• Improved matrix algorithms via the Subsampled Randomized Hadamard\n Transform
• Fast monte-carlo algorithms for finding low-rank approximations
• Randomized low-rank approximation of monotone matrix functions
• Randomized low-rank approximation of parameter-dependent matrices