Let $A \in \mathbb{R}^{n \times m}$ be a full-column rank matrix and $x\in\mathbb{R}^n$ be a vector. At the moment I am performing the following computations:
- $Q, R = \texttt{QR}(A)$
- $y = x - 2QQ^\top x$
Is there a way to obtain $y$ without computing the QR decomposition?
Notes
The QR() function that I am using is the scipy.linalg.qr with mode='economic', meaning that $Q$ is a $n\times m$ matrix.
I think it should be possible to do this without computing the QR decomposition because the operation $QQ^\top x$ essentially is a projection of $x$ onto the column space of $Q$. But that same column space is spanned by the columns in $A$..
The projection $\hat x$ of $x$ onto the image of $A$ is $$ \hat x = A(A^T A)^{-1} A^T x. \tag{1} $$ so $y = x - 2 A(A^T A)^{-1} A^T x $.
This is a well known formula in the topic "linear least square problem". If you want to fully understand where it comes from, you can have look on this topic on Wikipedia or, for instance, here.
I'll try to give a quick answer:
In the linear least square problem, we want to find the best approximated solution to the overdetermined system $Au = x$, i.e. find $\hat u$ that minimizes the norm $\|Au - x\|_2$. One can show (see the link) that you can get $\hat u$ by solving the so called normal equation: $$ A^T A u = A^T x. \tag{2} $$ Since $A$ has full column-rank, $A^T A$ is invertible so we obtain $\hat u = (A^T A)^{-1} A^T x$. Now, note that $A \hat u$ is the vector in $\mathrm{im}\, A$ that lies closest to $x$ (recall that $\hat u$ minimizes $\|A u - x\|_2$), so $\hat x = A \hat u$ is the orthogonal projection of $x$ onto $\mathrm{im}\, A$.
In theory, you can use the formulas $(1)$ or $(2)$, but from a computational point of view, this isn't very effective (calculating an inverse matrix is a no-go). That's why the QR-decomposition is often used. Other matrix decompositions, like the singular value decomposition or Cholesky decomposition (for Hermitian positive matrices), can also be used.
Suggested exercise: if you substitute $A=QR$ into the formula $(1)$, you should retrieve $\hat x = QQ^T x$.