A PTAS for Computing the Supremum of Gaussian Processes

Details A PTAS for Computing the Supremum of Gaussian Processes A PTAS for Computing the Supremum of Gaussian Processes

2012-02-22

arxiv.org/abs/1202.4970v1

Computer Science

Data Structures and Algorithms

Scientific paper

We give a polynomial time approximation scheme (PTAS) for computing the supremum of a Gaussian process. That is, given a finite set of d-dimensional vectors V, we compute a (1+epsilon)-factor approximation to Ex_{X standard Gaussian}[sup_{v in V}||] deterministically in time poly(d) |V|^{O_epsilon(1)}. Previously, only a constant factor deterministic polynomial time approximation algorithm was known due to the work of Ding, Lee and Peres. This answers an open question of Lee and Ding. The study of supremum of Gaussian processes is of considerable importance in probability with applications in functional analysis, convex geometry, and in light of the recent work of Ding, Lee and Peres, to random walks on finite graphs. As such our result could be of use elsewhere. In particular, combining with the recent work of Ding, our result yields a PTAS for computing the cover time of bounded degree graphs. Previously, such algorithms were known only for trees. Along the way, we also give an explicit oblivious linear estimator for semi-norms in Gaussian space with optimal query complexity.

Affiliated with

Also associated with

No associations

Rating

A PTAS for Computing the Supremum of Gaussian Processes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A PTAS for Computing the Supremum of Gaussian Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A PTAS for Computing the Supremum of Gaussian Processes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-415697