2
$\begingroup$

The algebraic polar decomposition is defined as: $$A=QS$$ Where $Q$ is a matrix with orthonormal columns and $S$ is a symmetric matrix. The question is, when is such a factorization possible? I started with the SVD of $A$:

$$A = U \Sigma V^T$$ Here, $U$ and $V$ are orthonormal matrices and $\Sigma$ is diagonal matrix with the singular values of $A$.

This leads to: $$S = V (\Sigma \Sigma)^.5 V^T$$ and $$QV(\Sigma \Sigma)^.5 = U\Sigma$$

If $A$ is full column rank, then $(\Sigma \Sigma)^.5$ will be invertible and we can easily solve for $Q$. The interesting case is when $A$ is not full column rank. Here are some cases -

1) When $A$ has more columns than rows (fat matrix), this is clearly impossible since we are hoping to get a $Q$ with orthonormal columns that span a space higher than the size of the column space itself.

2) When $A$ is square but not singular, here is an example where it is possible:

In [548]: a
Out[548]:
array([[ 1. ,  0.5,  0.4],
       [ 0.5,  1. ,  0. ],
       [ 0. ,  0. ,  0. ]])

In [549]: s
Out[549]:
array([[ 0.92417515,  0.52002785,  0.35421932],
       [ 0.52002785,  0.9896415 ,  0.01344378],
       [ 0.35421932,  0.01344378,  0.18533196]])

In [550]: q
Out[550]:
array([[ 0.88554831,  0.03360946,  0.46332991],
       [ 0.07725369,  0.97283677, -0.21822117],
       [-0.45807867,  0.22903933,  0.8588975 ]])

So, my question is - when is a decomposition like this possible and when not?

$\endgroup$
3
  • 1
    $\begingroup$ It is always possible when $A$ is square. If $A$ is not square, you can still write $A=QS$ with $S$ symmetric and now in your notation $Q=UV^T$ should have the dimensions of $A$. $\endgroup$
    – Max
    Aug 27 '17 at 18:50
  • $\begingroup$ @Max is it possible to prove that if $A$ is square but not full rank, this will always be possible? $\endgroup$ Aug 27 '17 at 20:35
  • $\begingroup$ @Max - also, when $A$ is not square, it is not possible to multiply $U$ and $V$ since they have different dimensions, no? $\endgroup$ Aug 27 '17 at 20:36
1
$\begingroup$

If $A$ is tall, the case is actually not different from the usual one. Perform a full SVD $A=U\pmatrix{\Sigma\\ 0}V^T$, where $U,V$ are (square) real orthogonal matrices, $\pmatrix{\Sigma\\ 0}$ has the same size as $A$ and $\Sigma$ has the same size as $V$. Then you may put $Q=U\pmatrix{I\\ 0}V^T$ and $S=V\Sigma V^T$.

If an "economic" SVD is used instead, so that $A=U\Sigma V^T$ for some $U, V$ with orthonormal columns and some positive diagonal matrix $\Sigma$, enlarge $U$ and $V$ by augmenting more orthonormal columns to them (e.g. using Gram-Schmidt orthogonalisation). Also, extend the diagonal of $\Sigma$ by appending zeros to it. Stop until $U,V,\Sigma$ have the same number of columns as $A$ (so that $V$ and $\Sigma$ become square matrices). Now we still have $A=U\Sigma V^T$ and you may put $Q=UV^T$ and $S=V\Sigma V^T$.

$\endgroup$
1
  • $\begingroup$ Sorry, there were several stupid comments by me, since I've initially misunderstood your notation. $\endgroup$ Mar 2 '18 at 12:20
1
$\begingroup$

Faced with the same problem recently, I came up with the following solution.

Observe first that, whenever the matrix $A$ is square, the polar matrix $U$ is orthogonal. Thus, its rows are orthogonal as well. So, if $A$ is a full-rank fat matrix, then $U$ remains full-rant with orthonormal rows.

Now, there are loads of examples on stackexchange how extract a polar decomposition from an SVD of a square matrix, and we may make a slight adaptation for fat rectangular ones.

Consider your SVD decomposition $A=U\Sigma V^T$. If $A$ is $m\times n$ fat matrix ($m \le n$), then $U$ is $m\times m$, $V$ is $n\times n$ and $\Sigma$ is $m\times n$ with singular values on the diagonal. Now you may present $\Sigma = JP$, where $J$ is an $m\times n$ matrix with $1$s on the diagonal, and $P = \begin{pmatrix}\Sigma \\ 0\end{pmatrix}$ is $n\times n$. Observe that $P$ is diagonal!

So, now you have $A = UJPV^T = UJV^TVPV^T$, since $V$ is orthogonal. But now $VPV^T$ is symmetric since $P$ is diagonal, and $UJV^T$ has orthonormal rows. Thus, in your notation, you get:

$Q = UJV^T$ and $S=VPV^T$.

Observe that for a fat matrix $A$ the matrix $JV^T$ is just a submatrix consisting of the first $m$ rows of $V^T$. So, if you already do have your SVD for $A$ obtained by some method, this information suffices to compute the polar decomposition.

As a side note, though many mathematical libraries provide methods to compute SVD but not polar decomposition, a method to compute SVD via polar decomposition has been proposed as early as in 1994, showing higher performance than contemporaty LAPACK SVD, and the newer methods are now being devised, making use of parallel computing, see this post by Nigel Higham for details.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.