  A matrix algorithm runs at {\em sublinear cost} if it uses much fewer memory
cells and arithmetic operations than the input matrix has entries. Such
algorithms are indispensable for Big Data Mining and Analysis. Quite typically
in that area the input matrices are so immense that realistically one can only
access a small fraction of all their entries but can access and process at
sublinear cost their Low Rank Approximation {\em (LRA)}. Can, however, we
compute LRA at sublinear cost? Adversary argument shows that the output of any
algorithm running at sublinear cost is extremely far from LRA of the worst case
input matrices and even of the matrices of small families of our Appendix, but
we prove that some deterministic sublinear cost algorithms output reasonably
close LRA in a memory efficient form of CUR LRA if an input matrix admits LRA
and is Symmetric Positive Semidefinite or is very close to a low rank matrix.
The latter result is technically simple but provides some (very limited but
long overdue) support for the well-known empirical efficiency of sublinear cost
LRA by means of Cross-Approximation. We demonstrate the power of application of
such LRA by turning the Fast Multipole celebrated Method into Superfast
Multipole Method. The design and analysis of our algorithms rely on extensive
prior study of the link of LRA of a matrix to maximization of its volume.
