Return to 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

$$\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.

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.

Let $X$ be a $p \times n$ matrix, with $p > n$ and of maximal rank. 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

$$\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.

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

$$\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.

Let $X$ be a $p \times n$ matrix, with $p > n$. All columns of $X$ have unit Euclidean norm and are in independent positions ($X$ has rank $n$). Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance of 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

$$\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.

Let $X$ be a $p \times n$ matrix, with $p > n$ and of maximal rank. 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

$$\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.