Low Rank Approximation at Sublinear Cost by Means of Subspace Sampling

Low Rank Approximation (hereafter LRA) of a matrix is a hot research subject, fundamental for Matrix and Tensor Computations and Big Data Mining and Analysis. Computations with LRA can be performed at sublinear cost, that is, by using much fewer memory cells and arithmetic operations than an input matrix has entries. Can we, however, compute LRA at sublinear cost? This is impossible for worst case inputs, but our sublinear cost deterministic variations of a popular randomized subspace sampling algorithms output accurate LRA of a large class of inputs, and in a sense of most of input matrices that admit LRA. This follows because we prove that with a high probability these deterministic algorithms output close LRA of a random input matrix that admits its LRA. Our numerical tests are in rather good accordance with our formal analysis. In other papers we propose and analyze other such algorithms for LRA and other important matrix computations.