33. Learning the coordinate space under bounded noise
On this page · Permalink · Source line 1358
Part II bounded operator error after a state space and basis were fixed. Here we also bound one step of data-dependent space selection. This remains a finite-matrix statement. It does not certify that a chosen finite history/test table captures the full process.
Let \(X\in\mathbb R^{m\times n}\) have rank \(r\geq1\), let \(s=\sigma_r(X)>0\), and observe \(Y=X+E\) with \(\|E\|_2\leq\varepsilon<s/2\). Let \(P\) project onto \(\operatorname{im}X\), and let \(\widehat P\) project onto the leading \(r\) left singular vectors of \(Y\).
Proposition 32: Finite-table rank separation and subspace stability
One has
The \((r+1)\)st singular value is interpreted as zero when \(r\) is the maximum possible rank. If \(U\) and \(\widehat U\) are orthonormal bases of the two ranges, then
Thus \(x\mapsto\widehat U^\top x\) is injective on the true column space. Its inverse on that space is
with norm at most \([1-(2\varepsilon/s)^2]^{-1/2}\).
Read proof · Recorded Lean scope · Permalink · Source line 1364
Proof
The min-max characterization of singular values and the triangle inequality imply that adding \(E\) changes each singular value by at most \(\varepsilon\). The leading-\(r\) singular subspace gives \(\|(I-\widehat P)Y\|_2=\sigma_{r+1}(Y)\leq\varepsilon\). Hence
For equal-rank orthogonal projections, the latter norm equals \(\|P-\widehat P\|_2\). To see the equality, diagonalize \(U^\top\widehat U\) by singular value decomposition. Each nontrivial paired principal plane contributes a sine to both norms, while common directions contribute zero. On the same planes the singular values of \(\widehat U^\top U\) are the corresponding cosines. This proves the last bound and the inverse formula. \(\square\)
A threshold \(\tau\) with \(\varepsilon<\tau<s-\varepsilon\) recovers the rank of this finite matrix. The unknown true gap must be justified or replaced by a valid confidence interval. Rank thresholds do not exclude modes absent from the selected tests or unexcited by the selected histories.
The inverse formula contains the unknown true basis \(U\). It proves identifiability and conditioning relative to that space, not that a learner already knows a perfect decoder. When using the estimated subspace as coordinates for a realization, all boundary vectors, symbol operators and probability constraints must be transformed together. Signed singular-vector coordinates are not new independent observations.