0
$\begingroup$

I've been thinking about algorithms of the form where a quantity $c$ can be viewed as the expectation of some estimator (random variable) $X$ and the expectation is taken over some multivariate Gaussian, a formal way to maybe write this is $$c = E_{\mathcal{N}(\mu, \Sigma)}[X]$$

The only one that I know of is this one here to estimate the permanent of a Hermitian positive semi-definite matrix. There they have access to $N$ samples and don't seem to factor the cost of obtaining the samples into the computation.

I'm curious if there are other "well-known" examples of randomized algorithms where the randomness comes from a Gaussian distribution? I'm curious about how other algorithms factor the cost of obtaining samples into their time complexity. This question is somewhat addressed in this older question.

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ The most famous Johnson-Lindenstrauss construction is probably the one using a matrix of i.i.d. Gaussians. $\endgroup$
    – Yonatan N
    Commented Sep 27, 2022 at 5:01
  • $\begingroup$ There's some Markov chain algorithms, such as the Langevin algorithm or Hamiltonian Monte Carlo, in which the random steps are chosen based on a Gaussian. $\endgroup$
    – smapers
    Commented Sep 27, 2022 at 5:31
  • $\begingroup$ The Gaussian mechanism in differential privacy. $\endgroup$
    – Clement C.
    Commented Sep 27, 2022 at 9:43
  • 2
    $\begingroup$ The Goemans-Williamson 0.878-approximation algorithm for Max-cut uses a random hyperplane, defined by its normal, a Gaussian vector. $\endgroup$
    – GBathie
    Commented Sep 27, 2022 at 12:36

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.