摘要： 
Low rank approximation of matrix plays an important role in areas such as numerical linear algebra, optimization and applied statistics. The Eckart–Young–Mirsky theorem shows that, under Schatten norms, the best k-rank approximation for a matrix A is its truncation of the first k singular values. However, for matrices with a large size, directly calculating their SVD truncations is expensive. Fortunately, people have developed many randomized algorithms to approximate the best low rank approximation with great precision and efficiency.

In this talk, we will introduce the latest work[Bakshi et al. 2022] on complexity of randomized low rank approximation, which shows, for any \epsilon accuracy, we only need O(1/\epsilon^{1/3}) matrix-vector products. This work greatly improves the O(1/\epsilon^{1/2}) bound in [Musco and Musco,2015] and gives the first nontrivial lower bound depending on \epsilon. Some remaining open problems will also be discussed.