A0215
Title: ICUDO: Incomplete U-statistic based on division and orthogonal arrays
Authors: Xiangshun Kong - Beijing Institute of Technology (China)
Wei Zheng - University of Tennessee (United States) [presenting]
Abstract: U-statistics are an important class of statistics. Unfortunately, its computation easily becomes impractical as the data size $n$ increases. Particularly, the number of combinations, say $m$, that a U-statistic of order $d$ has to evaluate is in the order of $n^d$. Many efforts have been made to approximate a U-statistic by a small subset of combinations. Such an approximation is called incomplete U-statistic. To the best of our knowledge, all existing methods require $m$ to grow at least faster than $n$, albeit much slower than $n^d$, in order for the corresponding incomplete U-statistic to be asymptotically efficient in the sense of mean squared error. We introduce a new type of incomplete U-statistic, which can be asymptotically efficient even when $m$ grows slower than $n$. In some cases, $m$ is only required to grow faster than $\sqrt{n}$. Both one-sample and multi-sample cases and both non-degenerate and degenerate cases are thoroughly discussed.
