How to solve overdetermined system $Ax=b$ using least squares, given a matrix $M$, where $M^T A$ is upper triangular and $M^TM$ is a diagonal?

Question

Given $A \in \mathbb{R}^{m\times n}$ and $b \in \mathbb{R}^m$ with $m>n$. How can I solve the full rank least squares problem if I am given a matrix $M\in \mathbb{R}^{m\times m}$ such that $M^TA = S$ and $M^TM = D$, where $S$ is upper triangular and $D$ is diagonal?

Answer 1

Given $M^TM = D$, we can do

$$M^TM = D^{1/2}D^{1/2} \rightarrow D^{-1/2} M^TMD^{-1/2} = I = Q^TQ$$ $$Q = MD^{-1/2}$$

(We view this as scaling $M$ with $D^{1/2}$ to get some orthogonal $Q$)

Now using our $Q$, we upper-triangularize A (and using $M^TA = S$)

$$Q^TA = D^{-1/2}M^TA = D^{-1/2}S = R$$

Now we can solve the least squares problem with $Q=MD^{-1/2}$ and $R = D^{-1/2}S$