Explicit construction for unitary extensions of CPTP maps?

Given a completely positive and trace preserving map $\Phi : \textrm{L}(\mathcal{H})\to\textrm{L}(\mathcal{G})$, it is clear by the Kraus representation theorem that there exist $A_k \in \text{L}(\mathcal{H}, \mathcal{G})$ such that $\Phi(\rho) = \sum_k A_k \rho A_k^\dagger$ for all density operators $\rho$ on $\mathcal{H}$. (I'll consider the special case $\mathcal{H} = \mathcal{G}$ for simplicity.)

If we use then the system+environment model to express this action as $\Phi(\rho)=\text{Tr}_{\mathcal{H}_E} (Y\rho Y^\dagger)$ for an isometry $Y$ from $\mathcal{H}$ to $\mathcal{H}\otimes\mathcal{H}_E$, where $\mathcal{H}_E$ is an ancilla modelling the environment, what is an explicit construction for a unitary $U$ that has the same action on inputs of the form $\rho\otimes\left|0\right>\left<0\right|_E$? That is, how can I construct an explicit dilation of the map to a unitary acting on a larger space? I understand that this is possible by Steinspring's dilation theorem, but actually constructing an explicit form for the dialated unitary I have had much less success with.

-
There used to be Joe Fitzsimmons' answer here, what happened? –  Marcin Kotowski Oct 30 '11 at 15:59
@Marcin: I deleted it because there was an error in the proof. –  Joe Fitzsimons Nov 8 '11 at 4:28

The isometry $Y:\mathcal H\rightarrow \mathcal H_E \otimes \mathcal H$ is $$Y=\left(\begin{array}{c} A_1 \\ \vdots \\ A_K \end{array}\right) = \sum_k |k\rangle \otimes A_k\ .$$ Clearly, $$\mathrm{tr}_E(Y\rho Y^\dagger) = \sum_{kl} \mathrm{tr}(|k\rangle\langle l|) A_k\rho A_l^\dagger = \sum_k A_k \rho A_k^\dagger \ ,$$ as desired. Moreover, $Y$ is an isometry, $Y^\dagger Y=I$, i.e., its columns are orthonormal, which follows from the condition $\sum_k A_k^\dagger A_k=I$ (i.e., the map is trace preserving).
Now if you want to obtain a unitary which acts on $|0\rangle\langle 0|\otimes \rho$ the same way $Y$ acts on $\rho$, you have to extend the matrix $Y$ to a unitary by adding orthogonal column vectors. For instance, you can pick linearly independent vectors from your favorite basis and orthonormalize. (Clearly, $U$ is highly non-unique, as its action on environment states other than $|0\rangle$ is not well defined.)