How Can We Find the Minimum 2-Norm of Ax-y Using an Orthogonal Matrix?

[mathmari]

Hey!

Let $A = QR$, where $Q$ is an orthogonal ($m\times m$)−matrix and $R$ is an upper ($m\times n$)-triangular matrix of rang $n$ ($m>n$).

I want to show that $$\min_{x\in \mathbb{R}^n}\|Ax-y\|_2=\|(Q^Ty)_{n+1}^m\|_2, \ \forall y\in \mathbb{R}^m$$

It is $(a)_k^l=(a_k, \ldots , a_l)^T$ if $a=(a_1, \ldots , a_l)^T\in \mathbb{R}^l$.
I have done the following:

\begin{align*}\min_{x\in \mathbb{R}^n}\|Ax-y\|_2&=\min_{x\in \mathbb{R}^n}\|QRx-y\|_2=\min_{x\in \mathbb{R}^n}\|QRx-QQ^{-1}y\|_2 \\ & =\min_{x\in \mathbb{R}^n}\|Q(Rx-Q^{T}y)\|_2=\min_{x\in \mathbb{R}^n}\|Rx-Q^{T}y\|_2\end{align*}

(We have used here the properties of an orthogonal matrix.)

How could we continue? How can we find that minimum? (Wondering)

 

[I like Serena]

Hey mathmari!

We can write $Rx$ as $\binom U0x$ where $U$ is an up upper triangular nxn matrix of rank n, and 0 is a zero matrix, can't we? (Wondering)
It means that:
$$\|Rx-Q^{T}y\|^2
= \|Ux-(Q^{T}y)_1^n\|^2 + \|0-(Q^{T}y)_{n+1}^m\|^2
$$
Can we solve it now? (Wondering)

 

[mathmari]

Hey mathmari!

We can write $Rx$ as $\binom U0x$ where $U$ is an up upper triangular nxn matrix of rank n, and 0 is a zero matrix, can't we? (Wondering)
It means that:
$$\|Rx-Q^{T}y\|^2
= \|Ux-(Q^{T}y)_1^n\|^2 + \|0-(Q^{T}y)_{n+1}^m\|^2
$$
Can we solve it now? (Wondering)

Ah ok! We have that \begin{align*}\|Rx-Q^{T}y\|_2^2&=\left \|\begin{pmatrix}U \\ 0\end{pmatrix}x-\begin{pmatrix}(Q^T)_1^n \\ (Q^T)_{n+1}^m\end{pmatrix}y\right \|_2^2 =\left \|\begin{pmatrix}Ux-(Q^Ty)_1^n \\ 0-(Q^Ty)_{n+1}^m\end{pmatrix}\right \|_2^2 \\ & =\|Ux-(Q^{T}y)_1^n\|_2^2 + \|(Q^{T}y)_{n+1}^m\|_2^2\end{align*}

Therefore, we get $$\min_{x\in\mathbb{R}^n}\|Rx-Q^{T}y\|^2=\min_{x\in\mathbb{R}^n}\{\|Ux-(Q^{T}y)_1^n\|_2^2 + \|(Q^{T}y)_{n+1}^m\|_2^2\}$$

This is minimized for that $x$ for which it holds $Ux=(Q^{T}y)_1^n$ and so we get $$\min_{x\in \mathbb{R}^n}\|Ax-y\|_2^2=\|(Q^{T}y)_{n+1}^m\|_2^2\Rightarrow \min_{x\in \mathbb{R}^n}\|Ax-y\|_2=\|(Q^{T}y)_{n+1}^m\|_2$$ right? (Wondering)

 

[I like Serena]

Yep.
And that is possible because $R$ is of rank $n$, and therefore $U$ is as well, making it an invertible matrix. (Nod)

 

[mathmari]

And that is possible because $R$ is of rank $n$, and therefore $U$ is as well, making it an invertible matrix. (Nod)

Ok! Thanks a lot! (Yes)