  Low rank approximation of a matrix (hereafter LRA) is a highly important area
of Numerical Linear and Multilinear Algebra and Data Mining and Analysis. One
can operate with LRA at sublinear cost, that is, by using much fewer memory
cells and flops than an input matrix has entries, but no sublinear cost
algorithm can compute accurate LRA of the worst case input matrices or even of
the matrices of small families in our Appendix. Nevertheless we prove that
Cross-Approximation celebrated algorithms and even more primitive sublinear
cost algorithms output quite accurate LRA for a large subclass of the class of
all matrices that admit LRA and in a sense for most of such matrices. Moreover,
we accentuate the power of sublinear cost LRA by means of multiplicative
pre-processing of an input matrix, and this also reveals a link between C-A
algorithms and Randomized and Sketching LRA algorithms. Our tests are in good
accordance with our formal study.
