Superfast Matrix Norm Estimation and Low Rank Approximation

We propose superfast (aka sublinear cost) algorithms for two fundamental problems of Matrix Computations, that is, Norm Estimation and Iterative Refinement of Low Rank Approximation (LRA). A superfast algorithm only accesses a small fraction of all entries of an input matrix and cannot accurately estimate their norms or output their close LRA for worst case inputs. Thus, we begin with some well-known algorithms solving these problems in linear or super linear time and then propose superfast modifications, which still promise to succeed for most or a large class of inputs, according to our tests with real world inputs.