bio | website | cs.cmu.edu/~odonnell |
---|---|---|
location | ||
age | ||
visits | member for | 4 years, 9 months |
seen | 3 hours ago | |
stats | profile views | 981 |
Jul 20 |
answered | Random RSK and Plancherel Measure |
Jul 2 |
awarded | Curious |
Jun 4 |
awarded | Revival |
Jan 13 |
awarded | Nice Question |
Jan 3 |
comment |
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
essentially needs to know a point inside the convex set to "get started". Since your set is an explicitly given intersection of n halfspaces, it should be straightforward to explicitly obtain such a point. In other words, I feel that it should be possible to work around the requirement and apply the Cousins-Vempala paper to your setting. |
Jan 3 |
comment |
Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector
Ah, good question. Okay, it occurs to me now that for relative accuracy $\epsilon$ you should be able to do it in time $\mathrm{poly}(n/\epsilon)$ using this paper of Cousins and Vempala (or those that it cites): arxiv.org/abs/1306.5829 It gives such an approximation for the Gaussian volume of any convex set, in fact. A small catch is that it requires some technical condition like the set containing the unit ball. However, from what I know of this subject, that is not a very strict requirement. It's more like a simple example of a possible requirement; really, the algorithm just |
Jan 3 |
answered | Computation complexity of calculating the cdf of an n-th dimensional gaussian random vector |
Nov 27 |
awarded | Citizen Patrol |
Nov 13 |
answered | Cardinality of intersection of a random subset with a fixed subset |
Oct 26 |
awarded | Enthusiast |
Oct 22 |
accepted | What are good English-language sources for reading about the Luzin affair? |
Oct 19 |
awarded | Informed |
Oct 19 |
comment |
Convergence of orthogonal polynomial expansions
Oh, I guess the desired uniform convergence statement from in #1 probably follows from Egorov's theorem. |
Oct 19 |
answered | Convergence of orthogonal polynomial expansions |
Oct 18 |
awarded | Yearling |
Oct 14 |
asked | What are good English-language sources for reading about the Luzin affair? |
Oct 8 |
awarded | Constituent |
Oct 3 |
awarded | Quorum |
Oct 3 |
awarded | Caucus |
Oct 1 |
answered | For interior point methods of linear programming, what is the “L” in the computational complexity $\mathcal{O}(n^3 L)$? |