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.

(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.

  • 3
    $\begingroup$ The question is probably about good bounds. $\endgroup$ – Jochen Wengenroth Jan 30 '13 at 8:24
  • $\begingroup$ Yes, I thought it was obvious that the question was about a tight upper bound. $\endgroup$ – gappy3000 Jan 30 '13 at 20:16
  • $\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 Jan 31 '13 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.