1
$\begingroup$

Let $A_{mn}$, $m\geq n$ have full column rank and $A=U_1 \Sigma V^T$ be its reduces singular value decomposition. Show that the linear least squares problem $min_{x \in R^n} \||y-Ax||_2$ is solved at $x= V \Sigma^-1 U_1^Ty$.

Here is my attempt, just want to make sure it is correct.

Since A has full column rank there is a unique solution and that solution satisfies the normal equations, ie $A^Ty= A^TA x$. So if we manage to show that the given x makes the right hand side of the equation equal to the left, then we are done.

$A^Ty= V \Sigma^T U_1^Ty$ and $A^TAx=V \Sigma^T U_1^T U_1 \Sigma V^T V \Sigma^{-1} U_1^Ty= V \Sigma^T U_1^Ty$ since $V^TV=I$ and $U_1^TU_1=I$.

Hence both sides are equal and the equation is satisfied, so x is the solution.

I am just wondering whether we can use $U_1^T U_1 =I$ and $V^TV=I$ even though its the reduced singular value? Those still hold correct? Thanks in advance

$\endgroup$
9
  • $\begingroup$ You cannot. At least not when $m\neq n$. I assume that the matrices $\Sigma$ and $V$ in your decomposition are quadratic and $U_1$ is rectangular - just as $A$. You did not specify this. However, in this case you have $V^TV = I$ but $U_1U_1^T = I$. The matrix $U_1^TU_1$ is an orthogonal projection, but this is not important. Your technique yields the result anyway. $\endgroup$ Mar 15 '17 at 5:09
  • $\begingroup$ Ah yes thats what I meant, $ U_1^TU_1=I$ and the other way around wont work as you said. So otherwise the proof/solution is correct? Thanks $\endgroup$
    – user172377
    Mar 15 '17 at 5:28
  • $\begingroup$ Please read my comment again... $U_1^TU_1 = I$ is NOT right. $\endgroup$ Mar 15 '17 at 5:34
  • $\begingroup$ Wait...since A is m by n, and $ m \geq n$ shouldn't U be m by n and V be n x n? So $U^TU= I_n$? I tried with an example and $UU^T$ wont give I if U is m by n where m>n. $\endgroup$
    – user172377
    Mar 15 '17 at 5:50
  • 1
    $\begingroup$ You are right, sorry. I mixed the dimensions. So, you were right from the beginning on and your solution is correct. $\endgroup$ Mar 15 '17 at 5:59
2
$\begingroup$

Using the singular value decomposition to solve the full column rank linear system $$ \mathbf{A} x = b $$ where $$ \mathbf{A}\in\mathbb{C}^{m\times n}_{n}, \quad x \in\mathcal{C}^{n}, \quad b \in\mathcal{C}^{n} $$ By construction, $m\ge n$ and the matrix rank $\rho=n$.

Singular value decomposition

The singular value decomposition is guaranteed to exist: $$ \mathbf{A} = \mathbf{U} \, \Sigma \, \mathbf{V}^{*} = \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] % \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \end{array} \right]. $$ Because the matrix has full column rank the null space $\color{red}{\mathcal{N}\left( \mathbf{A}\right)}$ is trivial.

The codomain matrix $\mathbf{U}\in\mathbb{C}^{m\times m}$, and the domain matrix $\mathbf{V}\in\mathbb{V}^{n\times n}$ are unitary: $$ \mathbf{U}^{*}\mathbf{U} = \mathbf{U}\,\mathbf{U}^{*} = \mathbf{I}_{m}, \quad \mathbf{V}^{*}\mathbf{V} = \mathbf{V}\,\mathbf{V}^{*} = \mathbf{I}_{n}. $$

The column vectors of $\color{blue}{\mathbf{U}_{\mathcal{R}}}\in\mathbb{C}^{m\times\rho}$ are an orthogonal span of $\color{blue}{\mathcal{R}}(\mathbf{A})$; the column vectors of $\color{blue}{\mathbf{V}_{\mathcal{R}}}\in\mathbb{C}^{n\times\rho}$ are an orthogonal span of $\color{blue}{\mathcal{R}}(\mathbf{A}^{*})$. Similarly, the column vectors of $\color{red}{\mathbf{U}_{\mathcal{N}}}\in\mathbb{C}^{m\times m-\rho}$ are an orthogonal span of $\color{red}{\mathcal{N}(\mathbf{A^{*}})}$. The $\rho$ singular values are ordered and real: $$ \sigma_{1} \ge \sigma_{2} \ge \dots \ge \sigma_{\rho}>0. $$ These singular values form the diagonal matrix of singular values $$ \mathbf{S} = \text{diagonal} (\sigma_{1},\sigma_{1},\dots,\sigma_{\rho}) \in\mathbb{R}^{\rho\times\rho}. $$ The $\mathbf{S}$ matrix is embedded in the sabot matrix $\Sigma\in\mathbb{R}^{m\times n}$ whose shape insures conformality.

Least squares solution

