Let $x_i, y_i \in \mathbb{R}^n$ for $i=1, \dots, k < n$ satisfy $$ \sum_{i=1}^k x_i^\top y_i = 0. $$ Let $E$ be a random subspace of dimension $m < n$ in $\mathbb{R}^n$ distributed uniformly on the Grassmannian $G_m(\mathbb{R}^n)$ and let $P_E$ be orthogonal projection onto $E$. What is the value of $$ \mathbb{E}\left[ \left(\sum_{i=1}^k x_i^\top P_E y_i \right)^2 \right] = \dots ? $$ Any references or suggestions would also be very helpful.

It's quite easy to get an upper bound using Johnson-Lindenstrauss style arguments but I feel that this should be possible to compute exactly. Also (by orthogonal invariance) the first moment vanishes.


1 Answer 1


It suffices to calculate $\mathbb E ( (P_E)_{ab} (P_E)_{cd})$ for all $1\leq a,b,c,d\leq n$, or, equivalently, calculate $\mathbb E( P_E \otimes P_E ) \in \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n$.

This is an $O(n)$-invariant tensor. The space of $O(n)$-invariant tensors in $\mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n \otimes \mathbb R^n$ is three-dimensional, generated by the three "diagonal" tensors. Thus

$$\mathbb E ( (P_E)_{ab} (P_E)_{cd}) = C_1 \delta_{a=b}\delta_{c=d}+ C_2 \delta_{a=c} \delta_{b=d} + C_3 \delta_{a=c} \delta_{b=d}$$ for some $C_1, C_2, C_3 \in \mathbb R$.

We have $$ m^2 = \sum_{i=1}^n (P_E)_{ii} \sum_{j=1}^n (P_E)_{jj} = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ii} (P_E)_{jj}) = n^2 C_1 + n C_2 + n C_3 $$

We have $$ m = \sum_{i=1}^n \sum_{j=1}^n (P_E)_{ij}^2 = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ij} (P_E)_{ji}) = n C_1 + n C_2 + n ^2 C_3 $$

and similarly

$$ m = \sum_{i=1}^n \sum_{j=1}^n (P_E)_{ij}^2 = \sum_{i=1}^n \sum_{j=1}^n \mathbb E ( (P_E)_{ij} (P_E)_{ij}) = n C_1 + n^2 C_2 + n C_3 $$

This gives $$C_1 = \frac{(m^2-m) (n+2) + m (n-m)}{n (n-1) (n+2) } , C_2 = \frac{m (n-m)}{ n (n-1)(n+2)}, C_3 = \frac{ m (n-m)}{ n (n-1) (n+2) } $$

We have

$$\mathbb E \left[ \left( \sum_{i=1}^k x_i^T P_E y_i\right)^2 \right] = \mathbb E\left[ \sum_{i=1}^k \sum_{j=1}^k x_i^T P_E y_i x_j^T P_E y_j \right]$$ $$ = C_1 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_i) (x_j \cdot y_j) + C_2 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot x_j) (y_i \cdot y_j) + C_3 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_j) (y_i \cdot x_j) $$

Your first term vanishes by assumption, so we get

$$ \frac{m (n-m)}{ n (n-1) (n+2) } \left( \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot x_j) (y_i \cdot y_j) + C_3 \sum_{i=1}^k \sum_{j=1}^k (x_i \cdot y_j) (y_i \cdot x_j) \right).$$

Expressed in terms of the matrix $M = \sum_{i=1}^k x_i y_i^T$, this is

$$ \frac{m (n-m)}{ n (n-1) (n+2) }\operatorname{tr}( M M^T + M^2).$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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