9
$\begingroup$

The Theil-Sen estimator is of interest to me, however when I implement it myself I end up with something that scales as O(n^2). According to wikipedia, it can be calculated exactly in O(n log(n)). Can someone point me toward an efficient implementation (python or mathematica would be best, Matlab or R would be tolerable) or otherwise explain in simple terms how the efficient versions work?

$\endgroup$
0

2 Answers 2

5
$\begingroup$

According to wikipedia, it can be calculated exactly in O(n log(n)).

Wikipedia points to no less than six papers detailing different deterministic or randomized algorithms with $O(n\log n)$ performance, right in the section where they mention the existence of such algorithms (as well as mentioning an even faster one under particular circumstances).

Deterministic:

Cole, Richard; Salowe, Jeffrey S.; Steiger, W. L.; Szemerédi, Endre (1989), An optimal-time algorithm for slope selection, SIAM Journal on Computing 18 (4): 792–810, doi:10.1137/0218055, MR 1004799.

Katz, Matthew J.; Sharir, Micha (1993), Optimal slope selection via expanders, Information Processing Letters 47 (3): 115–122, doi:10.1016/0020-0190(93)90234-Z, MR 1237287.

Brönnimann, Hervé; Chazelle, Bernard (1998), Optimal slope selection via cuttings, Computational Geometry Theory and Applications 10 (1): 23–29, doi:10.1016/S0925-7721(97)00025-4, MR 1614381.

$\ $

Randomized:

Dillencourt, Michael B.; Mount, David M.; Netanyahu, Nathan S. (1992), A randomized algorithm for slope selection, International Journal of Computational Geometry & Applications 2 (1): 1–27, doi:10.1142/S0218195992000020, MR 1159839.

Matoušek, Jiří (1991), Randomized optimal algorithm for slope selection, Information Processing Letters 39 (4): 183–187, doi:10.1016/0020-0190(91)90177-J, MR 1130747.

Blunck, Henrik; Vahrenhold, Jan (2006), "In-place randomized slope selection", International Symposium on Algorithms and Complexity, Lecture Notes in Computer Science 3998, Berlin: Springer-Verlag, pp. 30–41, doi:10.1007/11758471_6, MR 2263136.

Which did you want?

$\endgroup$
9
  • 3
    $\begingroup$ Yes, I do know how to notice when references are made. I'd like the one that can be explained HERE in relatively SIMPLE terms. Alternatively the one that has been implemented so that one can just use the code. $\endgroup$
    – mdeceglie
    Commented Oct 20, 2014 at 13:10
  • $\begingroup$ I do prefer a method that computes it exactly rather than something that gives a slightly different answer each time. $\endgroup$
    – mdeceglie
    Commented Oct 20, 2014 at 13:27
  • $\begingroup$ Why the downvote? $\endgroup$ Commented Oct 20, 2014 at 15:45
  • 4
    $\begingroup$ Italian, you mistake the meaning of a "randomized algorithm": these are algorithms that randomize their input in order to avoid rare worst-case situations. They have $O(n\log(n))$ expected computation time--but they produce exact, correct, repeatable optimal solutions. The deterministic algorithms Glen_b cites here tend to be complicated, whereas some of the randomized algorithms are relatively simple. The initial commentary in the last paper (Henrik Blunck and Jan Vahrenhold) explains this and provides an overview of several of the algorithms. $\endgroup$
    – whuber
    Commented Oct 20, 2014 at 16:14
  • 2
    $\begingroup$ italianice -- None of the algorithms are very simple; the papers explaining them leave out quite a few details (as being obvious enough that an expert could fill in the omitted details); all those would need to be explained - I can't seeing even the simplest being covered in less than many, many thousands of words (likely tens of thousands, plus diagrams). As far as I can see, all involve computational geometry in some way. The randomized algorithms tend to be somewhat simpler, but that's not saying much. If you really need this, your best bet might be to look for an implementation. $\endgroup$
    – Glen_b
    Commented Oct 21, 2014 at 6:16
1
$\begingroup$

The R-package robslopes contains a C++ implementation based on the algorithm by Dillencourt et. al (1992) and Matousek et. al (1998). See https://cran.r-project.org/web/packages/robslopes/index.html

$\endgroup$
1
  • $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$ Commented Jun 8, 2022 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.