# An elementary probability question

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.

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.
• 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. – Günter Rote Jan 31 '13 at 13:26