Computing the halfspace depth with multiple try algorithm and simulated annealing algorithm

Wei Shao () and Yijun Zuo
Additional contact information
Wei Shao: Qufu Normal University
Yijun Zuo: Michigan State University

Computational Statistics, 2020, vol. 35, issue 1, No 13, 203-226

Abstract: Abstract The halfspace depth is a powerful tool for the nonparametric multivariate analysis. However, its computation is very challenging for it involves the infimum over infinitely many directional vectors. The exact computation of the halfspace depth is a NP-hard problem if both sample size n and dimension d are parts of input. The approximate algorithms often can not get accurate (exact) results in high dimensional cases within limited time. In this paper, we propose a new general stochastic optimization algorithm, which is the combination of simulated annealing and the multiple try Metropolis algorithm. As a by product of the new algorithm, it is then successfully applied to the computation of the halfspace depth of data sets which are not necessarily in general position. The simulation and real data examples indicate that the new algorithm is highly competitive to, especially in the high dimension and large sample cases, other (exact and approximate) algorithms, including the simulated annealing and the quasi-Newton method and so on, both in accuracy and efficiency.

Keywords: Half-space depth computation; Multiple try Metropolis; Simulated annealing; Markov Chain Monte Carlo (MCMC) (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00180-019-00906-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:compst:v:35:y:2020:i:1:d:10.1007_s00180-019-00906-x

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/180/PS2

DOI: 10.1007/s00180-019-00906-x

Access Statistics for this article

Computational Statistics is currently edited by Wataru Sakamoto, Ricardo Cao and Jürgen Symanzik

More articles in Computational Statistics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().