Geometry and Statistics: Problems at the Interface

Excerpts

From the viewpoint of applied computational complexity, statistics is a gold mine, for it provides a rich and extensive source of unalyzed algorithms and computational procedures. For the statistician, however, the search for efficient algorithms has not been of prime concerns for several reasons: First, the design of fast algorithms is a new and developing art. Second, until recently, the cost of obtaining data has been far greater than the cost of analyzing it. Now, hoever, speech and image processing provide information to statistical analysis programs rapidly and cheaply, so that fast analysis is of considerable important. Third, statisticians are properly concerned with the significance and effectiveness of the tests they perform, rather than with their cost. The result has been that the analysis of statistical algorithms remains largely ignored.

— Page 251

Abstract

In this paper we approach the analysis of statistics algorithms from a geometric viewpoint and use 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 we use 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-we employ statistical methods to analyze the average case of geometric al gorithms.

Reference

Michael Ian Shamos “Geometry and Statistics: Problems at the Interface” (1976)

@Article{shamos1976,
  title = {Geometry and Statistics: Problems at the Interface},
  abstract = {In this paper we approach the analysis of statistics algorithms from a geometric viewpoint and use 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 we use 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-we employ statistical methods to analyze the average case of geometric al gorithms.},
  author = {Shamos, Michael Ian},
  booktitle = {In Algorithms and Complexity: New directions and recent results},
  year = {1976},
  organization = {Citeseer}
}