Approximating a subspace by sampling a base without replacement - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T15:37:24Z http://mathoverflow.net/feeds/question/118313 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118313/approximating-a-subspace-by-sampling-a-base-without-replacement Approximating a subspace by sampling a base without replacement gappy3000 2013-01-07T21:52:57Z 2013-05-16T07:22:00Z <p>Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m &lt; 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$.</p> <p>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$.</p> <p>Then, is it possible to find $\epsilon, \delta$ such that</p> <p>$$P(\sum_i d(x_i, S)^2 > \epsilon) &lt; \delta$$</p> <p>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.</p> <p>Since the question is relatively open-ended, I wouldn't mind characterizing any other deviation metric:</p> <p>$$\sum_i E(d(x_i, S)^2)$$</p> <p>or even </p> <p>$$P(\max_i d(x_i, S) > \epsilon) &lt; \delta$$</p> <p>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.</p> <p>N.B: some clarifications: I did not say that the matrix $X$ is random because it is <em>not</em>. 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.</p> <p>Also, I am not using any set-set distance on purpose, but only point-set distances. Gagelman seems thrown off-course by that one.</p> http://mathoverflow.net/questions/118313/approximating-a-subspace-by-sampling-a-base-without-replacement/118323#118323 Answer by bunbury for Approximating a subspace by sampling a base without replacement bunbury 2013-01-08T00:51:45Z 2013-01-10T01:40:38Z <p>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. </p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/118313/approximating-a-subspace-by-sampling-a-base-without-replacement/118331#118331 Answer by vxf for Approximating a subspace by sampling a base without replacement vxf 2013-01-08T04:15:43Z 2013-01-08T04:15:43Z <p>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).</p>