Polar Decomposition - Numerical Determination of The Matrix Polar Decomposition

Numerical Determination of The Matrix Polar Decomposition

To compute an approximation of the polar decomposition A=UP, usually the unitary factor U is approximated. The iteration is based on Heron's method for the square root of 1 and computes, starting from, the sequence

, k=0,1,2,...

The combination of inversion and Hermite conjugation is chosen so that in the singular value decomposition, the unitary factors remain the same and the iteration reduces to Heron's method on the singular values.

This basic iteration may be refined to speed up the process:

  • Every step or in regular intervals, the range of the singular values of is estimated and then the matrix is rescaled to to center the singular values around 1. The scaling factor is computed using matrix norms of the matrix and its inverse. Examples of such scale estimates are:
\gamma_k=\sqrt{\frac{ \|U_k^{-1}\|_1\,\|U_k^{-1}\|_\infty }{ \|U_k\|_1\,\|U_k\|_\infty } }
using the row-sum and column-sum matrix norms or
\gamma_k=\sqrt{\frac{\|U_k^{-1}\|_F}{\|U_k\|_F}}
using the Frobenius norm. Including the scale factor, the iteration is now
, k=0,1,2,...
  • The QR decomposition can be used in a preparation step to reduce a singular matrix A to a smaller regular matrix, and inside every step to speed up the computation of the inverse.
  • Heron' method for computing roots of can be replaced by higher order methods, for instance based on Halley's method of third order, resulting in
, k=0,1,2,...
This iteration can again be combined with rescaling. This particular formula has the benefit that it also applicable to singular or rectangular matrices A.

Read more about this topic:  Polar Decomposition

Famous quotes containing the words numerical, matrix and/or polar:

    “The terrible tabulation of the French statists brings every piece of whim and humor to be reducible also to exact numerical ratios. If one man in twenty thousand, or in thirty thousand, eats shoes, or marries his grandmother, then, in every twenty thousand, or thirty thousand, is found one man who eats shoes, or marries his grandmother.”
    —Ralph Waldo Emerson (1803–1882)

    “As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.”
    —Margaret Atwood (b. 1939)

    “Professor Fate: My apologies. There’s a polar bear in our car.”
    —Arthur Ross. Professor Fate (Jack Lemmon)