16. What finite data identify
On this page · Permalink · Source line 596
Suppose candidate states and their successors have been recorded as columns of matrices \(Z_-,Z_+\in\mathbb R^{m\times N}\). Their construction may use output histories. No hidden-state coordinates need be supplied to the fitting procedure.
Write \(W=\operatorname{im}Z_-\). Exact interpolation of these columns is a question about a linear map on \(W\), not yet about every physically realizable state.
Proposition 15: Data-span identification and its boundary
A linear map \(B\) on the ambient space with \(BZ_-=Z_+\) exists if and only if
Its restriction to \(W\) is unique. It is an endomorphism of \(W\) if and only if \(\operatorname{im}Z_+\subseteq W\). A particular ambient extension is
where \(\dagger\) denotes the Moore-Penrose inverse. Every other fitted extension agrees with \(B_0\) on \(W\). If \(W\) is a proper subspace of the true realizable state space \(V\), the data alone do not identify the operator on \(V\setminus W\).
Read proof · Recorded Lean scope · Visual guide: What four observations identify · Permalink · Source line 602
Proof
Necessity follows by applying \(B\) to every linear dependence among the input columns. Under the kernel condition, define \(B(Z_-a)=Z_+a\). Two choices of \(a\) differ by a kernel vector and give the same answer. This defines and uniquely determines the map on \(W\). It maps \(W\) into \(W\) exactly under the image condition. The pseudoinverse formula gives that map because \(a-Z_-^\dagger Z_-a\in\ker Z_-\). If \(W\subsetneq V\), choose a nonzero linear functional \(\varphi\) on \(V\) vanishing on \(W\) and a nonzero \(v\in V\). The operators \(B\) and \(B+v\varphi\) agree on every observed column and differ elsewhere. \(\square\)
The three checks are different. The kernel test checks consistency of a deterministic linear fit. The image test checks whether the observed span is closed under the fitted transitions. Equality \(W=V\) is a coverage condition. Neither of the first two checks establishes it.
For a known fixed feature space of dimension \(r\), coverage is witnessed by \(r\) independent input states. For an unknown larger feature space, the same rank only gives a lower bound on dimension. A model card must say which interpretation is being used.
If several action-specific operators act on a common declared \(r\)-dimensional state, each action's paired data must determine that operator on the required span. Pooling all actions into one high-rank matrix does not identify an action that has never been tried on some direction.
16.1 Perturbations have an explicit amplification factor
On this page · Permalink · Source line 624
A noisy rank test is not an exact certificate. Even after the state space is fixed, fitting can be ill-conditioned. The following deterministic bound isolates that issue without introducing a probability model for noise.
Work in a fixed \(r\)-dimensional coordinate system, where \(Z_-\in\mathbb R^{r\times N}\) has full row rank. Let
The matrix \(R\) records deviations from the declared linear recurrence on these samples. The matrices \(E\) and \(F\) record input and successor perturbations. All norms in the next proposition are spectral norms.
Proposition 16: Fixed-space identification bound
Put \(s=\sigma_{\min}(Z_-)>0\). If \(\|E\|<s\), then \(\widetilde Z_-\) has full row rank, and
satisfies the exact error identity and bound
Read proof · Recorded Lean scope · Visual guide: What four observations identify · Permalink · Source line 638
Proof
For every unit \(v\in\mathbb R^r\), \(\|\widetilde Z_-^\top v\|\geq\|Z_-^\top v\|-\|E^\top v\|\geq s-\|E\|\). Thus the perturbed matrix has full row rank and its pseudoinverse has norm at most \((s-\|E\|)^{-1}\). Since \(\widetilde Z_-\widetilde Z_-^\dagger=I_r\), subtract \(B\) from the fitted expression and collect terms. The bound follows by submultiplicativity and the triangle inequality. \(\square\)
This is a bound for a fixed state space and a fixed coordinate basis. If the basis or its dimension is also estimated from noisy data, subspace-estimation error must be added. No such error is hidden inside \(R\) without a derivation. Correlated and adversarial perturbations are allowed by the displayed deterministic inequality, but there is no sample-complexity claim until their magnitudes are bounded under a sampling model.
The denominator explains why numerical rank alone is insufficient. Full rank can coexist with severe noise amplification. The reference calculations include examples attaining the \(1/s\) dependence and a rank-collapse example at the excluded boundary \(\|E\|=s\).