Consider the case where the data vector is not the null space $b\notin\color{red}{\mathcal{N}\left( \mathbf{A}^{*} \right)}$, and the linear system $$ \mathbf{A} x - b = \mathbf{0} $$ does not have a solution of exactly 0. Generalize the question and ask for the best solution vector $x$ which minimizes the difference $r^{2}(x) = \lVert \mathbf{A} x - b \rVert_{2}^{2}$ in the $2-$norm. The least squares minimizers are defined as $$ x_{LS} = \left\{ x \in \mathbb{C}^{n} \colon \big\lVert \mathbf{A} x - b \big\rVert_{2}^{2} \text{ is minimized} \right\} $$

Exploit SVD: separate range and null spaces

Unitary transformations are invariant under the two norm. For example $$ \lVert \mathbf{V} x \rVert_{2} = \lVert x \rVert_{2}. $$ This provides a freedom to transform problems into a form easier to manipulate. In this case, $$ \lVert \mathbf{U}^{*} \mathbf{A}x - \mathbf{U}^{*} b \rVert_{2}^{2} = \lVert \Sigma \mathbf{V}^{*} x - \mathbf{U}^{*} b \rVert_{2}^{2}. $$ Switching to the block form which separates range and null spaces, $$ \begin{align} r^{2}(x) = \big\lVert \Sigma\, \mathbf{V}^{*} x - \mathbf{U}^{*} b \big\rVert_{2}^{2} &= \Bigg\lVert % \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \end{array} \right] % \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \end{array} \right] % x - \left[ \begin{array}{c} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \\[4pt] \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} \end{array} \right] b \Bigg\rVert_{2}^{2} \\ &= \big\lVert \mathbf{S} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} x - \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} b \big\rVert_{2}^{2} + \big\lVert \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} b \big\rVert_{2}^{2} \end{align} $$

Moore-Penrose pseudoinverse

By varying the solution vector $x$ we can control the range space term and force it to $0$: $$ \mathbf{S}\, \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} x - \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} b = 0 \qquad \Rightarrow \qquad x = \color{blue}{\mathbf{V}_{\mathcal{R}}} \mathbf{S}^{-1} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*}b. $$ This is the point solution, the solution of least norm: $$ x_{LS} = \mathbf{A}^{\dagger} b = \color{blue}{\mathbf{V}_{\mathcal{R}}} \mathbf{S}^{-1} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*}b $$ using the thin SVD.

The error term cannot be removed, leaving a residual error: $$ r^{2}\left(x_{LS}\right) = \big\lVert \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} b \big\rVert_{2}^{2}, $$ which quantifies how much of the data vector $b$ resides in the null space.

Orthogonality

Your question raises a point at times overlooked: the expression of orthogonality for the domain matrices. To be clear, $$ \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}} \end{array} \right] \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \end{array} \right] = \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}}^{*} \end{array} \right] \left[ \begin{array}{c} \color{blue}{\mathbf{V}_{\mathcal{R}}} \end{array} \right] = \mathbf{I}_{n}, $$ and $$ \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] \left[ \begin{array}{l} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} \end{array} \right] = \left[ \begin{array}{l} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \\ \color{red}{\mathbf{U}_{\mathcal{N}}}^{*} \end{array} \right] \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} & \color{red}{\mathbf{U}_{\mathcal{N}}} \end{array} \right] = \mathbf{I}_{m} $$ Keep in mind that when restricted to the range space component we get an identity matrix in only one direction: $$ \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \color{blue}{\mathbf{U}_{\mathcal{R}}} = \mathbf{I}_{\rho}, $$ $$ \color{blue}{\mathbf{U}_{\mathcal{R}}} \color{blue}{\mathbf{U}_{\mathcal{R}}}^{*} \ne \mathbf{I}_{m}. $$

$\endgroup$
7
  • $\begingroup$ Hi Dantopa, I think the rank should be n not m, since m$\geq n$. Also, I still don't see how $U_R^* U_R $ is not the identity, I mean I've tried all examples of matrices which are 3 by 2 or 4 by 3 which have orthonormal columns and they all give I ? $\endgroup$
    – user172377
    Mar 15 '17 at 20:30
  • $\begingroup$ I mean writing $U_R$ in block form with columns $u_1,u_2,...,u_n$ then $U_R^{*} U_R= I_n$ since you get $u_i^{*} u_i = 1$ and $u_i^{*} u_j = 0$ for all i not equal to j and you have n $ u_i^{*}$ terms each multiplying n$ u_i$ terms $\endgroup$
    – user172377
    Mar 15 '17 at 20:53
  • $\begingroup$ math.stackexchange.com/questions/182355/… Robert Israel's answer supports my claim? And en.wikipedia.org/wiki/Semi-orthogonal_matrix $\endgroup$
    – user172377
    Mar 15 '17 at 20:57
  • $\begingroup$ @Socchi Thank you for your careful reading and finding the typos. My notes are written in with $X$ and $Y$ instead of $U$ and $V$ which inspires confusion. $\endgroup$
    – dantopa
    Mar 15 '17 at 22:16
  • 1
    $\begingroup$ Thank you your answer was quite informative. I will upvote. I will still leave the question open though as it might inspire more good explanations. $\endgroup$
    – user172377
    Mar 15 '17 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy