Borel measurability and range correctness of the finite scan

After each scanned column, the retained vectors are orthonormal and span the scanned columns: subtracting their projections gives an orthogonal residual; a zero residual adds no span, while normalizing and multiplying a nonzero residual by a unit complex scalar adds exactly its line. This proves the invariant by finite induction. There are exactly $s$ scan steps, with no division on a zero branch, so the scan terminates with the asserted basis. If $s=0$ or $Y=0$, it returns the empty basis and zero projector.

Record all skip/retain branches and, in the complex case, the first nonzero coordinate at each retain branch. There are finitely many such records. Start with the whole input space as one Borel stratum. Inductively on a fixed partial record, residuals are continuous relative to its stratum; the zero and nonzero tests are relatively closed or open and hence ambient Borel by [F3]. Normalization is continuous where the norm is positive. If the first nonzero coordinate of the normalized residual is $w_j$, its phase multiplier is $\overline{w_j}\mathrm{/}\mathrm{\mid }{w}_j\mathrm{\mid }$, continuous where $w_j\mathrm{\ne }0$; the conditions $w_1=\cdots =w_{j-1}=0$, $w_j\mathrm{\ne }0$ give Borel substrata by the same argument. Thus every complete record has a Borel stratum and a relatively continuous output map of fixed size. For a Borel target set, [F3] expresses its preimage on each stratum as that stratum intersected with an ambient Borel set; the finite union over records is Borel. The rank strata are finite unions of these record strata, so this proves the stated variable-size Borel map, without asserting global continuity. Multiplication $Q\mapsto Q{Q}^{\ast }$ is continuous for each rank; [F4] and finite pasting give a Borel fixed-size projector. If either matrix coordinate dimension is zero, the empty-matrix input space has one point and these conclusions are immediate.

For fixed $A$, the map $\mathrm{\Omega }\mapsto A\mathrm{\Omega }$ is continuous and hence Borel by [F2] when both coordinate dimensions are positive; if either dimension is zero it is constant and Borel directly. Composing with step 2.1 using [F4] gives a Borel range-finder projector. The norm triangle inequality and [F5] give $\mathrm{\mid }\mathrm{\parallel }X{\mathrm{\parallel }}_2-\mathrm{\parallel }Z{\mathrm{\parallel }}_2\mathrm{\mid }\le \mathrm{\parallel }X-Z{\mathrm{\parallel }}_2\le \mathrm{\parallel }X-Z{\mathrm{\parallel }}_F$, so the matrix norm is continuous and the residual error is Borel too. By [F6], $v=Pv+(I-P)v$ is an orthogonal decomposition, whence $\mathrm{\parallel }(I-P)v{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }v{\mathrm{\parallel }}_2^2$ and the residual is bounded by $\mathrm{\parallel }A{\mathrm{\parallel }}_2$. For any probability law $\mu$ of the sketch, [F7] therefore gives $\int \mathrm{\parallel }(I-P)A{\mathrm{\parallel }}_{2}d\mu \le \int \mathrm{\parallel }A{\mathrm{\parallel }}_{2}d\mu =\mathrm{\parallel }A{\mathrm{\parallel }}_2<\mathrm{\infty }$, including $A=0$. Thus the Borel residual has a finite expectation under every such law.