How to calculate Rousseeuw’s and Croux’ (1993) Qn scale estimator for large samples?

Question

Let Qn = Cqn.{|Xi-Xj|;i < j}_(k) so for a very short sample like {1,3,6,2,7,5} it can be calculated from finding the kth static order of pairwise differences:

7 6 5 3 2 1

1 6 5 4 2 1

2 5 4 3 1

3 4 3 2

5 2 1

6 1

7

h=[n/2]+1=4

k=h(h-1)/2=8

Thus Qn=Cqn. 2

Obviously for large samples saying consist of 80,000 records we need very large memory. Is there anyway to calculate Qn in 1D space instead of 2D?

A link to the answer ftp://ftp.win.ua.ac.be/pub/preprints/92/Timeff92.pdf although I cannot fully understand it.

Answer 1

No, $O(n\log(n))$ is the lower theoretical bound (see (1)) for selecting the $k^{th}$ element among all $\frac{n(n-1)}{2}$ possible $|x_i - x_j|: 1 \leq i \lt j \leq n$.

You can get $O(1)$ space, but only by naively checking all combinations of $x_i-x_j$ in time $O(n^2)$.

The good news is that you can use the $\tau$ estimator of scale (see (2) and (3) for an improved version and some timing comparisons), implemented in the function scaleTau2() in the R package robustbase. The univariate $\tau$ estimator is an two-step (i.e. re-weighted) estimator of scale. It has 95 percent Gaussian efficiency, 50 percent breakdown point, and complexity of $O(n)$ time and $O(1)$ space (plus it can easily be made 'online', shaving off half the computational costs in repeated use -- although you will have to dig into the R code to implement this option, it is rather straightforward to do).

1. The complexity of selection and ranking in X + Y and matrices with sorted columns G. N. Frederickson and D. B. Johnson, Journal of Computer and System Sciences Volume 24, Issue 2, April 1982, Pages 197-208.
2. Yohai, V. and Zamar, R. (1988). High breakdown point estimates of regression by means of the minimization of an efficient scale. Journal of the American Statistical Association 83 406–413.
3. Maronna, R. and Zamar, R. (2002). Robust estimates of location and dispersion for high- dimensional data sets. Technometrics 44 307–317

Edit To use this

1. Fire up R (its free and can be downloaded from here)

2. install the package by tipping

   install.packages("robustbase")

3. load the package by tipping

   library("robustbase")

4. load your data file and run the function:

   mydatavector<-read.table("adress to my file in text format",header=T)

   scaleTau2(mydatavector)