0
$\begingroup$

Here I define my "orthogonal" matrix $Q$ as having orthonormal columns, but not necessarily orthonormal rows, and $Q$ need not be square - this definition clashes with standard ones a bit, but it is consistent with the video I was watching, involving a proof of the least square method using QR decomposition.

$Q^TQ=I$ always, as the product amounts to the dot products of the columns with the columns, which will produce only $1$ or $0$ due to the orthonormality of $Q$, but $QQ^T$ is the rows dot the rows, so not necessarily the identity matrix, and particularly as $Q$ is not necessarily square I do not know how to make sense of the following:

Suppose $x$ is some vector in $\mathbb{R}^m$, where $Q\in\mathbb{M}_{m\times n}$, and $x$ is not in the column space of $Q$. Apparently, the orthogonal projection of $x$ onto the column space of $Q$, $\hat{x}$, is $QQ^Tx$!

I have tried to expand $(x-\hat{x})\cdot\hat{x}=0$ many times, many ways, all to no avail. The computation of $x\cdot (QQ^Tx)$ and $(QQ^Tx)\cdot (QQ^Tx)$ is a nightmare, and I have not shown them to be equivalent - I don't know how.

Does anyone know how to A) prove this and B) give an intuition for this?

When $Q$ is square and standardly orthogonal, i.e. the rows also form an orthonormal set, then $Q$ and $Q^T$ are just rotations that invert each other and it is all intuitive... but this $QQ^T$ in a non-square, not completely orthogonal setting makes no sense to me.

$\endgroup$
1
  • 1
    $\begingroup$ If $Q$ is $m \times n$, then $Q^TQ$ only equals $I_n$ if $n\le m$. For your intuition, and proof, express $x$ as a linear combination of the columns of $Q$ and vectors that span the orthogonal complement of the column space of $Q$. $\endgroup$
    – Joe
    Commented Jul 11, 2021 at 12:55

3 Answers 3

2
$\begingroup$

The orthogonal projection $P_V$ to a subspace $V$ is the unique linear transformation such that:

  1. for any $v\in V$ we have $P_V(v)=v$ and
  2. for any $u\in V^\perp$ we have $P_V(v)=0$.

Now, for $V$ the column space of $Q$:

  1. $v\in V$ means $v=Qw$ for some $w$. Then $QQ^Tv=QQ^TQw=Qw=v$
  2. $u\in V^\perp$ means $u\in \ker Q^T$. Then $QQ^Tu=Q0=0$.

Thus $P_V=QQ^T$.

For a more general matrix $A$ with linearly independent columns, projection onto its column space is given by $A(A^TA)^{-1}A^T$ for the same reason. This is a standard formula in "least squares".

The above reasoning only allows us to check the answer once we know it. To come up with it in the first place, we can reason as follows. Let column space of $Q$ be $V$. Then the rows of $Q^T$ are a set of relations that need to hold for a vector to be orthogonal to $V$. That is, the rows of $Q^T$ record all the things that need to vanish for a vector to be in $V^\perp$. So any linear map $P$ vanishes on $V^\perp$ precisely when it "factors through" $Q^T$, that is when it is a composition of something with $Q^T$, i.e. $P=MQ^T$.

Now, in order for $P$ to then be identity on $V$ itself, we must have $PQw=Qw$, so we must have $MQ^TQw=Qw$. But for us $Q^TQ=Id$. So $M=Q$ and so $P=QQ^T$.

$\endgroup$
2
  • $\begingroup$ I will read this over thanks - great detail. Is there a typo in “1.”, the first numbered equation? I’m a touch confused and feel as if $v,w$ have been mixed up but I’m not sure $\endgroup$
    – FShrike
    Commented Jul 11, 2021 at 17:34
  • 1
    $\begingroup$ Yes, thanks for spotting that. I've edited it. $\endgroup$
    – Max
    Commented Jul 11, 2021 at 17:54
1
$\begingroup$

With thanks to Joe's comment:

Let $x$ be the vector not in the column space of $Q$ that we want to project. $x$ is going to be in the combined span of the columns of $Q$, and the columns of the orthogonal complement of $Q$, which I will denote $Q^\perp$. The components of $x$ w.r.t $Q$ will be the orthogonal projection. Thus, letting $A$ and $B$ be vectors encoding the linear combinations thereof,

$$ \begin{align*} \\x&=QA+Q^\perp B \\Q^Tx&=Q^TQA+Q^TQ^\perp B=A \\QQ^Tx&=QA=\hat{x} \end{align*} $$

The product $Q^TQ^\perp=0$ because every entry of the product will be the dot product of a row of $Q^T$, therefore a column of $Q$, and a column of $Q^\perp$, and by definition those columns are orthogonal to all the columns of $Q$, therefore the dot product is zero everywhere, zeroing out the $B$ part in the above equations. $Q^TQ$ is also the identity, assuming as Joe also said that there no more columns in $Q$ than rows (which is a safe assumption, since $Q$ couldn't really be called orthogonal in any sense if that were not true, as its columns wouldn't be linearly independent).

And we are done. Hope this helps.

$\endgroup$
0
$\begingroup$

This is relatively easy to prove for the case where $Q$ is simply a column vector $Q=u$ such that $u^Tu=1$ and generalizes readily from there. Consider $P = uu^T$. We'll need some basic facts about matrix multiplication to prove that this is the orthogonal projection onto the subspace spanned by $u$. First, $P$ is symmetric because $P^T = (uu^T)^T=(u^T)^Tu^T=uu^T=P$. Now for any $x$ we have that $Px=(uu^T)x = u(u^Tx)= (u^Tx) u$ because $u^Tx$ is just the dot product of $u$ and $x$, ie a scalar. This means $Px$ is in the subspace spanned by $u$. To see that $P$ is a projection we calculate $P^2=(uu^T)^2=(uu^T)(uu^T)=u(u^Tu)u^T = uu^T = P$.

Finally to see that it's the orthogonal projection we need to show that $x-Px$ is orthogonal to $Px$. To do this we calculate the dot product of these two vectors using the symmetry $P^T=P$ and the projection $P^2 = P$ to show that $(Px)^T(x-Px)=x^TP^T(x-Px)= x^TP(x-Px) = x^TPx-x^TP^2x =x^TPx-x^TPx=0$. This means that $Px$ and $x-Px$ are orthogonal.

To generalize this argument the requirement that the columns be of unit length is for the same reason, we want $P^2=P$. The orthogonality condition of required to ensure the projection onto each one dimensional space is distinct from the others and can be added together without altering the individual projections. I would encourage you to explore the case when the columns are not orthogonal but still unit length to better understand why orthogonality is required.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .