An efficient algorithm for T-estimation

We introduce an efficient and exact algorithm, together with a faster but approximate version, which implements with a sub-quadratic complexity the hold-out derived from T-estimation. We study empirically the performance of this hold-out in the context of density estimation considering well-known competitors (hold-out derived from least-squares or Kullback-Leibler divergence, model selection procedures, etc.) and classical problems including histogram or bandwidth selection. Our algorithms are integrated in a companion R-package called {\it Density.T.HoldOut} available on the CRAN: {\url{http://cran.r-project.org/web/packages/Density.T.HoldOut/index.html}}.