We are interested in the development of sublinear time algorithms for computing statistical leverage scores, and we need to focus on how to input the given matrix and vector. Obviously, it is not possible to load the entire matrix and vector into memory because it costs at least linear time. In this work, we assume that matrices and vectors can be sampled according to some natural probability distributions, which are found in many applications of machine learning [1]}, [2]}, [3]}.
