1

I have a full-column-rank matrix $A \in \mathbb{R}^{N \times n} $ ($N >> n$):

$Q^{T} A = \begin{bmatrix} R & w \\ 0 & v \\ \end{bmatrix} , Q^{T} = \begin{bmatrix} c \\ d \\ \end{bmatrix} $,

with $R \in \mathbb{R}^{(n-1)\times(n-1)}, w \in \mathbb{R}^{n-1}, v \in \mathbb{R}^{N-n+1}, c \in \mathbb{R}^{n-1}$ and $d \in \mathbb{R}^{N-n+1}$

Now I have to show that

$ \min_x ||Ax - b||^²_2 = ||d||^2_2 - (\frac{v^T d}{||v||_2})^2$

Anyone a idea how to approach this? I don't know how to start with this problem.

What I know is that with a standard least squares problem $\min_x ||y - Fx||_2^2$ with a QR factorization of $F$ and the application of $Q^T$ to $y$

you have the following solution $\hat{x} = R^{-1} d_1$ and $||y-Fx||_2^2 = ||d_2||_2^2$

with $ \begin{bmatrix} Q_1^T \\ Q_2^T \\ \end{bmatrix} y = \begin{bmatrix} d1 \\ d2 \\ \end{bmatrix}$

How to rewrite things to have a format more like this?

Derk
  • 277

1 Answers1

2

$x \in R^n$ must be true, otherwise the matrices cannot be subtracted form each other.

\begin{equation} \begin{split} \displaystyle \min_{x} ||Ax - b||_2^2 = \displaystyle \min_{x} ||Q^T(Ax - b)||_2^2 \\ = \displaystyle \min_{x} ||Q^TAx - Q^Tb||_2^2 \\ = \displaystyle \min_{x} || \begin{pmatrix} Rx & wx \\ 0 & vx \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 \\ \end{split} \end{equation}

This can be written as:

\begin{multline} \displaystyle \min_{x} || \begin{pmatrix} Rx & wx \\ 0 & vx \end{pmatrix} - \begin{pmatrix} 0 & 0 \\ 0 & vx \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 - \displaystyle \min_{x} || \begin{pmatrix} 0 & 0 \\ 0 & vx \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 \\ \end{multline}

Solving the first part of equation 2 following LSQR-Theorom :

\begin{equation} \begin{split} \displaystyle \min_{x} || \begin{pmatrix} Rx & wx \\ 0 & vx \end{pmatrix} - \begin{pmatrix} 0 & 0 \\ 0 & vx \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 \\ = \displaystyle \min_{x} || \begin{pmatrix} Rx & wx \\ 0 & 0 \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 \\ = ||d||_2^2 \end{split} \end{equation}

Than solving the second part of equation 2 following LS-Theorom :

\begin{equation} \begin{split} \displaystyle \min_{x} || \begin{pmatrix} 0 & 0 \\ 0 & vx \end{pmatrix} - \begin{pmatrix} c \\ d \end{pmatrix} ||_2^2 \\ = \displaystyle \min_{x} || vx - d||_2^2 \\ = ((v^Tv)^{-1}v^td)^2 = \left(\frac{v^Td}{||v||_2}\right)^2 \end{split} \end{equation}

Substituting equation 3 and 4 into equation 2 results in the asked answer.

\begin{equation} \displaystyle \min_{x} ||Ax - b||_2^2 = ||d||_2^2 - \left(\frac{v^Td}{||v||_2}\right)^2 \end{equation}

Any chance you are a stundent at TU delft following filtering and identification? Since I had the same exact exercise as homework :). This is what i think works, not the best explanation. It's still fuzzy in my own head. Plus I have doubts about it being $\left(\frac{v^Td}{||v||_2}\right)^2$ because I would expect it being $\frac{v^Td}{||v||_2^2}$. Maybe you have any ideas on that! goodluck and let me know if you think it can be written out better.

Peter Stijnman
  • 21
  • Yes TU Delft student :) Thanks for your answer, helped me on the right track. Close to the right solution I think. – Derk Nov 21 '15 at 12:37
  • Yes TU Delft student :) Thanks for your answer, helped me on the right track. Close to the right solution I think. But with x you means [x1 x2]^T and then Rx1, wx2, vx2 (because of the lengths)? What I don't understand right now is the line after this can be written as: why can you divide that in that two parts? That's where I got stuck. And as solution to min || vx2 - d || you write the least squares estimate of x2 instead of the loss? Tried to working it out by substituting x2 with the least squares loss didn't succeed yet. – Derk Nov 21 '15 at 12:43
  • Yes that is what i mean with x. That line can be written like that because in one instance i subtract the matrix and than i add it again, this is done because the separate least squares solutions are known. Where without doing it the solution is not known.And yeah for the last part im still not sure, For the same reasons as you, however that is the only thing that results in that second term – Peter Stijnman Nov 21 '15 at 15:37
  • An other idea I had was maybe to use something like pythagoras theorom to show that the length of d^2 - the length of the projection of d onto v in the plane, but i dont know how to connect that to the asked least squares yet. – Peter Stijnman Nov 21 '15 at 15:44
  • Okay, thanks again. The difficulty I see with separating the solutions is that now the $wx_2$ part is ignored in finding the solution for x2? And the first part has an exact solution because R should be upper-triangular, but know with the wx part in that matrix it is not sure if there is still an exact solution I think – Derk Nov 21 '15 at 17:10