  We present fast numerical methods for computing the Hessenberg reduction of a
unitary plus low-rank matrix $A=G+U V^H$, where $G\in \mathbb C^{n\times n}$ is
a unitary matrix represented in some compressed format using $O(nk)$ parameters
and $U$ and $V$ are $n\times k$ matrices with $k< n$. At the core of these
methods is a certain structured decomposition, referred to as a LFR
decomposition, of $A$ as product of three possibly perturbed unitary $k$
Hessenberg matrices of size $n$. It is shown that in most interesting cases an
initial LFR decomposition of $A$ can be computed very cheaply. Then we prove
structural properties of LFR decompositions by giving conditions under which
the LFR decomposition of $A$ implies its Hessenberg shape. Finally, we describe
a bulge chasing scheme for converting the initial LFR decomposition of $A$ into
the LFR decomposition of a Hessenberg matrix by means of unitary
transformations. The reduction can be performed at the overall computational
cost of $O(n^2 k)$ arithmetic operations using $O(nk)$ storage. The computed
LFR decomposition of the Hessenberg reduction of $A$ can be processed by the
fast QR algorithm presented in [8] in order to compute the eigenvalues of $A$
within the same costs.
