1
$\begingroup$

Let $x=A^T(AA^T)^{-1}b$ given that $A_{m\times n}$ is a full row rank matrix and $b$ is a vector. By $SVD$ decomposition $A=U\Sigma V^T$.

How can I express $x$ with $U,V,b$ and the addition of the partial matrix $\Sigma_{m\times m}$ which contains the non zeroes segments of $\Sigma$.

Also Can It be written with a slimmer version using $u_i\in \mathbb R^{m\times1},v_i\in \mathbb R^{n\times1}$, vectors from $U,V$ and $\sigma_i$ the diagonal values of $\Sigma$?

Is the following valid\good enough?

$$x=A^T(AA^T)^{-1}b=(UΣV^T)^T(UΣV(UΣV^T)^T)^{-1}b=U^TΣ^TV(UΣVU^TΣ^TV)^{-1}b$$ $$=U^T ΣV(UΣVU^T ΣV)^{-1}b$$

$\endgroup$
1
  • $\begingroup$ Your calculations are incorrect. Note that $(AB)^t = B^t A^t$. $\endgroup$
    – Dominik
    Nov 15, 2016 at 12:05

2 Answers 2

1
$\begingroup$

I assume that $m \le n$ holds? Then note: $$AA^t = U \Sigma V^t V \Sigma^t U^t = U \Sigma \Sigma^t U^t$$

Since $A$ has full rank, $\Sigma \Sigma^t$ also has full rank. From $U \Sigma \Sigma^t U^t U (\Sigma\Sigma^t)^{-1}U = I$, we can infer $(AA^t)^{-1}$ = $U(\Sigma\Sigma^t)^{-1}U^t$. This yields: $$A^t(AA^t)^{-1} = V \Sigma^t U^t U (\Sigma\Sigma^t)^{-1} U^t = V \Sigma^t (\Sigma \Sigma^t)^{-1} U^t.$$

We have $\Sigma = (\Sigma_{m \times m})$ and therefore $\Sigma \Sigma^t = \Sigma_{m \times m} \Sigma_{m \times m}^t = \Sigma_{m \times m}^2$. This implies $$\Sigma^t(\Sigma \Sigma^t)^{-1} = \begin{pmatrix}\Sigma_{m \times m}^{-1} \\ 0\end{pmatrix}.$$

Edit: If $u_i$ resp. $v_i$ are the rows of $U$ resp. $V$, you can simplify this further.

$$\begin{pmatrix}v_1 \\ v_2 \\ \vdots \\v_n\end{pmatrix} \begin{pmatrix}\Sigma_{m \times m}^{-1} \\ 0 \end{pmatrix} \begin{pmatrix}u_1^t & u_2^t & \cdots & u_m^t\end{pmatrix} =\begin{pmatrix}v_1 \\ v_2 \\ \vdots \\v_n\end{pmatrix} \begin{pmatrix}\Sigma_{m \times m}^{-1} u_1^t & \Sigma_{m \times m}^{-1} u_2^t & \cdots & \Sigma_{m \times m}^{-1}u_m^t \\ 0 & 0 & \cdots & 0\end{pmatrix}$$

Now if $\sigma_i$ are the diagonal elements of $\Sigma_{m \times m}$, then the $(i, j)$-th coordinate of this matrix is given by $\sum \limits_{k = 1}^m v_{i, k} \sigma_{k, k}^{-1} u_{j, k}$.

$\endgroup$
4
  • $\begingroup$ $m\leq n$ not necessarily holds.. $\endgroup$
    – havakok
    Nov 15, 2016 at 12:09
  • 1
    $\begingroup$ But $A A^t$ is an $m \times m$ matrix of rank $\min(m, n)$, so it is only invertible if $m \le n$. $\endgroup$
    – Dominik
    Nov 15, 2016 at 12:15
  • $\begingroup$ Can I write this with $u_i\in \mathbb R^{m\times 1},v_i\in \mathbb R^{n\times 1}$? How do I write $V$ as its partial vectors $v_i\in \mathbb R^{n\times 1}$ for example? $\endgroup$
    – havakok
    Nov 15, 2016 at 12:25
  • 1
    $\begingroup$ I have added some further formulae. $\endgroup$
    – Dominik
    Nov 15, 2016 at 12:45
0
$\begingroup$

The target matrix has full row rank $$ \mathbf{A} \in \mathbb{C}^{m\times n}_{m}, $$ and $m < n$. The null space $\mathcal{N}\left( \mathbf{A}^{*} \right)$ is trivial and the singular value decomposition takes the form $$ \begin{align} \mathbf{A} &= \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \\ % &= % U \left[ \begin{array}{c} \color{blue}{\mathbf{U}_{\mathcal{R}}} \end{array} \right] % Sigma \left[ \begin{array}{cccccc} \sigma_{1} & 0 & \dots & & & \dots & 0 \\ 0 & \sigma_{2} &&&&& \\ \vdots && \ddots &&&& \vdots\\ 0 & & & \sigma_{m} & 0 & \dots & 0 \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}^{*}_{\mathcal{R}}} \\ \color{red}{\mathbf{V}^{*}_{\mathcal{N}}} \end{array} \right] \\[3pt] % & = % U \left[ \begin{array}{cc} \color{blue}{\mathbf{U}_{\mathcal{R}}} \end{array} \right] % Sigma \left[ \begin{array}{cc} \mathbf{S}_{m\times m} & \mathbf{0} \\ \end{array} \right] % V \left[ \begin{array}{c} \color{blue}{\mathbf{V}^{*}_{\mathcal{R}}} \\ \color{red}{\mathbf{V}^{*}_{\mathcal{N}}} \end{array} \right] \\[3pt] % \end{align} $$ The product matrix is $$ \mathbf{A} \, \mathbf{A}^{*} = \left( \mathbf{U} \, \Sigma \, \mathbf{V}^{*} \right) \left( \mathbf{V} \, \Sigma \, \mathbf{U}^{*} \right) = \color{blue}{\mathbf{U}_{\mathcal{R}}} \, \mathbf{S}^{2} \, \color{blue}{\mathbf{U}^{*}_{\mathcal{R}}} $$ with the inverse being $$ \left( \mathbf{A} \, \mathbf{A}^{*} \right)^{-1} = \color{blue}{\mathbf{U}_{\mathcal{R}}} \, \mathbf{S}^{-2} \, \color{blue}{\mathbf{U}^{*}_{\mathcal{R}}} $$ Finally $$ \begin{align} \mathbf{A}^{*} \left( \mathbf{A} \, \mathbf{A}^{*} \right)^{-1} &= \left( % V \left[ \begin{array}{cc} \color{blue}{\mathbf{V}_{\mathcal{R}}} & \color{red}{\mathbf{V}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{c} \mathbf{S} \\ \mathbf{0} \\ \end{array} \right] % U \color{blue}{\mathbf{U}^{*}_{\mathcal{R}}} \right) \color{blue}{\mathbf{U}_{\mathcal{R}}} \, \mathbf{S}^{-2} \, \color{blue}{\mathbf{U}^{*}_{\mathcal{R}}} \\ &= % V \left[ \begin{array}{cc} \color{blue}{\mathbf{V}_{\mathcal{R}}} & \color{red}{\mathbf{V}_{\mathcal{N}}} \end{array} \right] % Sigma \left[ \begin{array}{c} \mathbf{S}^{-1} \\ \mathbf{0} \\[2pt] \end{array} \right] % U \color{blue}{\mathbf{U}_{\mathcal{R}}} \\ &= \mathbf{A}^{\dagger} \end{align} $$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .