  We study superfast algorithms that computes low rank approximation of a
matrix (hereafter referred to as LRA) that use much fewer memory cells and
arithmetic operations than the input matrix has entries. We first specify a
family of 2mn matrices of size m*n such that for almost 50% of them any
superfast LRA algorithm fails to improve the poor trivial approximation by the
matrix filled with zeros, but then we prove that the class of all such hard
inputs is narrow - the cross-approximation (hereafter {C-A}) superfast
iterations as well as some more primitive superfast algorithms compute
reasonably accurate LRAs in their transparent CUR form (i) to any matrix
allowing close LRA except for small norm perturbations of matrices of an
algebraic variety of a smaller dimension, (ii) to the average matrix allowing
close LRA, (iii) to the average sparse matrix allowing close LRA and (iv) with
a high probability to any matrix allowing close LRA if it is pre-processed fast
with a random Gaussian, SRHT or SRFT multiplier. Moreover empirically the
output LRAs remain accurate when we perform the computations superfast by
replacing such a multiplier with one of our sparse and structured multipliers.
Our techniques, auxiliary results and extensions may be of some independent
interest. We analyze C-A and other superfast algorithms twice -- based on two
well-known sufficient criteria for obtaining accurate LRAs. We provide a
distinct proof in the case of superfast variant of randomized algorithms of
[DMM08], improve a decade-old estimate for the norm of the inverse of a
Gaussian matrix, prove such an estimate also in the case of a sparse Gaussian
matrix, present some novel advanced pre-processing techniques for fast and
superfast computation of LRA, and extend our results to dramatic acceleration
of the Fast Multipole Method (FMM) and the Conjugate Gradient algorithms.
