I know that a complex matrix $U$ is unitary if $U^\ast U = UU^\ast = I$.
In 0910.0651, the author writes (see page 8)
... pick $U_\perp$, $V_\perp$ such that $[U, U_\perp]$ and $[V, V_\perp]$ are unitary matrices...
What does that notation mean? Additionally, in context, (see page 8), how is the existence of these matrices guaranteed?
Further up the paper, in section 2, $\mathbf{U}_{\perp}$ is introduced as the orthogonal complement of $\mathbf{U}.$ And, the notation $[\mathbf{A},\mathbf{B}]$ is used for a block matrix with hypercolumns $\mathbf{A}$ and $\mathbf{B}$ (it's used for vectors in section 2).
I haven't read through the paper, but here are some thoughts: Since orthogonal complements are not unique, the degree of freedom may be used to complete $\mathbf{U}$ and $\mathbf{V}$ to unitary matrices, i.e.
$$\mathbf{M}(\mathbf{U}_{\perp})^\top\mathbf{U}=\mathbf{0},$$
where $\mathbf{M}$ is the degree of freedom and can be chosen arbitrarily (invertible). $\mathbf{U}_{\perp}(\mathbf{M})^\top$ will be an orthogonal complement, too. Now, depending on $\mathbf{U},$ the matrix $\mathbf{M}$ may be chosen such that $[\mathbf{U}, \mathbf{U}_{\perp}(\mathbf{M})^\top]$ is unitary.