Minimizing `L2` norm with an inverse matrix. This question is from the MIT opencourseware website. Here's how the problem is stated

We now turn to the problem of interest. Givne a real $m \times n$ matrix $A$ of full column rank, and a real $m$-vector y, we wish to approximately satisfy the equation $y = Ax$. Specifically, let us choose the vector $x$ to minimize $||y-Ax||^2 = (y-Ax)'(y-Ax)$. By invoking the above results on orhogonal matrices, show that (in the notation introduced earlier) the minimizing x is $\hat x = R^{-1} y_1$ where y_1 denotes the vector formed form the first $n$ component of $Uy$.

The final piece that is necessary to know is that
$$UA =
\begin{pmatrix}
    R \\ 0
\end{pmatrix}
$$
And $R$ is nonsingular, upper-triangular matrix.


I think what the problem is saying that even though we can't find a perfect map to take $y_1$ back to $R$ we can find a close approximation which is by using the portion of our data that we can inverse. I also know that $R^{-1}$ is analogous to $(X'X)^{-1}X'$ and I know how to derive that just fine using matrix calculus.


I think I could do most of it if I had some help wit hthe setup but I'm not sure how to get form $A$ to $UA$ for minimizing the the 2 norm.
 A: Write $A = U^{T}\tilde{R}$, where $U$ is an orthogonal $m \times m$ matrix and $\tilde{R}$ is a $m \times n$ upper triangular matrix.  It is possible to do this whenever $A$ is an $m \times n$ matrix; the procedure is called the $QR$ decomposition since typically we use the symbol $Q$ instead of $U$.
Based on the wording of your question, you (or the MIT courseware you're citing) seem to assuming that the range space of $\tilde{R}$ equals $\mathbb{R}^{n} \times \{0\}$.  This isn't a restrictive assumption --- you can always change coordinates so that it's true --- but it's worth thinking carefully about.  Given this assumption, we can write
\begin{equation*}
\tilde{R} = \left( \begin{array}{c} 
R \\
0
\end{array} \right) (*).
\end{equation*}
Here $R$ is a $n \times n$ upper triangular matrix with non-zero elements on the diagonal (hence nonsingular).
Given $y \in \mathbb{R}^{n}$, we want to find the $x \in \mathbb{R}^{n}$ so that
\begin{equation*}
\|Ax - y\| = \min \left\{ \|A\tilde{x} - y\| \, \mid \, \tilde{x} \in \mathbb{R}^{n} \right\},
\end{equation*}
that is, the so-called least squares solution of the system $Ax = y$.  This is equivalent to finding the global minimum of the function $x \mapsto \|Ax-y\|^{2}$.
Using the decomposition $A = U^{T}\tilde{R}$ and the fact that $U$ is orthogonal, we have
\begin{equation*}
\|Ax - y\|^{2} = \|\tilde{R}x - U y\|^{2}.
\end{equation*}
Notice that $\tilde{R}x$ is constrained to the range space of $\tilde{R}$, no matter how we choose $x$.  Furthermore, the range space of $\tilde{R}$ equals $\mathbb{R}^{n} \times \{0\}$ by $(*)$ above.  Thus, if we let $P : \mathbb{R}^{m} \to \mathbb{R}^{n} \times \{0\}$ denote the orthogonal projection, then, by the (generalized) Pythagorean theorem,
\begin{equation*}
\|Ax - y\|^{2} = \|Rx - PUy\|^{2} + \|Uy - PUy\|^{2}.
\end{equation*}
The right-hand term doesn't depend on $x$ so we can ignore it and instead minimize $x \mapsto \|Rx - PUy\|^{2}$.  Since $PUy$ is in the range space of $R$, this is minimized precisely when it's zero, that is, when $x = R^{-1}PUy$.
Hence
\begin{equation*}
\|Uy - PUy\|^{2} = \min \left\{ \|Ax - y\|^{2} \, \mid \, x \in \mathbb{R}^{n} \right\}
\end{equation*}
and the minimum is achieved if and only if $x = R^{-1} PUy$.
