Approximating a subspace by sampling a base without replacement

Question

Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance between the subspace generated by the smaller sample, denoted $S$, and the original column subspace of $X$.

More precisely, I define the distance of a point $a \in R^p$ from a subspace $S$ as $d(a, S) = ||a- \Pi_S a||$, where $\Pi_S$ is the projection operator on $S$.

Then, is it possible to find $\epsilon, \delta$ such that

$$P(\sum_i d(x_i, S)^2 > \epsilon) < \delta$$

Alternatively, I expect that given $\epsilon, \delta$, and the singular values of $X$, one can find the minimum number of samples $m$ satisfying the inequality above.

Since the question is relatively open-ended, I wouldn't mind characterizing any other deviation metric:

$$\sum_i E(d(x_i, S)^2)$$

or even

$$P(\max_i d(x_i, S) > \epsilon) < \delta$$

This seems to me a very basic question, and I would be shocked if it hasn't been fully resolved. I just can't find a reference, and haven't been able to solve it using the tools at hand.

N.B: some clarifications: I did not say that the matrix $X$ is random because it is not. I am a datum of the problem. rather, you can interpret the sampled columns, say $y_i, i=1,\ldots, m$ as sampled from the empirical distribution of columns of $X$. The answer of bunbury misunderstands the question.

Also, I am not using any set-set distance on purpose, but only point-set distances. Gagelman seems thrown off-course by that one.

Answer 1

I don't understand some things here. First, you did not say that the given matrix was random. So it would seem that you either want an upper or lower bound of some kind. You get wildly different answers depending on how far from mutually orthogonal the columns are. For example, if all the columns are the same, then the distance is 0. Second, you say you want a measure of the distance between two spaces but your metric measures the distance between points and a space. If you want the distance between spaces, I would expect some sort of angle (or angles).

Answer 2

Starting with the case where $n = m + 1$, if I understand correctly you can take a point sampled from the uniform distribution on the surface of the unit sphere in $p$-space and obtain $d(x,S)^2$ by ignoring the contribution from the first $m$ coordinates. So using the representation of the uniform distribution on the sphere as a vector of $p$ standard normal random variables: $$x = (X_1, X_2, \dots , X_p)/\sqrt{\sum\limits_{i=1}^n {X_i^2}}$$ we get $$d(x,S)^2 = \sum\limits_{i=m+1}^n{X_i^2}/\sum\limits_{i=1}^n{X_i^2}$$ which is I think, after looking at Wikipedia for $\chi^2$ distributions, a Beta distribution with parameters determined by $m$ and $p$. It looks like the distribution for $\sum\limits_i d(x_i,S)^2$ should then be a sum of iid Beta distributions.

Added in edit. If this is purely about the random subspace I don't think there is much that can be said without more info about $X$. If all the columns are orthogonal then $\sum\limits_i d(x_i,S)^2 = n-m$ while for any $\epsilon>0$ there are configurations where it is an upper bound for the sum for any simplex. That means that $P(\sum\limits_i d(x_i,S)^2 > n-m) = 0$ is the best that can be said without further qualification.

Something might be possible by using the covariance matrix or volumes and Cayley Menger determinants of subsimplices of the simplex made of the points in $X$ and the origin to control the lengths but it won't be straightforward because the geometry of simplices is a complicating factor. If the object of interest were a hypercuboid instead of a simplex, the problem would become purely combinatorical whereas in the simplex the relevant lengths vary between the pairwise distances and each point's opposite face. However even in the rectilinear case the distributions of sums of squared lengths depend strongly on the distribution of individual lengths and can be very complex even if the size of the sample of subsets of X is huge.