Geometry and Statistics: Problems at the Interface,
Abstract
In this paper the author approaches the analysis of statistics algorithms from a geometric viewpoint and uses techniques from computational geometry to develop new, fast algorithms for computing familiar statistical quantities. Such fundamental procedures as sorting and selection play an important role in nonparametric estimation as well as in correlation and regression and the author uses known results to obtain lower bounds on the time required to perform various statistical tests. For some problems, computing the test statistic is NP-hard. While geometric insight is helpful in understanding statistical calculations, the reverse is also true -- statistical methods are employed to analyze the average case of geometric algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1976
- Accession Number
- ADA029131
Entities
People
- Michael Ian Shamos
Organizations
- Carnegie Mellon University