# Approximating a subspace by sampling a base without replacement

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.

-
I'm not understanding what you mean by "sampling $m$ columns from X without replacement;" why isn't $S \subset span(X)$ according to what you've written down? –  Jerry Gagelman Jan 8 '13 at 0:53
It means sampling $m$ elements out of $n$ without replacement. The probability distribution is $$P(k_1,\ldots, k_m)= {n\choose m}^{-1}$$ yes, it's $S\subset \text{span}(X)$. –  gappy3000 Jan 8 '13 at 2:46

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

-
I see now that you can not mean to measure the distance between the whole subspace and the sample subspace because that distance is going to be zero as a previous comment has mentioned. Instead, you are looking at the distance between each vector and the whole subspace. However, this depends heavily on the matrix as I mentioned. If the columns in the matrix are orthogonal, then the angles between the vectors and the subspace are either 0 or pi/2. –  vxf Jan 8 '13 at 4:52
So now I think I get the bunbury comment. If we assume that we start with a fixed subspace S and then choose a random sequence of new vectors from the space X (in other words, the matrix is going to be generated at random) and ask for the distribution of angles between these new vectors and S then this is equivalent to choosing a random sequence of unit vectors in X. To answer that, we only have to compute the distribution for a single vector in X. Isn't this the same as putting a hyperplane through the origin of a sphere? –  vxf Jan 8 '13 at 5:09
See clarification to the question. The matrix is given. –  gappy3000 Jan 8 '13 at 14:38

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.

-