User denis - MathOverflow

Inflate a simplex, change rows to make the rank n

2012-06-13T14:31:23Z

I have a simplex, n + 1 points in $\mathbb{R}^n$, which may have rank $r < n$.
Is there a cheap way of "inflating" it to rank $n$, changing a few, all but $r$, of the points ?

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.

Answer by denis for Uniformly Sampling from Convex Polytopes

2012-06-10T11:30:12Z

A case with a fast simple method: to sample the "right simplex" $\ \sum{x_i} \le 1,\ x_i \ge 0$:

sample in $\sum{x_i} = 1$ by taking i.i.d. exponentials scaled to sum 1
scale by random-uniform$^\frac{1}{dim}$.

(I have no idea how to generalize this.)

In Python with NumPy, this is

def random_simplex_sum1( N, dim ):
    """ N uniform-random points >= 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 >= 0, sum x_i <= 1 """ 
    return random_simplex_sum1( N, dim ) \
        * (np.random.uniform( size=N ) ** (1/dim)) [:,np.newaxis]

Place n telescopes on a sphere in R^d to see the whole sky

2012-02-24T13:09:32Z

Where would one put $n$ telescopes on the surface of the earth to see the whole sky as well as possible ?
Use the cosine metric to define how well we can see in direction $x$:
$ \qquad \text{cansee}( x; x_1 \dots x_n ) = \text{max}_i \ x \cdot x_i $
The worst direction for all the telescopes is then
$ \qquad \text{worstsee}( x_1 \dots x_n ) = \text{min}_x \ \text{cansee}( x )$
and we want $n$ telescope positions that maximize that, i.e. that can see pretty well even in the worst direction.

That's in $R^3$. What I really want to do is generate approximate solutions on a sphere in $R^d$ for $3 <= d <= 10$ and $d+1 <= n < 2d$.
"Very approximate" would do; with < 20 points, an iterative method would do.

(Feel free to change the metric if min-max is intractable.)

estimate density of k points in Rn from their distances ?

2010-10-26T10:14:58Z

In a random point cloud in Rⁿ, say d₁ <= d₂ <= ... d_k are the distances of the k points nearest the origin — I know only their distances, not their coordinates. What's a "good" estimate of the point density near 0 ?

In density estimation in statistics, it seems common to use vol_k = k / d_kⁿ for a fixed k, not using d₁ d₂ ... at all.
For example, one could take a weighted average of the naive vol₁ vol₂ ..., but with what weights ?

Added, re convex hull: can't say — 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.

(Experts, please add tags.)

Answer by denis for How to generate a net on a 8-dimensional sphere

2010-07-28T14:49:41Z

Shells of evenly spaced lattice points:

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 √6 from the origin, and each has 4 neighbours √2 away (+1 here, -1 there):

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 √6 from the origin, and each now has 6 neighbours √2 away.

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 √2 away — a nice, regular graph. The shell of 280 * 2^7 = 35840 sign-flipped points is not quite 3^10, but.

(I'd appreciate links to papers or programs on such graphs.)

Answer by denis for Combining variances

2010-07-29T10:34:13Z

(Basic, not research level — tag all such "basic" please):
see Variance: "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" — for equal subgroup sizes.
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 SO how-do-i-measure-variability.

best p for inverse distance weighting ?

2010-07-28T14:12:19Z

Inverse distance weighting is a common way of interpolating values z_j at scattered data points X_j in Rn:

    idw(P) = Σ w_j z_j / Σ w_j
    w_j = f( |P - X_j| )
    f(d) = 1 / d^p

Is there a "best" p, for say X_j uniformly distributed in the unit cube and z(X) = cos( c . X ) + normal noise ?
(For that matter, is there a rationale for 1/d at all -- why not say Gaussian ?)

The Wikipedia article say that IDW minimizes a φ(x,u) which looks like least squares minimization with variance ~ distance^p: maybe a connection to least squares, maybe not.

(Please add tag "interpolation", thanks.)

Estimate probability( 0 is in the convex hull of N random points ) ?

2010-07-23T17:00:39Z

Can anyone estimate N such that Prob( 0 is in the convex hull of $N$ points ) >= .95
for points uniformly scatterered in $[-1,1]^d$, $d = 2, 3, 4, 10$ ?

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.
I'd like to be able to say "taking 6 neighbors in 2d, 10 in 3d, is seldom one-sided".

If anyone could point me to selfcontained pseudocode for the function Inhull( $N$ points ) (without calling full LP), that would be useful too.

(Please add tags interpolation convex-geometry ?)

random cities: scatter / cluster parameters C(a point set) then randomgen(C) ?

2010-06-11T17:09:04Z

An example: given the coordinates of say 1000 cities in the USA, are there a few parameters which describe how they scatter / cluster,

C = clusterparams( cities )

which can then drive a random point generator

randomcities = randomgen( C )

so that

clusterparams( randomcities ) ~ C

i.e. the random cities scatter/cluster "like" the real cities ?
In general, I have N points in (typically) R2 or R3, and want to generate synthetic data for kd* trees.

Comment by denis

2012-06-14T15:41:51Z

Thanks @Andrew. Won't the result depend heavily on which row you subtract / add back at the end ?

Comment by denis

2012-02-24T17:06:01Z

@Igor, from playing with noisy optimization: Nelder-Mead tracks d+1 points. (You're welcome to unrestrict ...)

Comment by denis

2010-10-26T11:57:20Z

@Boris, anything you can analyze :) the q said "uniformly distributed", exponential would be nice

Comment by denis

2010-07-28T15:14:09Z

Thanks Andrey, nice. Found another exposition, also following Wendel: mathpages.com/home/kmath327/kmath327.htm