|
|
PreMoLab Seminar
March 7, 2013, Moscow, A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences (Bol'shoi Karetnyi per., 19), room 615
|
|
|
|
|
|
Random sampling: Billiard Walk Algorithm
E. N. Gryazina Institute of Control Sciences, Russian Academy of Sciences, Moscow
|
Number of views: |
This page: | 235 |
|
Abstract:
Hit-and-Run is known to be one of the best random sampling algorithms, its
mixing time is polynomial in dimension. Nevertheless, in practice the number
of iterations required to achieve uniformly distributed samples is
rather high. We
propose new random walk algorithm based on billiard trajectories.
Numerical experiments demonstrate much faster convergence to uniform
distribution.
|
|