Understanding this matrix expansion

71 Views Asked by At

EDIT: With help from user8675309, it seems the answer to my question is that $Q$ and $R$ are obtained from a reduced $QR$ decomposition, not a full one. As a consequence, $R$ is a square matrix, and $Q^\top Q = I$ but $QQ^\top \neq I$. This resolves my question below.

In my current studies, I have come across the following reformulation:

$$I - A(A^\top A)^{-1}A^\top = I - QQ^\top \tag{1}$$

where $A$ is a $N\times D$ matrix, I is the $N\times N$ identity matrix, and $Q$ is obtained from the QR decomposition of $A$, i.e.: $QR=A$.

Below are my attempts to follow this derivation.

First off, I assume I may not directly invert $(A^\top A)^{-1}$ as $(A^\top A)^{-1}=A^{-1}A^{-\top}$ because $A$ is not square. If I were allowed to do this, the RHS of Equation 1 would become $I$ and the entire term would be zero. Correct?

So I believe we instead make use of the QR decomposition. Plugging the $QR=A$ into the LHS of equation 1 yields:

$$I - QR((QR)^\top QR)^{-1}(QR)^\top$$

Expanding the tranpose yields:

$$I - QR(R^\top Q^\top QR)^{-1}R^\top Q^\top$$

Since $Q$ is an orthogonal matrix (edit: I initially assumed the QR decomposition was a full decomposition), we have $Q^\top Q=I$, which yields:

$$I - QR(R^\top R)^{-1}R^\top Q^\top$$

Now if I were to invert $R^\top R$ as $(R^\top R)^{-1}=R^{-1}R^{-\top}$ I would obtain:

$$I - QRR^{-1}R^{-\top}R^\top Q^\top$$

which, using the identities $RR^{-1}=I$ and $R^{-\top}R^\top=I$ yields the RHS of equation 1:

$$I - Q Q^\top$$

Now my question: It seems to me that I am allowed to invert $(R^\top R)^{-1}$ but not $(A^\top A)^{-1}$. Why? Neither matrix appears to be square. Does this have anything to do with the fact that $R$ is upper triangular and $A$ is generally not?