User denis - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:39:15Z http://mathoverflow.net/feeds/user/6749 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/99452/inflate-a-simplex-change-rows-to-make-the-rank-n Inflate a simplex, change rows to make the rank n denis 2012-06-13T14:31:23Z 2012-06-13T15:31:05Z <p>I have a simplex, n + 1 points in $\mathbb{R}^n$, which may have rank $r &lt; n$.<br> Is there a cheap way of "inflating" it to rank $n$, changing a few, all but $r$, of the points ? </p> <p>The points are also ordered, rows 1 2 3 $\dots$ in a matrix, and I'd like to keep as many of the leading rows as possible unchanged.</p> http://mathoverflow.net/questions/9854/uniformly-sampling-from-convex-polytopes/99232#99232 Answer by denis for Uniformly Sampling from Convex Polytopes denis 2012-06-10T11:30:12Z 2012-06-10T13:00:04Z <p>A case with a fast simple method: to sample the "right simplex" $\ \sum{x_i} \le 1,\ x_i \ge 0$:</p> <ol> <li>sample in $\sum{x_i} = 1$ by taking i.i.d. exponentials scaled to sum 1</li> <li>scale by random-uniform$^\frac{1}{dim}$.</li> </ol> <p>(I have no idea how to generalize this.) <hr> In Python with NumPy, this is</p> <pre><code>def random_simplex_sum1( N, dim ): """ N uniform-random points &gt;= 0, sum x_i == 1 """ X = np.random.exponential( size=(N,dim) ) X /= X.sum(axis=1)[:,np.newaxis] return X def random_simplex_le1( N, dim ): """ N uniform-random points &gt;= 0, sum x_i &lt;= 1 """ return random_simplex_sum1( N, dim ) \ * (np.random.uniform( size=N ) ** (1/dim)) [:,np.newaxis] </code></pre> http://mathoverflow.net/questions/89392/place-n-telescopes-on-a-sphere-in-rd-to-see-the-whole-sky Place n telescopes on a sphere in R^d to see the whole sky denis 2012-02-24T13:09:32Z 2012-02-25T17:39:21Z <p>Where would one put $n$ telescopes on the surface of the earth to see the whole sky as well as possible ?<br> Use the cosine metric to define how well we can see in direction $x$:<br> $\qquad \text{cansee}( x; x_1 \dots x_n ) = \text{max}_i \ x \cdot x_i$<br> The worst direction for all the telescopes is then<br> $\qquad \text{worstsee}( x_1 \dots x_n ) = \text{min}_x \ \text{cansee}( x )$<br> and we want $n$ telescope positions that maximize that, i.e. that can see pretty well even in the worst direction.</p> <p>That's in $R^3$. What I really want to do is generate approximate solutions on a sphere in $R^d$ for $3 &lt;= d &lt;= 10$ and $d+1 &lt;= n &lt; 2d$.<br> "Very approximate" would do; with &lt; 20 points, an iterative method would do.</p> <p>(Feel free to change the metric if min-max is intractable.)</p> http://mathoverflow.net/questions/43652/estimate-density-of-k-points-in-rn-from-their-distances estimate density of k points in Rn from their distances ? denis 2010-10-26T10:14:58Z 2010-10-26T14:41:15Z <p>In a random point cloud in R<sup>n</sup>, say d<sub>1</sub> &lt;= d<sub>2</sub> &lt;= ... d<sub>k</sub> are the distances of the k points nearest the origin &mdash; I know only their distances, not their coordinates. What's a "good" estimate of the point density near 0 ?</p> <p>In density estimation in statistics, it seems common to use vol<sub>k</sub> = k / d<sub>k</sub><sup>n</sup> for a fixed k, not using d<sub>1</sub> d<sub>2</sub> ... at all.<br> For example, one could take a weighted average of the naive vol<sub>1</sub> vol<sub>2</sub> ..., but with what weights ?</p> <p>Added, re convex hull: can't say &mdash; 0 might not even be in the convex hull (cf. Wendel's formula). So there are two related but separate questions: estimating volume (answered by Joseph O'Rourke's reference), and estimating density.</p> <p>(Experts, please add tags.)</p> http://mathoverflow.net/questions/32442/how-to-generate-a-net-on-a-8-dimensional-sphere/33661#33661 Answer by denis for How to generate a net on a 8-dimensional sphere denis 2010-07-28T14:49:41Z 2010-08-03T12:28:32Z <p>Shells of evenly spaced lattice points:</p> <p>To generate evenly spaced sets of non-random points on an n-sphere, start with the permutations of { 0 1 1 ... 2 2 ... }, then make 2^n flips of that. For example, in 4-space start with the 12 permutations of { 0 1 1 2 }. Each point is &radic;6 from the origin, and each has 4 neighbours &radic;2 away (+1 here, -1 there):</p> <pre><code>0 1 1 2 0 1 2 1 0 2 1 1 1 0 1 2 1 1 0 2 </code></pre> <p>Make 2^4 sign-flipped copies of this, i.e. multiply by { 1 1 1 1 } .. { -1 -1 -1 -1 } except where there's a 0. This gives a shell of 96 points, 0 1 1 2 .. 0 -1 -1 -2. Each is &radic;6 from the origin, and each now has 6 neighbours &radic;2 away.</p> <p>For the 8-sphere, start with the 280 permutations of { 0 1 1 1 1 2 2 2 }. Each has of course the same distance from the origin, and each has 12 neighbours &radic;2 away &mdash; a nice, regular graph. The shell of 280 * 2^7 = 35840 sign-flipped points is not quite 3^10, but.</p> <p>(I'd appreciate links to papers or programs on such graphs.)</p> http://mathoverflow.net/questions/32365/combining-variances/33772#33772 Answer by denis for Combining variances denis 2010-07-29T10:34:13Z 2010-07-29T10:34:13Z <p>(Basic, not research level &mdash; tag all such "basic" please):<br> see <a href="http://en.wikipedia.org/wiki/Variance" rel="nofollow">Variance</a>: "the variance of the total group is equal to the mean of the variances of the subgroups, plus the variance of the means of the subgroups" &mdash; for equal subgroup sizes.<br> You could cook up the corresponding formula for different subgroup sizes, but why not just take the variance of all m1 + m2 + ... measurements pooled together ? See also the little example in <a href="http://stackoverflow.com/questions/3307186/how-do-i-measure-variability-of-a-benchmark-comprised-of-many-sub-benchmarks">SO how-do-i-measure-variability</a>.</p> http://mathoverflow.net/questions/33657/best-p-for-inverse-distance-weighting best p for inverse distance weighting ? denis 2010-07-28T14:12:19Z 2010-07-28T14:12:19Z <p><a href="http://en.wikipedia.org/wiki/Inverse_distance_weighting" rel="nofollow">Inverse distance weighting</a> is a common way of interpolating values z<sub>j</sub> at scattered data points X<sub>j</sub> in Rn:</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;idw(P) = &Sigma; w<sub>j</sub> z<sub>j</sub> / &Sigma; w<sub>j</sub><br> &nbsp;&nbsp;&nbsp;&nbsp;w<sub>j</sub> = f( |P - X<sub>j</sub>| )<br> &nbsp;&nbsp;&nbsp;&nbsp;f(d) = 1 / d<sup>p</sup></p> <p>Is there a "best" p, for say X<sub>j</sub> uniformly distributed in the unit cube and z(X) = cos( c . X ) + normal noise ?<br> (For that matter, is there a rationale for 1/d at all -- why not say Gaussian ?)</p> <p>The Wikipedia article say that IDW minimizes a &phi;(x,u) which looks like least squares minimization with variance ~ distance<sup>p</sup>: maybe a connection to least squares, maybe not.</p> <p>(Please add tag "interpolation", thanks.)</p> http://mathoverflow.net/questions/33112/estimate-probability-0-is-in-the-convex-hull-of-n-random-points Estimate probability( 0 is in the convex hull of N random points ) ? denis 2010-07-23T17:00:39Z 2010-07-26T11:48:54Z <p>Can anyone estimate N such that Prob( 0 is in the convex hull of $N$ points ) >= .95<br> for points uniformly scatterered in $[-1,1]^d$, $d = 2, 3, 4, 10$ ?</p> <p>The application is nearest-neghbour interpolation: given values $z_j$ at sample points $X_j$, and a query point $P$, one chooses the $N$ $X_j$ nearest to $P$ ($N$ fixed) and averages their $z_j$. If $P$ is not in the convex hull of the $N$ $X_j$, the interpolation will be one-sided, not so good.<br> I'd like to be able to say "taking 6 neighbors in 2d, 10 in 3d, is seldom one-sided".</p> <p>If anyone could point me to selfcontained pseudocode for the function Inhull( $N$ points ) (without calling full LP), that would be useful too.</p> <p>(Please add tags interpolation convex-geometry ?)</p> http://mathoverflow.net/questions/27838/random-cities-scatter-cluster-parameters-ca-point-set-then-randomgenc random cities: scatter / cluster parameters C(a point set) then randomgen(C) ? denis 2010-06-11T17:09:04Z 2010-06-11T17:09:04Z <p>An example: given the coordinates of say 1000 cities in the USA, are there a few parameters which describe how they scatter / cluster,</p> <pre><code>C = clusterparams( cities ) </code></pre> <p>which can then drive a random point generator</p> <pre><code>randomcities = randomgen( C ) </code></pre> <p>so that</p> <pre><code>clusterparams( randomcities ) ~ C </code></pre> <p>i.e. the random cities scatter/cluster "like" the real cities ?<br> In general, I have N points in (typically) R2 or R3, and want to generate synthetic data for kd* trees.</p> http://mathoverflow.net/questions/99452/inflate-a-simplex-change-rows-to-make-the-rank-n/99459#99459 Comment by denis denis 2012-06-14T15:41:51Z 2012-06-14T15:41:51Z Thanks @Andrew. Won't the result depend heavily on which row you subtract / add back at the end ? http://mathoverflow.net/questions/89392/place-n-telescopes-on-a-sphere-in-rd-to-see-the-whole-sky Comment by denis denis 2012-02-24T17:06:01Z 2012-02-24T17:06:01Z @Igor, from playing with noisy optimization: Nelder-Mead tracks d+1 points. (You're welcome to unrestrict ...) http://mathoverflow.net/questions/43652/estimate-density-of-k-points-in-rn-from-their-distances Comment by denis denis 2010-10-26T11:57:20Z 2010-10-26T11:57:20Z @Boris, anything you can analyze :) the q said &quot;uniformly distributed&quot;, exponential would be nice http://mathoverflow.net/questions/33112/estimate-probability-0-is-in-the-convex-hull-of-n-random-points/33132#33132 Comment by denis denis 2010-07-28T15:14:09Z 2010-07-28T15:14:09Z Thanks Andrey, nice. Found another exposition, also following Wendel: <a href="http://www.mathpages.com/home/kmath327/kmath327.htm" rel="nofollow">mathpages.com/home/kmath327/kmath327.htm</a>