4
$\begingroup$

Let $X$ be a $d$-dimensional random vector distributed according to probability measure $D$. At least the second moment of the coordinates of $X$ is finite.

Consider $n+1$ samples $X_0, \ldots, X_n \sim D$. Is it possible to find an upper bound of

$$E_D(\min_{v_1,\ldots, v_n} || X_0 - \sum_{i} v_i X_i||^2)$$

as a function of statistics of $D$? Otherwise stated, is it possible to bound the expected distance of a point sampled from $D$ and the smallest subspace containing $n$ points drawn from the same distribution.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

YES, trivially. Even $E(\|X_0-X_1\|^2)$ is already bounded by 4x the variance. (or even 2x ?)

For $n < d$, this is optimal up to a constant factor. Take the uniform distribution on the $d$ unit vectors. (All (non-centered) moments are 1.) Then the distance is 1 if $X_0$ is distinct from $X_1,\dots,X_n$ and 0 otherwise. The expected distance is thus the probability of the first event: $(1-1/d)^n$. For $n < d$, this is between $1/e$ and $1$.

If the distribution is smooth, then $n\ge d$ makes no sense, the $n$ vectors will span the whole space with probability 1, and the expected distance is 0.

(I had also considered the uniform distribution on the sphere, but after discovering the above example, I was too lazy to calculate the expectation there, although it's just a univariate integral.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ The question is probably about good bounds. $\endgroup$
    – Jochen Wengenroth
    Commented Jan 30, 2013 at 8:24
  • $\begingroup$ Yes, I thought it was obvious that the question was about a tight upper bound. $\endgroup$
    – gappy3000
    Commented Jan 30, 2013 at 20:16
  • 1
    $\begingroup$ Any idea how tight? Anything known about a lower bound? Can we assume the samples are independent? How is $n$ related to $d$? Apparently $n$ does not go to infinity (as it usually does in probability), since $n\ge d$ makes no sense. $\endgroup$
    – Günter Rote
    Commented Jan 31, 2013 at 13:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .