2
$\begingroup$

Given fixed real symmetric $D\in\mathbb{R}^{n\times n}$ with $n$ distinct eigenvalues, let $U$ be a random orthogonal matrix selected uniformly from the space of $n\times n$ orthogonal matrices, and denote the first $m$ columns of $U$ as the rectangular matrix $Q\in\mathbb{R}^{n\times m}$. Then we say that the matrix $QQ^T$ is a random orthogonal projection over $\mathbb{R}^n$ of rank $m$.

We are interested in the quantity $$\mu=\lambda_\min(D+QQ^T) - \lambda_\min(D)$$ when the rank of the projection satisfies $m\in\Omega(n)$. Of course, $0 \le \mu \le 1$. But given that $Q$ is randomly selected, the decoherence between the bases of $D$ and $Q$ causes the distribution of $\mu$ to lie strictly in between the two extremes. For sufficiently large $n$ the following statements should hold:

  1. The event $\mu=0$ occurs with probability zero.
  2. The expectation $\mathbb{E}\{\mu\}$ is bounded from below by an absolute constant.
  3. The distribution of $\mu$ concentrates about $\mathbb{E}\{\mu\}$.

Indeed, all three statements are readily confirmed using numerical simulations. But how might we go about proving these statements?


Numerical example. We sample $\mu$ for $n\in\{10,30,100,300\}$ and $m=n/4$, performing 1000 trials for each $n$. Initially, $D$ is set to be a diagonal matrix with random Gaussian entries, and this is fixed for all trials.

Numerical example


Remark 1. Since $D$ is fixed, we can, WLOG, assume that $D$ is positive definite and / or diagonal.

Remark 2. Many of the existing work on random orthogonal projections use standard Gaussians to approximate a few orthonormal columns. But with as many columns as $m\in\Omega(n)$, the approach is no longer valid. See Jiang, Tiefeng. "How many entries of a typical orthogonal matrix can be approximated by independent normals?" The Annals of Probability 34.4 (2006): 1497-1529.

$\endgroup$
  • $\begingroup$ Assuming that $\lambda_n \equiv \lambda_\min$, of course, $\lambda_\min(QQ^T)=0$ for all $m<n$, so that bound simply gives the trivial result that $\mu\ge0$. In the case of $m=n$, we have $QQ^T=UU^T=I_n$, but that yields the other trivial result that $\mu \le 1$. (I had defined $Q$ to be the first $m$ columns of $U$. This is just a more rigorous way of saying "$m$ random orthonormal columns", using language taken from Jiang's paper) $\endgroup$ – Richard Zhang Mar 8 '16 at 15:58
  • $\begingroup$ I removed the previous comments because they don't help. Perhaps this proves helpful, though am not sure about it. Considering $D+uu^T$ may still be interesting, in particular, because we know that the eigenvalues of this perturbed matrix are the roots of $f(\lambda) := 1+\sum_i \frac{u_i^2}{d_i-\lambda}$. Alternatively, since the eigenvalues of the perturbed matrix are of the form $d_i+\nu_i$ for $0\le \nu_i \le 1$, we can consider solving for $\nu$. $\endgroup$ – Suvrit Mar 9 '16 at 15:17
  • $\begingroup$ Thanks Suvrit. Looking at the rank-1 case immediately proves that $\mathbf{Pr}(\mu=0) = 0$, because the event can only occur if $u$ is exactly orthogonal to the rank-1 eigenspace associated with the smallest eigenvalue. Still working on statements 2 and 3.... $\endgroup$ – Richard Zhang Mar 10 '16 at 19:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.