Conceptually, statistical leverage scores give a measure of the relative importance of each row, where the importance depends on the application. In [1]}, Hoaglin and Welsch first used statistical leverage scores as a regression diagnosis of least squares to detect potential outliers in the data. They describe how the size of the \(i\) -th statistical leverage score gives a measure of the influence of the \(i\) -th row on the least squares data fitting. If the \(i\) -th statistical leverage score is large, then one may doubt the accuracy of the corresponding data point, and may want to remove the abnormal data point in order to better fit the remaining data. Recently, Drineas et al. [2]}, [3]}, [4]} start to advocate the use of statistical leverage scores in many randomized matrix algorithms. These random sampling algorithms for solving matrix problems are important tools to design fast algorithms, which are used to sample the input data matrix, like least-squares regression [5]} and low rank matrix approximation [6]}, [7]}, [8]}, [9]}. A related concept is matrix coherence, defined by the largest statistical leverage score, and it has gained widespread attention on recent popular problems, see [10]}, [11]} and the references therein.
