Abstract :

In this talk we survey recent essential developments (2, 3) of the ideas of low-rank matrix approximation proposed in (1). The practical importance of the very approach consists in its paradigm of using only small part of matrix entries that allows one to construct a sufficiently accurate approximation in a fast way for “big data” matrices that cannot be placed in any available computer memory and are accessed implicitly through calls to a procedure producing any individual entry in demand. During the two recent decades the approach has become a powerful numerical instrument in a tremendous variety of applications. However, its theoretical grounds still invite the researchers to provide them a better look. We discuss the notable new findings and as well some perspectives and open questions. (1) S. Goreinov, E. Tyrtyshnikov, N. Zamarashkin, A theory of pseudo-skeleton approximations, Linear Algebra Appl. 261 (1997) 1-21. (2) A. Osinsky, N. Zamarashkin, Pseudo-skeleton approximations with better accuracy estimates, Linear Algebra Appl. 537 (2018) 221-249. (3) A. Osinsky, Probabilistic estimation of the rank 1 cross approximation accuracy, arXiv: 1706.10285 (2017).