3
$\begingroup$

Suppose I have a symmetric positive definite matrix $A \in \mathbb{R}^{n \times n}$ with $n$ linearly indepedent columns $a_1,...a_n$ in $\mathbb{R}^n$. All columns $a_i$ has norm 1, but they are not orthogonal. Consider $P_i = I-a_ia_i^{'}$, which is an orthogonal projection to the orthogonal complement of $a_i$. I want to find the norm (or largest eigenvalue since they are the same) of the symmetric matrix $$P = P_1...P_{n-1}P_nP_{n-1}....P_1$$

Obviously the norm of $P$ is less than or equal to 1, since all $P_i$ has norm 1. If A is an orthonormal matrix, then $P=0$ since every $P_i$ eliminates a indepedent direction in $\mathbb{R}^n$. But for general case, where A is an arbitary matrix with unit column norm, things are unclear.

If any of the $P_i$ are removed from the product to form $\hat{P}$ (for example, $\hat{P}$ is obtained by removing the $P_1$ on left and right from the product), then the norm of $P'$ is exactly 1. This makes sense because in this case, we can find a vector that is in orthogonal complement of $span\{a_2,...,a_n\}$ and it is easy to check this vector is an eigenvector of $\hat{P}$ with eigenvalue 1.

Some observations are obtained from numerical experiments. If I let $A$ to be randomly generated PD matrix whose columns has norm 1, then P has rank n-1.And the norm of $P$ is usually very close to 1 (>0.99 in all trys). However, these results are certainly not general, considering matrix A with orthonormal columns.

Any thoughts that can explain the result of the numerical experiments? And any idea on finding the norm of $P$ given a particular A? Intuitively it has something to do with the norm of A, but I am not sure. Thanks!

$\endgroup$
  • 1
    $\begingroup$ You want to estimate the converge rate of the Kaczmarz method where you sweep back and forth through the rows? I bet there is no easy formula for this. $\endgroup$ – Dirk Nov 30 '18 at 19:37
  • 1
    $\begingroup$ You could also check the paper by Strohmer and Vershynin about the randomized Kaczmarz method where the give a convergence rate for the method (related to the largest eigenvalue) only in terms of simple quantities, but the catch is that you choose the indices of the projections at random. $\endgroup$ – Dirk Nov 30 '18 at 21:22
  • $\begingroup$ @Dirk Thanks a lot and I am looking at the paper. Indeed this is related to double sweep Kaczmarz, and I can try to write this P as I-X where X is several matrices' product (but far less complicated than just expand P). Maybe I should compute the norm in that way, instead of directly looking at the form of P. $\endgroup$ – dave2d Nov 30 '18 at 21:27
2
$\begingroup$

Take a vector $v$ orthogonal to the first $n-1$ $a_i$. The squared norm of $P_nP_{n-1}...P_1v$ is $1-<a_n,v>^2$. Now if the $a_i$'s are independent and uniformly distributed, the expected value of $<a_n,v>^2$ is $1/n$. This is because you can complete $a_n$ in an orthonormal basis $b_i$, and the $<b_i,v>^2$ all have the same expectation, the sum of these expectations being $1$. In fact, it can be shown that the probability that $<a_n,v>^2$ exceeds $1/n$ by a margin $x$ decays very rapidly with $x$ (this is the concentration of measure phenomenon), which explains why you see this in all trials. Now in your case it is slightly different because of the constraint that the matrix is positive definite, so a more delicate argument is required, but basically the idea is similar.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I use random generated matrix just to do some numerical experiements and in fact there is no randomness, and A is a given matrix. Can you elaborate on your first sentence? I don't see immediately why the norm of Pv is this. Thanks! $\endgroup$ – dave2d Nov 30 '18 at 21:21
  • $\begingroup$ as you observed, $v$ is left unchanged by the first $n-1$ operations, so only the last projection affects it. Actually there's a conflict of notations, let me fix this. $\endgroup$ – alesia Nov 30 '18 at 21:26
  • $\begingroup$ But this only means the norm of P_n....P_1v is what you said, and can it explain the effect of close-to-1 norm of P_1...P_n...P_1? $\endgroup$ – dave2d Nov 30 '18 at 21:37
  • $\begingroup$ they're equal, it's just the transpose $\endgroup$ – alesia Nov 30 '18 at 21:38
  • $\begingroup$ Ah, hadn't seen the last P_1 sorry. The norm of that is the maximum square norm of P_n...P_1v for unit v, so it is close to 1 as well $\endgroup$ – alesia Dec 1 '18 at 2:33

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.

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