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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Mar 8, 2016 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
    Commented Mar 9, 2016 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
    Commented Mar 10, 2016 at 19:37

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .