2019/06/11 by Qi Luan, Victor Y. Pan, Luan, Qi +5
Computer Science · Mathematics · #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Stochastic Gradient Optimization Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.1906.04327
openalex publication_date 2019/06/11 · openalex created_date 2021/04/26 · openalex updated_date 2026/07/28
Low Rank Approximation (LRA) of a matrix is a hot research subject, fundamental for Matrix and Tensor Computations and Big Data Mining and Analysis. Computations with low rank matrices can be performed at sublinear cost -- by using much fewer floating-point operations (flops) than an input matrix has entries, but can we compute LRA at sublinear cost? This is routinely done in computational practice for a large class of inputs, even though any sublinear cost LRA algorithm fails most miserably on worst case matrices. To provide insight into this controversy we first accelerate some popular near-optimal random sketching LRA algorithms -- to run them at sublinear cost. Then we define two probabilistic structures in the space of input matrices and estimate that the expected spectral and Frobenius error norms for the output LRA of the accelerated algorithms stay within a reasonable factor from their optima under both models, and so these sublinear cost algorithms only fail for a very narrow input class. Our upper estimates for their output accuracy are still quite high, but under some additional semi-heuristic amendments the algorithms have consistently output accurate LRA of various synthetic and real-world matrices in our numerical tests.