  We construct fast, structure-preserving iterations for computing the sign
decomposition of a unitary matrix $A$ with no eigenvalues equal to $\pm i$.
This decomposition factorizes $A$ as the product of an involutory matrix $S =
\operatorname{sign}(A) = A(A^2)^{-1/2}$ times a matrix $N = (A^2)^{1/2}$ with
spectrum contained in the open right half of the complex plane. Our iterations
rely on a recently discovered formula for the best (in the minimax sense)
unimodular rational approximant of the scalar function $\operatorname{sign}(z)
= z/\sqrt{z^2}$ on subsets of the unit circle. When $A$ has eigenvalues near
$\pm i$, the iterations converge significantly faster than Pad\'e iterations.
Numerical evidence indicates that the iterations are backward stable, with
backward errors often smaller than those obtained with direct methods. This
contrasts with other iterations like the scaled Newton iteration, which suffers
from numerical instabilities if $A$ has eigenvalues near $\pm i$. As an
application, we use our iterations to construct a stable spectral
divide-and-conquer algorithm for the unitary eigendecomposition.
