Fast surrogates of U-statistics

U-statistics have long been known as a class of nonparametric estimators with good theoretical properties such as unbiasedness and asymptotic normality. However, their applications in modern statistical analysis are limited due to the high computational complexity, especially when massive data sets are becoming more and more common nowadays. In this paper, using the "divide-and-conquer" technique, we developed two surrogates of the U-statistics, aggregated U-statistics and average aggregated U-statistics, both of which are shown asymptotically equivalent to U-statistics and computationally much more efficient. When dividing the raw data set into K subsets, the two proposed estimators reduce the computational complexity from O(N-m) to O(K(N/K)(m)), which results in significant time reduction as long as K = o(N) and m >= 2. The merit of the two proposed statistics is demonstrated by both simulation studies and real data examples. (C) 2009 Elsevier B.V. All rights reserved.