printed: AMS subject classifications. 68T05, 68Q32, 41A46, 65D15, 47A16
Introduction
Modern learning systems achieve remarkable predictive performance, but their internal mechanisms are often difficult to characterize mathematically. In this work we study a different organizing principle for learning: rather than beginning with unrestricted parametrization, we begin with a structured orbit geometry induced by the data and ask what targets can be constructively realized on it. This leads to an orbit-based framework organized around three linked bottlenecks: a scaffold bottleneck , measuring how well a data-induced orbit scaffold captures the relevant target geometry; a realizability bottleneck , measuring how accurately the projected target can be synthesized on that scaffold; and a predictive coefficient bottleneck , measuring how well the resulting constructive coefficient rule can be extended to unseen inputs.
The main contribution is a constructive controlled-deviation synthesis mechanism (CCDS) on data-induced orbit dictionaries. Wrapped weighted shifts and block interpolation provide the dictionary; CCDS then characterizes the feasible stepwise deviations and constructs the corresponding sparse realizations. Minimal-deviation choices recover MP and OMP, while nonzero interior updates departing from an OMP projection state cannot be produced by OMP under any atom ordering. For prescribed interior paths with positive feasibility margins, the realization is locally Lipschitz stable under admissible perturbations of the block interpolants. An observable local-chart score further controls the distortion of bounded-coefficient sparse approximation, providing a geometric justification for dictionary pre-selection. The predictive model, which we call a Weighted Backward Shift Neural Network (WBSNN), is built directly on this constructive structure. Phase 1 identifies the orbit scaffold, Phase 2 uses CCDS to associate each training target with a sparse coefficient certificate over the fixed orbit dictionary, and Phase 3 learns an extension of this coefficient map to unseen inputs. Thus prediction is not introduced as an independent parametrization problem: it extends the constructive rule identified by the first two phases. Nonlinearity enters through the data-dependent selection and combination of orbit-generated atoms and CCDS paths, while prediction further extends this structure through a learned coefficient map to unseen inputs.
This viewpoint provides both structural interpretability and practical flexibility. Every realization and prediction is expressed through coefficients over a fixed orbit-derived representation, while the projection and parametrization errors expose where the construction succeeds or fails. The theory also shows that exact block interpolation is not required in practice: regularized block interpolants preserve the scaffold geometry locally and perturb the CCDS realization continuously, justifying a better-conditioned relaxed implementation. Empirically, across synthetic and real datasets, the framework produces highly sparse realizations and competitive predictive performance; in several experiments the relevant orbit scaffold is recovered using only a small fraction, as little as 1%, of the training data.
The construction is rooted in linear dynamics. Weighted backward shifts provide a simple operator class whose iterates generate rich orbit structure, and we introduce a wrapped finite-dimensional version that preserves this mechanism while avoiding coordinate loss. Its iterates generate the dictionaries on which scaffold construction, constructive realization, and prediction are built. The resulting perspective shifts attention from parametrization alone to the interaction between dataset geometry, orbit structure, and constructive realizability.
The paper is organized as follows. Our main results are in § 3 , and experimental results are in § 4 . Appendix § 5 contains the complete proofs, while Appendix § 6 records the experimental configurations.
Relation to prior work
Our deviation-control viewpoint through CCDS is motivated by Bernstein lethargy theory, where approximation errors along nested families need not obey a universal decay rate [5 , 17 ] . Rather than postulating such a rate, we treat the residual trajectory itself as a constructive object. This differs from discrepancy principles, where a prescribed residual typically serves as a stopping or regularization criterion [15 , 3 ] , and from classical greedy pursuits such as MP and OMP, whose residuals are determined by greedy contraction or orthogonal projection [13 , 16 , 19 , 8 , 18 ] . In our framework, feasible residual profiles are prescribed and realized explicitly; standard greedy updates arise as boundary regimes of this broader deviation-control mechanism.
Classical dictionary-learning methods, including K-SVD [1 ] and online dictionary learning [12 ] , adapt dictionary atoms to data through sparsity-constrained or sparsity-penalized reconstruction. Our construction instead generates atoms through the structured family J k W m x k , j J_k W^m x_{k,j} J k W m x k , j , coupling dictionary geometry to anchor interpolation. On the resulting dictionary, CCDS constructs sparse realizations with prescribed feasible deviations and fixed-path stability under admissible perturbations, recovering MP/OMP at the minimal-deviation boundary.
Operator-theoretic ideas in machine learning also appear in Koopman-based representations and forecasting [14 , 11 , 2 , 6 ] and in neural-operator approaches such as DeepONet and neural integral equations [10 , 20 ] . WBSNN is different in that it does not learn an operator representation directly: iterates of a single orbit-generating operator first induce a data-dependent scaffold, targets are then constructively realized on that scaffold, and prediction is obtained by extending the resulting coefficient law. Its mathematical origin is therefore closer to linear dynamics and orbit theory, with weighted backward shifts providing the guiding prototype [4 ] .
Our Orbit-Based Constructive Theory
This section develops the constructive backbone of the paper. The central object is a data-induced orbit scaffold U ⊆ R C U \subseteq\mathbb{R}^{C} U ⊆ R C constructed from a small anchor subset of a given dataset. The target is first projected onto this scaffold and then constructively realized within it. This separates realization into two distinct problems: how well the scaffold captures the target on the dataset, and how accurately the projected target can be synthesized once the scaffold is fixed. These will become, respectively, the projection and realization bottlenecks developed below.
Standing data notation. Throughout, let Ξ t r a i n = { ( x i , y i ) } i = 1 n ⊆ R d × R C \Xi_{\mathrm{train}} = \{(x_i,y_i)\}_{i=1}^{n} \subseteq\mathbb{R}^{d} \times\mathbb{R}^{C} Ξ train = {( x i , y i ) } i = 1 n ⊆ R d × R C be a finite input–target dataset generated by an empirical target map f Ξ : R d → R C f_{\Xi}:\mathbb{R}^{d} \to\mathbb{R}^{C} f Ξ : R d → R C , so that f Ξ ( x i ) : = y i f_{\Xi}(x_i) := y_i f Ξ ( x i ) := y i . We define the empirical mean seminorm for any map h h h evaluated on the dataset by ∥ h ∥ Ξ : = 1 n ∑ i = 1 n ∥ h ( x i ) ∥ 2 \lVert h\rVert_{\Xi} := \frac{1}{n}\sum_{i=1}^{n}\lVert h(x_i)\rVert_2 ∥ h ∥ Ξ := n 1 ∑ i = 1 n ∥ h ( x i ) ∥ 2 .
Let Ξ s u b ⊆ Ξ t r a i n \Xi_{\mathrm{sub}} \subseteq\Xi_{\mathrm{train}} Ξ sub ⊆ Ξ train be the anchor subset used for scaffold construction. We write
Ξ s u b = D 1 ⊔ ⋯ ⊔ D K , D k = { ( x k , j , y k , j ) } j = 1 s k . (1) \Xi_{\mathrm{sub}} = D_1 \sqcup\cdots\sqcup D_K,\qquad D_k = \{(x_{k,j},y_{k,j})\}_{j=1}^{s_k}. \tag*{(1)} Ξ sub = D 1 ⊔ ⋯ ⊔ D K , D k = {( x k , j , y k , j ) } j = 1 s k . (1)
The framework’s backbone
Our starting point is the observed input–target relation. Even within an anchor block, there need not exist a single linear operator sending every original input to its prescribed target. We therefore seek a structured representation of these constraints by first transforming the inputs along operator orbits and then applying a blockwise linear readout.
Weighted backward shifts are classical operators in linear dynamics and can exhibit remarkably rich orbit behavior in infinite-dimensional spaces. To adapt their orbit mechanism to finite-dimensional learning, we use a wrapped weighted backward shift, which replaces coordinate loss by cyclic propagation modulo d d d . This provides the structured orbit backbone used throughout the framework.
Definition 3.1 (The wrapped weighted backward shift). A wrapped weighted backward shift W : R d → R d W:\mathbb{R}^{d} \to\mathbb{R}^{d} W : R d → R d is defined as W e j = w j e j − 1 ( m o d d ) We_j = w_je_{j-1}\pmod d W e j = w j e j − 1 ( mod d ) , where e 0 , … , e d − 1 e_0,\ldots,e_{d-1} e 0 , … , e d − 1 is the canonical basis and w j ≠ 0 w_j \ne0 w j = 0 .
Even within a block, the original assignments x k , j ↦ y k , j x_{k,j} \mapsto y_{k,j} x k , j ↦ y k , j need not admit a common linear interpolant. We therefore use anchor-dependent iterates of W W W to seek orbit representatives on which a shared linear readout can realize the prescribed targets. Specifically, in the next subsection, for an anchor block D k D_k D k , we seek depths L k , j L_{k,j} L k , j and a linear operator J k J_k J k such that
x k , j ⟼ W L k , j x k , j ⟼ J k W L k , j x k , j = y k , j . x_{k,j} \longmapsto W^{L_{k,j}}x_{k,j} \longmapsto J_kW^{L_{k,j}}x_{k,j} = y_{k,j}. x k , j ⟼ W L k , j x k , j ⟼ J k W L k , j x k , j = y k , j .
The two operators have then distinct roles: W W W generates the orbit geometry, while J k J_k J k converts the selected orbit representatives into target outputs. The depth may depend on the anchor, although the readout is shared within each block. These identities realize the anchor constraints in Ξ s u b \Xi_{\mathrm{sub}} Ξ sub .
Lemma 3.2. For every m ≥ 1 m \ge1 m ≥ 1 and z ∈ R d z \in\mathbb{R}^{d} z ∈ R d ,
( W m z ) i − 1 = ( ∏ r = 0 m − 1 w ( i + r ) m o d d ) z ( i + m − 1 ) m o d d , i = 1 , … , d . \left(W^{m}z\right)_{i-1}=\left(\prod_{r=0}^{m-1}w_{(i+r)\bmod d}\right)z_{(i+m-1)\bmod d},\qquad i=1,\ldots,d. ( W m z ) i − 1 = ( r = 0 ∏ m − 1 w ( i + r ) mod d ) z ( i + m − 1 ) mod d , i = 1 , … , d .
The proof is deferred to Subsection A.1. For intuition, the reader may view W L x W^{L}x W L x as a shift-and-scale transformation of x x x , beginning at the L L L -th entry and preserving the cyclic order of the components modulo d d d .
Set ρ : = ∏ j = 0 d − 1 w j \rho:= \prod_{j=0}^{d-1}w_j ρ := ∏ j = 0 d − 1 w j . Since every coordinate crosses every weight exactly once in d d d iterates, W d = ρ I R d W^d=\rho I_{\mathbb{R}^d} W d = ρ I R d . Hence:
Lemma 3.3. If L = m d + r L=md+r L = m d + r , 0 ≤ r < d 0\le r<d 0 ≤ r < d , then W L = ρ m W r W^L=\rho^mW^r W L = ρ m W r .
Blockwise orbit interpolation
Fix a partition as in (3.1) with s k ≤ d s_k\le d s k ≤ d for every k k k . We call the partition orbit-admissible for W W W if, for each 1 ≤ k ≤ K 1\le k\le K 1 ≤ k ≤ K , there exist depths
L k , 1 , … , L k , s k ∈ { 0 , … , d − 1 } L_{k,1},\ldots,L_{k,s_k}\in\{0,\ldots,d-1\} L k , 1 , … , L k , s k ∈ { 0 , … , d − 1 }
such that the orbit representatives
z k , j : = W L k , j x k , j , j = 1 , … , s k , z_{k,j}:=W^{L_{k,j}}x_{k,j},\qquad j=1,\ldots,s_k, z k , j := W L k , j x k , j , j = 1 , … , s k ,
are linearly independent. In what follows, assume that the partition is orbit-admissible and choose such depths for each block.
Define
Z k : = [ z k , 1 ⋯ z k , s k ] ∈ R d × s k , Y k : = [ y k , 1 ⋯ y k , s k ] ∈ R C × s k . (2) Z_k:=\begin{bmatrix}z_{k,1}&\cdots&z_{k,s_k}\end{bmatrix}\in\mathbb{R}^{d\times s_k},\qquad
Y_k:=\begin{bmatrix}y_{k,1}&\cdots&y_{k,s_k}\end{bmatrix}\in\mathbb{R}^{C\times s_k}. \tag*{(2)} Z k := [ z k , 1 ⋯ z k , s k ] ∈ R d × s k , Y k := [ y k , 1 ⋯ y k , s k ] ∈ R C × s k . (2)
Since Z k Z_k Z k has full column rank, the canonical interpolant J k : = Y k Z k † ∈ L ( R d , R C ) J_k:=Y_kZ_k^\dagger\in\mathcal{L}(\mathbb{R}^{d},\mathbb{R}^{C}) J k := Y k Z k † ∈ L ( R d , R C ) satisfies
J k W L k , j x k , j = J k z k , j = y k , j , j = 1 , … , s k . (3) J_kW^{L_{k,j}}x_{k,j}=J_kz_{k,j}=y_{k,j},\qquad j=1,\ldots,s_k. \tag*{(3)} J k W L k , j x k , j = J k z k , j = y k , j , j = 1 , … , s k . (3)
Moreover, ∥ J k ∥ ≤ ∥ Y k ∥ F / σ min ( Z k ) \lVert J_k\rVert\le\lVert Y_k\rVert_F/\sigma_{\min}(Z_k) ∥ J k ∥ ≤ ∥ Y k ∥ F / σ m i n ( Z k ) , so the conditioning of the orbit matrix Z k Z_k Z k controls the amplification associated with blockwise interpolation.
Additionally, we show that exact interpolation also survives in the infinite-dimensional setting through a constructive application of the Hahn–Banach theorem; readers interested in this extension are referred to Subsection A.2.
A natural question is how restrictive the orbit-independence hypothesis underlying exact interpolation is. The next result shows that, whenever this condition is feasible for a given block, it is topologically generic and robust, and holds Lebesgue-almost everywhere: the admissible weights form an open dense subset of weight space, and the exceptional set has Lebesgue measure zero. Complete proof in Subsection A.2.
Theorem 3.4 (Genericity of the orbit-independence condition). Let D = ( x i , y i ) i = 1 s ⊂ R d × R C D = (x_i, y_i)_{i=1}^{s} \subset\mathbb{R}^{d} \times\mathbb{R}^{C} D = ( x i , y i ) i = 1 s ⊂ R d × R C , s ≤ d s \le d s ≤ d , and let Ω : = ( R \ { 0 } ) d \Omega:= (\mathbb{R}\backslash\{0\})^{d} Ω := ( R \ { 0 } ) d . For each w = ( w 0 , … , w d − 1 ) ∈ Ω w = (w_0, \ldots, w_{d-1}) \in\Omega w = ( w 0 , … , w d − 1 ) ∈ Ω , let W w W_w W w denote the wrapped weighted backward shift determined by w w w . Define z i : = W w L i x i z_i := W_w^{L_i}x_i z i := W w L i x i and
Ω D : = { w ∈ Ω : ∃ L 1 , … , L s ∈ { 0 , … , d − 1 } such that z i ∉ span { z 1 , … , z i − 1 } for 1 ≤ i ≤ s } . \Omega_D := \left\{w \in\Omega: \exists L_1,\ldots,L_s \in\{0,\ldots,d-1\}\ \text{such that } z_i \notin\operatorname{span}\{z_1,\ldots,z_{i-1}\}\ \text{for } 1 \le i \le s\right\}. Ω D := { w ∈ Ω : ∃ L 1 , … , L s ∈ { 0 , … , d − 1 } such that z i ∈ / span { z 1 , … , z i − 1 } for 1 ≤ i ≤ s } . If Ω D ≠ ∅ \Omega_D \ne\varnothing Ω D = ∅ , then Ω D \Omega_D Ω D is open and dense in Ω \Omega Ω . Moreover, Ω \ Ω D \Omega\backslash\Omega_D Ω\ Ω D has Lebesgue measure zero.
Proof sketch. For each depth tuple L = ( L 1 , … , L s ) L = (L_1,\ldots,L_s) L = ( L 1 , … , L s ) , the entries and s × s s \times s s × s minors of
M L ( w ) = [ W w L 1 x 1 ⋯ W w L s x s ] M_L(w) = [W_w^{L_1}x_1\ \cdots\ W_w^{L_s}x_s] M L ( w ) = [ W w L 1 x 1 ⋯ W w L s x s ]
are polynomial in w w w . Thus Ω D \Omega_D Ω D is a finite union of polynomial nonvanishing sets and is open. If Ω D ≠ ∅ \Omega_D \ne\varnothing Ω D = ∅ , some minor p p p is nonzero at an admissible weight and hence is not the zero polynomial. Since
Ω \ Ω D ⊆ { w ∈ Ω : p ( w ) = 0 } , \Omega\backslash\Omega_D \subseteq\{w \in\Omega: p(w) = 0\}, Ω\ Ω D ⊆ { w ∈ Ω : p ( w ) = 0 } ,
and the zero set of a nonzero polynomial has empty interior and Lebesgue measure zero, the remaining conclusions follow.
From local interpolation to the orbit scaffold.
The selected depths in Equation (3) provide one target-matching orbit position for each anchor. To construct the dictionary, we retain the other orbit positions as well, using
J k W m x k , j , 0 ≤ m ≤ d − 1 , J_k W^m x_{k,j}, \qquad0 \le m \le d-1, J k W m x k , j , 0 ≤ m ≤ d − 1 ,
as candidate atoms for sparse synthesis. Lemma 3.3 shows that deeper iterates contribute no additional directions, since they are scalar multiples of these finite-depth iterates. Thus orbit interpolation establishes the anchor constraints, while the full orbit family provides the dictionary in which subsequent realizations are built.
When the original anchors also admit linear interpolants, these provide local reference maps. The local-chart analysis in § 3.4 below quantifies how orbit interpolation changes the resulting dictionary geometry and its bounded-coefficient sparse approximation properties.
Therefore, we build the scaffold from the full finite orbit family generated by these anchors. Specifically, define the orbit-based dictionary
D : = { J k W m x k , j : ( x k , j , y k , j ) ∈ D k , 1 ≤ k ≤ K , 0 ≤ m ≤ d − 1 } ⊆ R C . (4) \mathcal{D} := \left\{J_k W^m x_{k,j} : (x_{k,j},y_{k,j}) \in D_k,\ 1 \le k \le K,\ 0 \le m \le d-1\right\} \subseteq\mathbb{R}^{C}. \tag*{(4)} D := { J k W m x k , j : ( x k , j , y k , j ) ∈ D k , 1 ≤ k ≤ K , 0 ≤ m ≤ d − 1 } ⊆ R C . (4)
We use this notation throughout:
I : = { ( k , j , m ) : 1 ≤ k ≤ K , 1 ≤ j ≤ s k , 0 ≤ m ≤ d − 1 } , P : = ∣ I ∣ . \mathcal{I} := \{(k,j,m) : 1 \le k \le K,\ 1 \le j \le s_k,\ 0 \le m \le d-1\}, \qquad P := |\mathcal{I}|. I := {( k , j , m ) : 1 ≤ k ≤ K , 1 ≤ j ≤ s k , 0 ≤ m ≤ d − 1 } , P := ∣ I ∣.
We call U : = span D U := \operatorname{span}\mathcal{D} U := span D the orbit scaffold and denote Π U : R C → R C \Pi_U : \mathbb{R}^{C} \to\mathbb{R}^{C} Π U : R C → R C the associated orthogonal projector and write
g k , j , m : = J k W m x k , j ∈ R C , G : = [ g r ] r ∈ I ∈ R C × P . (5) g_{k,j,m} := J_k W^m x_{k,j} \in\mathbb{R}^{C}, \qquad G := [g_r]_{r \in\mathcal{I}} \in\mathbb{R}^{C \times P}. \tag*{(5)} g k , j , m := J k W m x k , j ∈ R C , G := [ g r ] r ∈ I ∈ R C × P . (5)
I + : = { r ∈ I : ∥ g r ∥ > 0 } , q r : = g r ∥ g r ∥ , r ∈ I + \mathcal{I}_{+}:=\{r\in\mathcal{I}:\|g_r\|>0\},\qquad q_r:=\frac{g_r}{\|g_r\|},\quad r\in\mathcal{I}_{+} I + := { r ∈ I : ∥ g r ∥ > 0 } , q r := ∥ g r ∥ g r , r ∈ I + .
Define the fixed synthesis map associated with the orbit dictionary as
S D : R P ⟶ U , S D ( a ) : = ∑ ( k , j , m ) ∈ I a k , j , m g k , j , m = G a , U = range G . (6) S_D:\mathbb{R}^{P}\longrightarrow U,\qquad S_D(a):=\sum_{(k,j,m)\in\mathcal{I}}a_{k,j,m}g_{k,j,m}=Ga,\qquad U=\operatorname{range}G. \tag*{(6)} S D : R P ⟶ U , S D ( a ) := ( k , j , m ) ∈ I ∑ a k , j , m g k , j , m = G a , U = range G . (6)
By Lemma 3.3, depths 0 ≤ m ≤ d − 1 0\le m\le d-1 0 ≤ m ≤ d − 1 contain all distinct orbit directions generated by W W W up to scalar multiplication, since every deeper iterate is a scalar multiple of one of these residue classes. Moreover, the selected depths L k , j L_{k,j} L k , j guarantee exact interpolation on the anchors. Thus, { y : ( x , y ) ∈ Ξ s u b } ⊆ D \{y:(x,y)\in\Xi_{\mathrm{sub}}\}\subseteq\mathcal{D} { y : ( x , y ) ∈ Ξ sub } ⊆ D . So every column y k , j y_{k,j} y k , j of Y k Y_k Y k belongs to D \mathcal{D} D . Conversely, since J k = Y k Z k T J_k=Y_kZ_k^{\mathsf{T}} J k = Y k Z k T , every atom J k W m x k , j J_kW^mx_{k,j} J k W m x k , j belongs to range ( Y k ) \operatorname{range}(Y_k) range ( Y k ) . Hence
U = span D = ∑ k = 1 K range ( Y k ) = span { y : ( x , y ) ∈ Ξ s u b } . (7) U=\operatorname{span}\mathcal{D}=\sum_{k=1}^{K}\operatorname{range}(Y_k)=\operatorname{span}\{y:(x,y)\in\Xi_{\mathrm{sub}}\}. \tag*{(7)} U = span D = k = 1 ∑ K range ( Y k ) = span { y : ( x , y ) ∈ Ξ sub } . (7)
Therefore, for fixed anchors, changing the shift or partition changes the dictionary’s internal geometry, but not its full span.
The two realizability bottlenecks. Let f Ξ : R d → R C f_{\Xi}:\mathbb{R}^{d}\to\mathbb{R}^{C} f Ξ : R d → R C be an empirical target map, and let f ^ : R d → R C \hat{f}:\mathbb{R}^{d}\to\mathbb{R}^{C} f ^ : R d → R C . Inserting the projected target and applying the triangle inequality gives
∥ f Ξ − f ^ ∥ Ξ t r a i n ≤ ∥ f Ξ − Π U f Ξ ∥ Ξ t r a i n ⏟ ε p r o j + ∥ Π U f Ξ − f ^ ∥ Ξ t r a i n ⏟ ε p a r a m . (8) \|f_{\Xi}-\hat{f}\|_{\Xi_{\mathrm{train}}}\leq
\underbrace{\|f_{\Xi}-\Pi_Uf_{\Xi}\|_{\Xi_{\mathrm{train}}}}_{\varepsilon_{\mathrm{proj}}}
+
\underbrace{\|\Pi_Uf_{\Xi}-\hat{f}\|_{\Xi_{\mathrm{train}}}}_{\varepsilon_{\mathrm{param}}}. \tag*{(8)} ∥ f Ξ − f ^ ∥ Ξ train ≤ ε proj ∥ f Ξ − Π U f Ξ ∥ Ξ train + ε param ∥ Π U f Ξ − f ^ ∥ Ξ train . (8)
The decomposition identifies the two structural bottlenecks governing realization on an orbit scaffold. The projection error ε p r o j \varepsilon_{\mathrm{proj}} ε proj measures how well U U U captures the target set { f Ξ x : ( x , y ) ∈ Ξ t r a i n } \{f_{\Xi}x:(x,y)\in\Xi_{\mathrm{train}}\} { f Ξ x : ( x , y ) ∈ Ξ train } , and depends only on the target map and the selected scaffold. The realization error ε p a r a m \varepsilon_{\mathrm{param}} ε param measures how accurately the projected target Π U f Ξ \Pi_Uf_{\Xi} Π U f Ξ is realized once U U U has been fixed. The remainder of this section addresses these two bottlenecks in order: first the selection of an orbit scaffold with small projection error, and then the constructive realization of the projected target on that scaffold.
Scaffold selection and dictionary geometry
The existence of optimal scaffolds under which projection error collapses, is a mathematically well-posed problem. Indeed, by the scaffold identity (7) , each admissible anchor subset determines its full scaffold through the span of its targets. Since the training set is finite, the family of such scaffolds is finite, and the projection error attains a minimum over any nonempty admissible family. Hence, there exists U ⋆ ∈ U U^{\star}\in\mathcal{U} U ⋆ ∈ U such that ∥ f Ξ − Π U ⋆ f Ξ ∥ Ξ t r a i n = min U ∈ U ∥ f Ξ − Π U f Ξ ∥ Ξ t r a i n \|f_{\Xi}-\Pi_{U^{\star}}f_{\Xi}\|_{\Xi_{\mathrm{train}}}=\min_{U\in\mathcal{U}}\|f_{\Xi}-\Pi_Uf_{\Xi}\|_{\Xi_{\mathrm{train}}} ∥ f Ξ − Π U ⋆ f Ξ ∥ Ξ train = min U ∈ U ∥ f Ξ − Π U f Ξ ∥ Ξ train , where U \mathcal{U} U the set of all scaffolds relative to Ξ t r a i n \Xi_{\mathrm{train}} Ξ train . This guarantee is existential. We provide the details on the practical implementation of scaffold selection in Subsection 3.6 below. We now derive an observable quantity serving as a pre-selection criterion.
Observable stability of orbit-sparse realizability. By (7) , the full orbit scaffold is determined by the anchor targets, while the geometry of its generating dictionary depends on the chosen orbit configuration. We now show that the observable quantity S ( P ) S(\mathcal{P}) S ( P ) defined in (9) below controls this internal geometry in a sense directly relevant to sparse realization.
Let P = { D 1 , … , D K } \mathcal{P}=\{D_1,\ldots,D_K\} P = { D 1 , … , D K } be an orbit-admissible partition of Ξ s u b \Xi_{\mathrm{sub}} Ξ sub , with
D k = { ( x k , j , y k , j ) } j = 1 s k , N = ∑ k = 1 K s k . D_k=\{(x_{k,j},y_{k,j})\}_{j=1}^{s_k},\qquad N=\sum_{k=1}^{K}s_k. D k = {( x k , j , y k , j ) } j = 1 s k , N = k = 1 ∑ K s k .
Set X k = [ x k , 1 ⋯ x k , s k ] X_k=[x_{k,1}\ \cdots\ x_{k,s_k}] X k = [ x k , 1 ⋯ x k , s k ] , and retain the preceding notation Y k Y_k Y k , Z k Z_k Z k and J k = Y k Z k † J_k=Y_kZ_k^\dagger J k = Y k Z k † . Assume
ker X k ⊆ ker Y k , 1 ≤ k ≤ K . \ker X_k\subseteq\ker Y_k,\qquad1\leq k\leq K. ker X k ⊆ ker Y k , 1 ≤ k ≤ K .
Set E k : = range Z k E_k:=\operatorname{range}Z_k E k := range Z k . The quantity
S ( P ) : = ∑ k = 1 K ∑ j = 1 s k ∥ Y k ∥ F σ min ( X k ) ( dist ( x k , j , E k ) + ∥ x k , j ∥ σ min ( Z k ) ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1 / 2 ) N (9) S(\mathcal{P}):=\frac{\sum_{k=1}^{K}\sum_{j=1}^{s_k}\frac{\lVert Y_k\rVert_F}{\sigma_{\min}(X_k)}
\left(\operatorname{dist}(x_{k,j},E_k)+\frac{\lVert x_{k,j}\rVert}{\sigma_{\min}(Z_k)}
\left(\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}-z_{k,\ell}\rVert^2\right)^{1/2}\right)}
{N} \tag*{(9)} S ( P ) := N ∑ k = 1 K ∑ j = 1 s k σ m i n ( X k ) ∥ Y k ∥ F ( dist ( x k , j , E k ) + σ m i n ( Z k ) ∥ x k , j ∥ ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1/2 ) (9)
is therefore computable from the selected anchor configuration.
To identify what this quantity controls, define the canonical local-chart operator
A k : = Y k X k † . A_k:=Y_kX_k^\dagger. A k := Y k X k † .
The compatibility assumption ensures that A k x k , j = y k , j A_kx_{k,j}=y_{k,j} A k x k , j = y k , j . Thus A k A_k A k interpolates the original anchors, whereas J k J_k J k interpolates their orbit representatives. This gives a natural reference dictionary
D c h a r t : = { A k Π E k W m x k , j : ( k , j , m ) ∈ I } , \mathcal{D}_{\mathrm{chart}}:=\{A_k\Pi_{E_k}W^m x_{k,j}:(k,j,m)\in\mathcal{I}\}, D chart := { A k Π E k W m x k , j : ( k , j , m ) ∈ I } ,
whose atoms are generated by the original local charts restricted to the corresponding orbit-representative spaces. Comparing D c h a r t \mathcal{D}_{\mathrm{chart}} D chart with the actual orbit dictionary D \mathcal{D} D isolates the geometric distortion introduced by orbit interpolation.
For any dictionary B \mathcal{B} B with index set I \mathcal{I} I , let S B S_{\mathcal{B}} S B denote its synthesis map. Given an integer 1 ≤ s ≤ P 1\leq s\leq P 1 ≤ s ≤ P and B > 0 B>0 B > 0 , define the constrained sparse realization error
e s , B ( y ; B ) : = inf a ∈ R P ∣ { r ∈ I : a r ≠ 0 } ∣ ≤ s ∑ r ∈ I ∣ a r ∣ ≤ B ∥ y − S B ( a ) ∥ . e_{s,B}(y;\mathcal{B}):=\inf_{\substack{a\in\mathbb{R}^{P}\\
|\{r\in\mathcal{I}:a_r\neq0\}|\leq s\\
\sum_{r\in\mathcal{I}}|a_r|\leq B}}
\lVert y-S_{\mathcal{B}}(a)\rVert. e s , B ( y ; B ) := a ∈ R P ∣ { r ∈ I : a r = 0 } ∣ ≤ s ∑ r ∈ I ∣ a r ∣ ≤ B inf ∥ y − S B ( a )∥ .
The coefficient bound prevents small atom perturbations from being arbitrarily amplified by large coefficients. Finally, define the observable orbit-amplification factor
κ ( P ) : = max ( k , j , m ) ∈ I ∥ W m x k , j ∥ ∑ ℓ = 1 s k ∥ x k , ℓ ∥ . \kappa(\mathcal{P}):=\max_{(k,j,m)\in\mathcal{I}}
\frac{\lVert W^m x_{k,j}\rVert}{\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}\rVert}. κ ( P ) := ( k , j , m ) ∈ I max ∑ ℓ = 1 s k ∥ x k , ℓ ∥ ∥ W m x k , j ∥ .
Theorem 3.5 (Observable stability of orbit-sparse realizability). Under the preceding assumptions, for every y ∈ R C y\in\mathbb{R}^{C} y ∈ R C , 1 ≤ s ≤ P 1\leq s\leq P 1 ≤ s ≤ P , and B > 0 B>0 B > 0 ,
∣ e s , B ( y ; D ) − e s , B ( y ; D c h a r t ) ∣ ≤ B N κ ( P ) S ( P ) . \left|e_{s,B}(y;\mathcal{D})-e_{s,B}(y;\mathcal{D}_{\mathrm{chart}})\right|\leq BN\kappa(\mathcal{P})S(\mathcal{P}). ∣ e s , B ( y ; D ) − e s , B ( y ; D chart ) ∣ ≤ B N κ ( P ) S ( P ) .
Proof sketch. The compatibility condition gives Y k = A k X k Y_k=A_kX_k Y k = A k X k , and hence
J k − A k Π E k = A k ( X k − Z k ) Z k † . J_k-A_k\Pi_{E_k}=A_k(X_k-Z_k)Z_k^\dagger. J k − A k Π E k = A k ( X k − Z k ) Z k † .
The resulting operator bound, combined with the definition of S ( P ) S(\mathcal{P}) S ( P ) , yields
max ( k , j , m ) ∈ I ∥ ( J k − A k Π E k ) W m x k , j ∥ ≤ N κ ( P ) S ( P ) . \max_{(k,j,m)\in\mathcal{I}}\left\|(J_k-A_k\Pi_{E_k})W^m x_{k,j}\right\|\le N\kappa(\mathcal{P})S(\mathcal{P}). ( k , j , m ) ∈ I max ∥ ( J k − A k Π E k ) W m x k , j ∥ ≤ N κ ( P ) S ( P ) .
Thus synthesis with any common admissible coefficient vector differs between the two dictionaries by at most B N κ ( P ) S ( P ) BN\kappa(\mathcal{P})S(\mathcal{P}) B N κ ( P ) S ( P ) . Taking the infimum over the same coefficient set proves the assertion. The details are given in Subsection A.5.
Theorem 3.5 shows that S ( P ) S(\mathcal{P}) S ( P ) controls the distortion of the entire bounded-coefficient sparse approximation problem, uniformly over targets and sparsity budgets. Consequently, among candidate anchor configurations with comparable orbit amplification, minimizing S ( P ) S(\mathcal{P}) S ( P ) favors dictionaries whose sparse realization geometry remains close to that induced by the original local charts. This provides a structural justification for its use as a pre-selection criterion, independently of the projection quality of the full scaffold.
Collapsing the parametrization error: the CCDS mechanism
Once U U U is fixed, standard sparse approximation methods such as Orthogonal Matching Pursuit (OMP) can be used to reduce the parametrization error, and in finite dimension can recover the orthogonal projection once a sufficient independent atom set has been selected. Our goal is therefore not to replace OMP merely as an approximation solver. Instead, we introduce a realization mechanism in which the residual trajectory itself becomes a controllable geometric object: Constructive Controlled Deviation Synthesis (CCDS).
Why CCDS if OMP already realizes the scaffold? OMP selects an atom, enlarges the current span, and refits by least squares; the resulting residual is therefore determined by the extremal orthogonal projection onto that span. CCDS retains the same span-building logic but replaces the rigid least-squares update by a controlled realization path: rather than accepting the residual dictated by the orthogonal projection at each step, it allows the residual decay to be prescribed within the geometry permitted by the current realization space. Thus, unlike OMP, which treats sparse realization as an endpoint approximation problem, CCDS turns it into a stepwise controllable process. Both OMP and CCDS can accurately realize targets on a fixed scaffold, but OMP is confined to the extremal least-squares update on each selected span. CCDS can instead move through the interior of the feasible deviation geometry by prescribing admissible residual levels, while OMP has no parameter with which to realize those prescribed interior paths. This distinction is explicit in difficult geometry (see Experiments Section 4): at the minimal-deviation boundary CCDS agrees with OMP, whereas strict interior schedules generate feasible realization trajectories unavailable to OMP; under a fixed step budget, increasingly interior schedules deliberately trade residual contraction for greater path control. Thus deviation control enlarges the realizable trajectory class rather than uniformly improving endpoint approximation.
From Bernstein-type prescribed approximation to deviation control. The CCDS viewpoint is motivated by the Bernstein-type lethargy theory question of prescribing approximation errors along a nested family of subspaces, rather than merely taking the best approximation available at each stage. Let H H H be a real Hilbert space
Y 0 ⊂ Y 1 ⊂ ⋯ ⊂ Y T ⊂ H , Y t = Y t − 1 ⊕ span { u t } , u t ∈ Y t − 1 ⊥ , ∥ u t ∥ = 1. Y_0 \subset Y_1 \subset\cdots\subset Y_T \subset H,\qquad Y_t = Y_{t-1} \oplus\operatorname{span}\{u_t\},\qquad u_t \in Y_{t-1}^{\perp},\ \lVert u_t\rVert= 1. Y 0 ⊂ Y 1 ⊂ ⋯ ⊂ Y T ⊂ H , Y t = Y t − 1 ⊕ span { u t } , u t ∈ Y t − 1 ⊥ , ∥ u t ∥ = 1.
Given a target y ∈ H y \in H y ∈ H , initialize y ^ 0 = 0 \hat{y}_0 = 0 y ^ 0 = 0 and r 0 = y r_0 = y r 0 = y , and update
y ^ t = y ^ t − 1 + λ t u t , r t = r t − 1 − λ t u t . (10) \hat{y}_t = \hat{y}_{t-1} + \lambda_t u_t,\qquad r_t = r_{t-1} - \lambda_t u_t. \tag*{(10)} y ^ t = y ^ t − 1 + λ t u t , r t = r t − 1 − λ t u t . (10)
Instead of forcing the extremal projection at every step, we prescribe a deviation d t : = dist ( r t , Y t − 1 ) d_t := \operatorname{dist}(r_t,Y_{t-1}) d t := dist ( r t , Y t − 1 ) . Thus the entire stepwise realization problem reduces to the scalar distance equation
dist ( r t − 1 − λ t u t , Y t − 1 ) = d t . (11) \operatorname{dist}(r_{t-1} - \lambda_t u_t,Y_{t-1}) = d_t. \tag*{(11)} dist ( r t − 1 − λ t u t , Y t − 1 ) = d t . (11)
The next result completely characterizes when this equation is feasible and gives the corresponding coefficient λ t \lambda_t λ t explicitly, thereby turning prescribed approximation geometry into a constructive finite-horizon realization mechanism.
Theorem 3.6 (Constructive controlled-deviation principle). Under the preceding notation, for each t t t , define
a t : = ( I − Π Y t − 1 ) r t − 1 , α t : = ⟨ a t , u t ⟩ , d t , min : = ∥ a t ∥ 2 − α t 2 . a_t := (I-\Pi_{Y_{t-1}})r_{t-1},\qquad\alpha_t := \langle a_t,u_t\rangle,\qquad d_{t,\min} := \sqrt{\lVert a_t\rVert^2-\alpha_t^2}. a t := ( I − Π Y t − 1 ) r t − 1 , α t := ⟨ a t , u t ⟩ , d t , m i n := ∥ a t ∥ 2 − α t 2 . Then the prescribed deviation equation (11) is feasible if and only if d t ≥ d t , min d_t \ge d_{t,\min} d t ≥ d t , m i n , in which case
λ t = α t ± d t 2 − d t , min 2 . (12) \lambda_t = \alpha_t \pm\sqrt{d_t^2-d_{t,\min}^2}. \tag*{(12)} λ t = α t ± d t 2 − d t , m i n 2 . (12) Consequently, every feasible deviation profile ( d t ) t = 1 T (d_t)_{t=1}^{T} ( d t ) t = 1 T can be realized constructively by the updates (10) satisfying exactly dist ( r t , Y t − 1 ) = d t \operatorname{dist}(r_t,Y_{t-1}) = d_t dist ( r t , Y t − 1 ) = d t , for all t = 1 , … , T t=1,\ldots,T t = 1 , … , T .
Proof. We proceed sequentially in t t t . Suppose that λ 1 , … , λ t − 1 \lambda_1,\ldots,\lambda_{t-1} λ 1 , … , λ t − 1 have already been chosen, so that y ^ t − 1 ∈ Y t − 1 \hat{y}_{t-1} \in Y_{t-1} y ^ t − 1 ∈ Y t − 1 and r t − 1 = y − y ^ t − 1 r_{t-1}=y-\hat{y}_{t-1} r t − 1 = y − y ^ t − 1 are determined. Since u t ∈ Y t ∩ Y t − 1 ⊥ u_t \in Y_t \cap Y_{t-1}^{\perp} u t ∈ Y t ∩ Y t − 1 ⊥ and ∥ u t ∥ = 1 \lVert u_t\rVert=1 ∥ u t ∥ = 1 . By Lemma A.4 , the equation dist ( r t − 1 − λ u t , Y t − 1 ) = d t \operatorname{dist}(r_{t-1}-\lambda u_t,Y_{t-1})=d_t dist ( r t − 1 − λ u t , Y t − 1 ) = d t admits a real solution if and only if d t ≥ ∥ a t ∥ 2 − α t 2 = d t , min d_t \ge\sqrt{\lVert a_t\rVert^2-\alpha_t^2}=d_{t,\min} d t ≥ ∥ a t ∥ 2 − α t 2 = d t , m i n . Under the assumed feasibility condition, its solutions are precisely
λ = α t ± d t 2 − d t , min 2 . \lambda= \alpha_t \pm\sqrt{d_t^2-d_{t,\min}^2}. λ = α t ± d t 2 − d t , m i n 2 .
Choose one of these two roots according to the prescribed deterministic rule and denote it by λ t \lambda_t λ t . Define
y ^ t : = y ^ t − 1 + λ t u t , r t : = y − y ^ t . \hat{y}_t := \hat{y}_{t-1}+\lambda_tu_t,\qquad r_t := y-\hat{y}_t. y ^ t := y ^ t − 1 + λ t u t , r t := y − y ^ t .
Since y ^ t − 1 ∈ Y t − 1 ⊂ Y t \hat{y}_{t-1}\in Y_{t-1}\subset Y_t y ^ t − 1 ∈ Y t − 1 ⊂ Y t and u t ∈ Y t u_t\in Y_t u t ∈ Y t , one has y ^ t ∈ Y t \hat{y}_t\in Y_t y ^ t ∈ Y t . Moreover,
r t = y − y ^ t − 1 − λ t u t = r t − 1 − λ t u t . r_t = y-\hat{y}_{t-1}-\lambda_tu_t = r_{t-1}-\lambda_tu_t. r t = y − y ^ t − 1 − λ t u t = r t − 1 − λ t u t .
Therefore, by the defining choice of λ t \lambda_t λ t ,
dist ( r t , Y t − 1 ) = dist ( r t − 1 − λ t u t , Y t − 1 ) = d t . \operatorname{dist}(r_t,Y_{t-1})=\operatorname{dist}(r_{t-1}-\lambda_tu_t,Y_{t-1})=d_t. dist ( r t , Y t − 1 ) = dist ( r t − 1 − λ t u t , Y t − 1 ) = d t .
Starting from y ^ 0 = 0 \hat{y}_0=0 y ^ 0 = 0 and r 0 = y r_0=y r 0 = y , this construction can be applied successively for t = 1 , … , T t=1,\ldots,T t = 1 , … , T . Hence every feasible profile ( d t ) t = 1 T (d_t)_{t=1}^{T} ( d t ) t = 1 T is realized, and the resulting coefficients satisfy Equation (12) . The deterministic root-selection rule makes the resulting sequence ( λ t ) t = 1 T (\lambda_t)_{t=1}^{T} ( λ t ) t = 1 T deterministic.
We next instantiate this abstract deviation-control principle on the orbit dictionary used by our realization framework.
Dictionary-induced CCDS realization. To instantiate Theorem 3.6 on the orbit dictionary, let D ⊂ H \mathcal{D}\subset H D ⊂ H be unit norm. At step t t t , given Y t − 1 Y_{t-1} Y t − 1 and r t − 1 r_{t-1} r t − 1 , select an atom q t ∈ D ∖ Y t − 1 q_t\in\mathcal{D}\setminus Y_{t-1} q t ∈ D ∖ Y t − 1 and define
η t : = ∥ q t − Π Y t − 1 q t ∥ , u t : = q t − Π Y t − 1 q t η t , Y t : = Y t − 1 ⊕ span { u t } . (14) \eta_t:=\lVert q_t-\Pi_{Y_{t-1}}q_t\rVert,\qquad u_t:=\frac{q_t-\Pi_{Y_{t-1}}q_t}{\eta_t},\qquad Y_t:=Y_{t-1}\oplus\operatorname{span}\{u_t\}. \tag*{(14)} η t := ∥ q t − Π Y t − 1 q t ∥ , u t := η t q t − Π Y t − 1 q t , Y t := Y t − 1 ⊕ span { u t } . (14)
For any feasible prescribed deviation d t ≥ d t , min d_t\ge d_{t,\min} d t ≥ d t , m i n , Theorem 3.6 determines λ t \lambda_t λ t explicitly and updates
y ^ t = y ^ t − 1 + λ t u t , r t = y − y ^ t . \hat{y}_t=\hat{y}_{t-1}+\lambda_tu_t,\qquad r_t=y-\hat{y}_t. y ^ t = y ^ t − 1 + λ t u t , r t = y − y ^ t .
Since q t ∉ Y t − 1 q_t\notin Y_{t-1} q t ∈ / Y t − 1 and Y t = span { q 1 , … , q t } Y_t=\operatorname{span}\{q_1,\ldots,q_t\} Y t = span { q 1 , … , q t } , the selected atoms q 1 , … , q T q_1,\ldots,q_T q 1 , … , q T are linearly independent. Moreover, u t ∈ span { q 1 , … , q t } u_t\in\operatorname{span}\{q_1,\ldots,q_t\} u t ∈ span { q 1 , … , q t } for every t t t . Consequently, for every CCDS path q 1 : T q_{1:T} q 1 : T there exists a unique β ( T ) ∈ R T \beta^{(T)}\in\mathbb{R}^T β ( T ) ∈ R T such that
y ^ T = ∑ t = 1 T λ t u t = ∑ j = 1 T β j ( T ) q j . \hat{y}_T=\sum_{t=1}^{T}\lambda_tu_t=\sum_{j=1}^{T}\beta_j^{(T)}q_j. y ^ T = t = 1 ∑ T λ t u t = j = 1 ∑ T β j ( T ) q j .
We call β ( T ) \beta^{(T)} β ( T ) the CCDS dictionary-coordinate vector . Its explicit triangular recursion in terms of the innovation coordinates is given in Subsection A.3. We denote this path-specific realization by
CCDS D T ( y ; q 1 : T , d 1 : T ) : = y ^ T , \operatorname{CCDS}_{\mathcal{D}}^{T}(y;q_{1:T},d_{1:T}):=\hat{y}_T, CCDS D T ( y ; q 1 : T , d 1 : T ) := y ^ T ,
for the CCDS output after T T T steps. Here q 1 : T : = ( q 1 , … , q T ) q_{1:T}:=(q_1,\ldots,q_T) q 1 : T := ( q 1 , … , q T ) denotes the prescribed atom ordering and d 1 : T : = ( d 1 , … , d T ) d_{1:T}:=(d_1,\ldots,d_T) d 1 : T := ( d 1 , … , d T ) the prescribed deviation profile.
For a target y y y , let T ( y ) T(y) T ( y ) denote the termination horizon of its CCDS path. We denote by
β D ( y ) ∈ R P \beta_{\mathcal{D}}(y)\in\mathbb{R}^{P} β D ( y ) ∈ R P
the full-dictionary CCDS coordinate vector obtained by placing the path-specific coefficients β ( T ( y ) ) \beta^{(T(y))} β ( T ( y )) in the selected dictionary coordinates and setting every unselected coordinate equal to zero. If CCDS is run using normalized atoms, the corresponding normalization factors are absorbed into β D ( y ) \beta_D(y) β D ( y ) so that synthesis is always performed with the original atoms d k , j , m d_{k,j,m} d k , j , m . We fix the atom-selection rule, deviation profile, root choices, and all tie-breaking conventions; consequently, y ↦ β D ( y ) y \mapsto\beta_D(y) y ↦ β D ( y ) is a well-defined map. With this notation,
CCDS D ( y ) = S D ( β D ( y ) ) . (15) \operatorname{CCDS}_D(y)=S_D(\beta_D(y)). \tag*{(15)} CCDS D ( y ) = S D ( β D ( y )) . (15)
The nested orthogonal-innovation construction is designed so that, at the minimal deviation boundary, CCDS recovers the Fourier coefficients of the target in the induced orthonormal basis. Proof of Proposition 3.8 in Subsection A.3.
Proposition 3.8 (Minimal-deviation CCDS recovers the orthogonal coordinates). Let D ⊂ H \mathcal{D} \subset H D ⊂ H be a unit-norm dictionary, let q 1 , … , q s ∈ D q_1,\ldots,q_s \in\mathcal{D} q 1 , … , q s ∈ D be linearly independent, and set E : = span { q 1 , … , q s } E := \operatorname{span}\{q_1,\ldots,q_s\} E := span { q 1 , … , q s } . For y ∈ H y \in H y ∈ H , apply CCDS with atom ordering q 1 : s q_{1:s} q 1 : s and d t = d t , min d_t=d_{t,\min} d t = d t , m i n for t = 1 , … , s t=1,\ldots,s t = 1 , … , s . Then
CCDS D s ( y ; q 1 : s , d min , 1 : s ) = Π E y = ∑ t = 1 s λ t u t = ∑ j = 1 s β j ( s ) q j , \operatorname{CCDS}_{\mathcal{D}}^s(y;q_{1:s},d_{\min,1:s})=\Pi_E y=\sum_{t=1}^{s}\lambda_tu_t=\sum_{j=1}^{s}\beta_j^{(s)}q_j, CCDS D s ( y ; q 1 : s , d m i n , 1 : s ) = Π E y = t = 1 ∑ s λ t u t = j = 1 ∑ s β j ( s ) q j , where λ t = ⟨ y , u t ⟩ \lambda_t=\langle y,u_t\rangle λ t = ⟨ y , u t ⟩ and β ( s ) \beta^{(s)} β ( s ) is the CCDS dictionary-coordinate vector.
MP and OMP as minimal-deviation boundaries. Neither Matching Pursuit (MP) nor OMP is, in general, a special case of the other. CCDS, however, provides a common geometric mechanism containing both as boundary regimes. The following proposition identifies MP and OMP as the two minimal-deviation boundary regimes of CCDS while strict interior CCDS updates are globally inaccessible to OMP, marking a geometric separation between OMP and CCDS. Complete proof in Subsection A.3.
Proposition 3.9. Let D ⊂ H \mathcal{D} \subset H D ⊂ H be a unit-norm dictionary.
(i) (MP boundary). If Y t − 1 = { 0 } Y_{t-1}=\{0\} Y t − 1 = { 0 } at every step, q t q_t q t is selected by the MP atom-selection rule, and d t = d t , min d_t=d_{t,\min} d t = d t , m i n , then CCDS coincides with MP.
(ii) (OMP boundary). If q t q_t q t is selected by the OMP atom-selection rule such that the nested spaces Y t = span { q 1 , … , q t } Y_t=\operatorname{span}\{q_1,\ldots,q_t\} Y t = span { q 1 , … , q t } , and d t = d t , min d_t=d_{t,\min} d t = d t , m i n , then CCDS coincides with OMP until termination.
(iii) (Global geometric separation from OMP). Any interior CCDS update with d t > d t , min d_t>d_{t,\min} d t > d t , m i n , λ t ≠ 0 \lambda_t\ne0 λ t = 0 , departing from an OMP boundary state y ^ t − 1 = Π Y t − 1 y \widehat{y}_{t-1}=\Pi_{Y_{t-1}}y y t − 1 = Π Y t − 1 y is globally inaccessible to OMP, irrespective of its atom selection or ordering.
Proof sketch. At minimal deviation, λ t = α t \lambda_t=\alpha_t λ t = α t , giving the MP update with a trivial reference space and the OMP projection update with nested selected spaces. Every OMP iterate satisfies
⟨ y − y ^ O M P , y ^ O M P ⟩ = 0. \langle y-\widehat{y}_{\mathrm{OMP}},\widehat{y}_{\mathrm{OMP}}\rangle=0. ⟨ y − y OMP , y OMP ⟩ = 0.
For a CCDS update departing from y ^ t − 1 = Π Y t − 1 y \widehat{y}_{t-1}=\Pi_{Y_{t-1}}y y t − 1 = Π Y t − 1 y , orthogonality gives
⟨ y − y ^ t , y ^ t ⟩ = λ t ( α t − λ t ) . \langle y-\widehat{y}_t,\widehat{y}_t\rangle=\lambda_t(\alpha_t-\lambda_t). ⟨ y − y t , y t ⟩ = λ t ( α t − λ t ) .
Strict interior deviation implies λ t ≠ α t \lambda_t\ne\alpha_t λ t = α t . If also λ t ≠ 0 \lambda_t\ne0 λ t = 0 , this violates the invariant of every OMP iterate, irrespective of its selected subspace.
Beyond the MP/OMP boundary. The additional freedom of CCDS appears when d t > d t , min d_t > d_{t,\min} d t > d t , m i n . In this regime, the update is no longer forced to be the extremal orthogonal projection. Instead, CCDS can prescribe any feasible deviation profile ( d t ) t = 1 T (d_t)_{t=1}^{T} ( d t ) t = 1 T and thereby control the realization path through the nested spaces Y t Y_t Y t .
The strict regime d t > d t , min d_t > d_{t,\min} d t > d t , m i n also gives CCDS a pathwise stability property. The perturbation stability Theorem 3.11 below shows that, when the prescribed CCDS path has a positive feasibility margin, the same atom labels, deviations, and root branches remain feasible under sufficiently small perturbations of the orbit dictionary, and the transported realization varies locally Lipschitz continuously. The boundary case d t = d t , min d_t = d_{t,\min} d t = d t , m i n , which recovers OMP for the same atom-selection rule, is not covered by this argument because the feasibility margin vanishes. Thus the distinction from OMP is not in endpoint realizability, but the ability to prescribe a realization path and obtain a stability guarantee for that prescribed path. At the coefficient level, interior choices d t > d t , min d_t > d_{t,\min} d t > d t , m i n move CCDS away from the boundary where the root term vanishes in λ t = α t ± d t 2 − d t , min 2 \lambda_t = \alpha_t \pm\sqrt{d_t^2-d_{t,\min}^2} λ t = α t ± d t 2 − d t , m i n 2 . This avoids boundary-root degeneracy.
Intrinsic orbit-certificate sparsity. The deviation-control mechanism is compatible with the intrinsic sparse geometry of the orbit dictionary. Let D \mathcal{D} D be the orbit dictionary, U = span D U = \operatorname{span}\mathcal{D} U = span D , and I \mathcal{I} I the dictionary index set. Write q k , j , m ∈ D q_{k,j,m} \in\mathcal{D} q k , j , m ∈ D for the corresponding unit-norm orbit atom. For S ⊆ I S \subseteq\mathcal{I} S ⊆ I , define
E S : = span { q k , j , m : ( k , j , m ) ∈ S } . E_S := \operatorname{span}\{q_{k,j,m} : (k,j,m) \in S\}. E S := span { q k , j , m : ( k , j , m ) ∈ S } .
For ( x i , y i ) ∈ Ξ t r a i n (x_i,y_i) \in\Xi_{\mathrm{train}} ( x i , y i ) ∈ Ξ train and 0 ≤ η ≤ ∥ Π U y i ∥ 0 \leq\eta\leq\lVert\Pi_U y_i\rVert 0 ≤ η ≤ ∥ Π U y i ∥ , set
s i ( η ) : = min { ∣ S ∣ : S ⊆ I , dist ( Π U y i , E S ) ≤ η } . s_i(\eta) := \min\{|S| : S \subseteq\mathcal{I},\ \operatorname{dist}(\Pi_U y_i,E_S) \leq\eta\}. s i ( η ) := min { ∣ S ∣ : S ⊆ I , dist ( Π U y i , E S ) ≤ η } .
Thus s i ( η ) s_i(\eta) s i ( η ) measures the intrinsic per-sample number of orbit-dictionary atoms needed to realize the projected target to tolerance η \eta η . Let S i = { r 1 , … , r s } S_i = \{r_1,\ldots,r_s\} S i = { r 1 , … , r s } be a minimizer, so that s = ∣ S i ∣ = s i ( η ) s = |S_i| = s_i(\eta) s = ∣ S i ∣ = s i ( η ) . The atoms q r 1 , … , q r s q_{r_1},\ldots,q_{r_s} q r 1 , … , q r s are linearly independent. Indeed, if one belonged to the span of the others, removing its index would leave E S i E_{S_i} E S i unchanged, contradicting the minimality of S i S_i S i . Proposition 3.8 therefore applies directly to this atom family. Since E S i ⊆ U E_{S_i} \subseteq U E S i ⊆ U , we have Π E S i y i = Π E S i Π U y i \Pi_{E_{S_i}}y_i = \Pi_{E_{S_i}}\Pi_U y_i Π E S i y i = Π E S i Π U y i . Hence, by the defining property of the minimizing support S i S_i S i ,
∥ Π U y i − Π E S i y i ∥ = dist ( Π U y i , E S i ) ≤ η . \lVert\Pi_U y_i-\Pi_{E_{S_i}}y_i\rVert= \operatorname{dist}(\Pi_U y_i,E_{S_i}) \leq\eta. ∥ Π U y i − Π E S i y i ∥ = dist ( Π U y i , E S i ) ≤ η .
Thus, we have the following.
Corollary 3.10 (Intrinsic local orbit-certificate sparsity of full CCDS). With the notation above,
CCDS D s ( y i ; q r 1 : r s , d min , 1 : s ) = Π E S i y i = ∑ j = 1 s β j ( s ) q r j , \operatorname{CCDS}_{\mathcal{D}}^s(y_i;q_{r_{1:r_s}},d_{\min,1:s}) = \Pi_{E_{S_i}}y_i = \sum_{j=1}^{s}\beta_j^{(s)}q_{r_j}, CCDS D s ( y i ; q r 1 : r s , d m i n , 1 : s ) = Π E S i y i = j = 1 ∑ s β j ( s ) q r j , and
∥ Π U y i − CCDS D s ( y i ; q r 1 : r s , d min , 1 : s ) ∥ ≤ η . \lVert\Pi_U y_i-\operatorname{CCDS}_{\mathcal{D}}^s(y_i;q_{r_{1:r_s}},d_{\min,1:s})\rVert\leq\eta. ∥ Π U y i − CCDS D s ( y i ; q r 1 : r s , d m i n , 1 : s )∥ ≤ η . In particular, this CCDS realization is supported on at most s i ( η ) s_i(\eta) s i ( η ) orbit-dictionary atoms.
Repairing CCDS infeasibility. Prescribing the realization path introduces a feasibility obstruction with no direct analogue in standard OMP: for a chosen innovation direction u t u_t u t , a desired deviation d t < d t , min d_t < d_{t,\min} d t < d t , m i n is infeasible in the current ambient space. This is the finite-dimensional analogue of the prescribed-approximation obstruction underlying Bernstein-type lethargy theory. Such infeasibility can be repaired constructively: by adjoining one orthogonal dimension, any prescribed 0 ≤ d t ≤ ∥ a t ∥ 0 \le d_t \le\lVert a_t\rVert 0 ≤ d t ≤ ∥ a t ∥ can be made feasible through a suitable lifted innovation direction. The explicit lifting theorem and its proof are given in Subsection A.4.
Stability under relaxed block interpolation
Exact interpolation provides the canonical construction, with block maps J k = Y k Z k T J_k = Y_kZ_k^{\mathsf{T}} J k = Y k Z k T recovering the anchor outputs exactly. In practice, however, we use the regularized interpolant J k , λ : = Y k ( Z k T Z k + λ I ) − 1 Z k T J_{k,\lambda} := Y_k(Z_k^{\mathsf{T}}Z_k + \lambda I)^{-1}Z_k^{\mathsf{T}} J k , λ := Y k ( Z k T Z k + λ I ) − 1 Z k T , λ > 0 \lambda> 0 λ > 0 , which is better conditioned on noisy or nearly singular blocks. The next theorem shows that this relaxation preserves the scaffold geometry and perturbs the CCDS realization error only continuously, thereby connecting the exact theory to the implementation used in practice. Complete proof in Subsection A.5.
Theorem 3.11 (Stability of the scaffold/CCDS bottlenecks under relaxed interpolation). Fix the orbit data ( W , Ξ s u b , { D k } k = 1 K ) (W,\Xi_{\mathrm{sub}}, \{D_k\}_{k=1}^{K}) ( W , Ξ sub , { D k } k = 1 K ) . For each block write Z k Z_k Z k for the orbit matrix and Y k Y_k Y k for the corresponding output matrix as defined in (2) , let J k = Y k Z k T J_k = Y_kZ_k^{\mathsf{T}} J k = Y k Z k T be the reference minimal-norm exact interpolant. Let G G G be the associated atom matrix as in (5) such that U = range ( G ) U = \operatorname{range}(G) U = range ( G ) , r : = rank ( G ) r := \operatorname{rank}(G) r := rank ( G ) , γ : = σ r ( G ) > 0 \gamma:= \sigma_r(G) > 0 γ := σ r ( G ) > 0 . Assume the reference CCDS realizer C C D S D \mathrm{CCDS}_{D} CCDS D on U U U has a finite prescribed path with positive feasibility margin and selected raw directions uniformly bounded away from zero. For every admissible relaxed block family J k ′ = Y k R k ′ J'_k = Y_kR'_k J k ′ = Y k R k ′ , where R k ′ R'_k R k ′ is a regularized pseudoinverse factor for the same block data, G ′ G' G ′ the corresponding atom matrix and U ′ : = range ( G ′ ) U' := \operatorname{range}(G') U ′ := range ( G ′ ) , there exist δ 0 > 0 \delta_0 > 0 δ 0 > 0 such that if ∥ G ′ − G ∥ 2 < δ 0 \lVert G' - G\rVert_2 < \delta_0 ∥ G ′ − G ∥ 2 < δ 0 , then U ′ = U U' = U U ′ = U . Consequently,
ε p r o j ( f Ξ , U ′ ) = ε p r o j ( f Ξ , U ) . \varepsilon_{\mathrm{proj}}(f_{\Xi},U') = \varepsilon_{\mathrm{proj}}(f_{\Xi},U). ε proj ( f Ξ , U ′ ) = ε proj ( f Ξ , U ) . Moreover, transporting the reference CCDS path to the perturbed atoms, with the same prescribed deviations and the same root branches, gives a CCDS realizer C C D S D ′ \mathrm{CCDS}_{D'} CCDS D ′ on U ′ U' U ′ satisfying
ε p a r a m ( f Ξ , U ′ , C C D S D ′ ) ≤ ε p a r a m ( f Ξ , U , C C D S D ) + C C C D S ∥ G ′ − G ∥ 2 . \varepsilon_{\mathrm{param}}(f_{\Xi},U',\mathrm{CCDS}_{D'}) \le\varepsilon_{\mathrm{param}}(f_{\Xi},U,\mathrm{CCDS}_{D}) + C_{\mathrm{CCDS}}\lVert G' - G\rVert_2. ε param ( f Ξ , U ′ , CCDS D ′ ) ≤ ε param ( f Ξ , U , CCDS D ) + C CCDS ∥ G ′ − G ∥ 2 . Thus, the projection bottleneck is invariant under relaxed interpolation and the constructive CCDS bottleneck is locally Lipschitz stable.
Proof sketch. Set η = ∥ G ′ − G ∥ 2 \eta= \lVert G' - G\rVert_2 η = ∥ G ′ − G ∥ 2 . Since J k ′ = Y k R k ′ J'_k = Y_kR'_k J k ′ = Y k R k ′ , the scaffold identity gives U ′ ⊆ U U' \subseteq U U ′ ⊆ U . For η < γ / 2 \eta< \gamma/2 η < γ /2 , Weyl’s inequality yields
σ r ( G ′ ) ≥ γ − η > 0 , \sigma_r(G') \ge\gamma- \eta> 0, σ r ( G ′ ) ≥ γ − η > 0 ,
so U ′ = U U' = U U ′ = U and the projection errors coincide. Transport the same atom labels, deviations, and root branches. The positive innovation norms preserve the normalization steps, while the positive feasibility margins keep the square-root arguments away from zero. Consequently, the innovation directions and coefficient updates vary locally Lipschitz continuously. Induction along each finite path gives
∥ r t ′ − r t ∥ ≤ C t η . \lVert r'_t-r_t\rVert\le C_t\eta. ∥ r t ′ − r t ∥ ≤ C t η .
Taking a common constant over the finitely many training paths and averaging the terminal residual bounds proves the stated parametrization-error estimate.
Our framework in practice.
The preceding theory isolates the projection and parametrization bottlenecks and provides constructive mechanisms for controlling them. In practice, however, scaffold construction begins one step earlier: from the anchor subset Ξ s u b \Xi_{\mathrm{sub}} Ξ sub , one must choose a partition, orbit depths, and a wrapped shift W W W that generate a suitable candidate orbit geometry. In Subsection 3.3 we derived observable quantities such as S ( P ) S(\mathcal{P}) S ( P ) guiding this preliminary selection. Now we describe another criterion and then summarize how they enter the two realizability phases.
Vanishing-cycle criterion. A second, independent criterion concerns the repeated orbit dynamics of W W W . Set ρ : = ∏ i = 0 d − 1 w i \rho:= \prod_{i=0}^{d-1} w_i ρ := ∏ i = 0 d − 1 w i . If ∣ ρ ∣ < 1 |\rho| < 1 ∣ ρ ∣ < 1 , then repeated full cycles decay geometrically. Indeed, if m = q d + r m = qd + r m = q d + r with 0 ≤ r < d 0 \le r < d 0 ≤ r < d , Lemma 3.3 gives W m = ρ q W r W^m = \rho^q W^r W m = ρ q W r and hence
∥ W m z ∥ ≤ ∣ ρ ∣ ⌊ m / d ⌋ C z , C z : = max 0 ≤ r ≤ d − 1 ∥ W r z ∥ . (16) \lVert W^m z\rVert\le|\rho|^{\lfloor m/d\rfloor} C_z,\qquad C_z := \max_{0\le r\le d-1}\lVert W^r z\rVert. \tag*{(16)} ∥ W m z ∥ ≤ ∣ ρ ∣ ⌊ m / d ⌋ C z , C z := 0 ≤ r ≤ d − 1 max ∥ W r z ∥ . (16)
Thus, if an input perturbation η \eta η is propagated through the orbit, ∥ W m η ∥ ≤ ∣ ρ ∣ ⌊ m / d ⌋ C η \lVert W^m\eta\rVert\le|\rho|^{\lfloor m/d\rfloor}C_\eta ∥ W m η ∥ ≤ ∣ ρ ∣ ⌊ m / d ⌋ C η ; hence ∣ ρ ∣ < 1 |\rho| < 1 ∣ ρ ∣ < 1 acts as an implicit noise regularizer by geometrically damping perturbations propagated through repeated orbit cycles, without changing the formal scaffold generated by the d d d residue-class depths. This is the main reason we favor vanishing shifts in scaffold discovery.
The practical pipeline retains the same structural decomposition developed above. Phase 1 addresses the projection bottleneck by constructing and selecting an orbit scaffold, Phase 2 addresses the parametrization bottleneck by constructively realizing the projected targets on the selected scaffold, and Phase 3 extends the resulting CCDS coefficient certificates to unseen inputs. Let Ξ s u b ⊆ Ξ t r a i n \Xi_{\mathrm{sub}} \subseteq\Xi_{\mathrm{train}} Ξ sub ⊆ Ξ train , where Ξ s u b \Xi_{\mathrm{sub}} Ξ sub is the anchor subset used to construct the orbit scaffold.
Phase 1: scaffold discovery and selection. Phase 1 searches over a finite collection of candidate anchor configurations
ϑ = ( Ξ s u b , P , W ) , \vartheta= (\Xi_{\mathrm{sub}},\mathcal{P},W), ϑ = ( Ξ sub , P , W ) ,
where Ξ s u b \Xi_{\mathrm{sub}} Ξ sub is an anchor subset, P \mathcal{P} P is a partition of the anchors, and W W W is a wrapped weighted shift. For each candidate, orbit-independence tests select admissible depths L k , j L_{k,j} L k , j , and the corresponding block interpolants are computed as
J k = Y k Z k † , Z k = [ W L k , 1 x k , 1 ⋯ W L k , s k x k , s k ] . J_k = Y_k Z_k^{\dagger},\qquad Z_k = [W^{L_{k,1}}x_{k,1}\ \cdots\ W^{L_{k,s_k}}x_{k,s_k}]. J k = Y k Z k † , Z k = [ W L k , 1 x k , 1 ⋯ W L k , s k x k , s k ] .
The candidate orbit dictionary and associated orbit scaffold are then
D ϑ = { J k W m x k , j : 1 ≤ k ≤ K , 1 ≤ j ≤ s k , 0 ≤ m ≤ d − 1 } , U ϑ : = span D ϑ . (17) \mathcal{D}_{\vartheta} = \{J_kW^m x_{k,j}: 1 \le k \le K,\ 1 \le j \le s_k,\ 0 \le m \le d-1\},\qquad U_{\vartheta} := \operatorname{span}\mathcal{D}_{\vartheta}. \tag*{(17)} D ϑ = { J k W m x k , j : 1 ≤ k ≤ K , 1 ≤ j ≤ s k , 0 ≤ m ≤ d − 1 } , U ϑ := span D ϑ . (17)
The code first constructs several disjoint farthest-first anchor candidates. For each one, it forms a greedy orbit-admissible partition, refines the partition until the prescribed block-size condition is reached, computes the local-chart score S ( P ) S(\mathcal{P}) S ( P ) , and constructs the corresponding block interpolants. A wrapped shift is then fitted or constrained in the vanishing-cycle regime, and the full candidate orbit dictionary D ϑ \mathcal{D}_{\vartheta} D ϑ is assembled.
To evaluate the projection quality of a candidate, the code computes an orthonormal SVD chain inside U ϑ = span D ϑ U_{\vartheta}=\operatorname{span}\mathcal{D}_{\vartheta} U ϑ = span D ϑ . This chain provides a basis for a nested sequence of projection spaces and a numerical diagnostic of the residual decay. It is not itself the dictionary used for synthesis. The candidate configuration is retained according to the smallest projection diagnostic among the evaluated candidates, with early termination when the prescribed tolerance is reached. The output of Phase 1 is therefore the selected configuration
ϑ ⋆ = ( Ξ s u b ⋆ , P ⋆ , W ⋆ ) , \vartheta^\star=(\Xi^\star_{\mathrm{sub}},\mathcal{P}^\star,W^\star), ϑ ⋆ = ( Ξ sub ⋆ , P ⋆ , W ⋆ ) ,
together with the orbit dictionary D ϑ ⋆ \mathcal{D}_{\vartheta^\star} D ϑ ⋆ and its full span
U ϑ ⋆ = span D ϑ ⋆ . U_{\vartheta^\star}=\operatorname{span}\mathcal{D}_{\vartheta^\star}. U ϑ ⋆ = span D ϑ ⋆ .
Phase 2: CCDS realization.. Once the scaffold has been selected, Phase 2 addresses the parametrization bottleneck by realizing each projected training target using the fixed orbit dictionary D ϑ ⋆ \mathcal{D}_{\vartheta^\star} D ϑ ⋆ defined in (4) . For each ( x i , y i ) ∈ Ξ t r a i n (x_i,y_i)\in\Xi_{\mathrm{train}} ( x i , y i ) ∈ Ξ train , define its coefficient certificate and realized target by
β i : = β D ϑ ⋆ ( y i ) , c i : = S D ϑ ⋆ ( β i ) = CCDS D ϑ ⋆ ( y i ) ∈ U . (18) \beta_i:=\beta_{\mathcal{D}_{\vartheta^\star}}(y_i),\qquad c_i:=S_{\mathcal{D}_{\vartheta^\star}}(\beta_i)=\operatorname{CCDS}_{\mathcal{D}_{\vartheta^\star}}(y_i)\in U. \tag*{(18)} β i := β D ϑ ⋆ ( y i ) , c i := S D ϑ ⋆ ( β i ) = CCDS D ϑ ⋆ ( y i ) ∈ U . (18)
Once D ϑ ⋆ \mathcal{D}_{\vartheta^\star} D ϑ ⋆ and the CCDS rule have been fixed, the construction in (18) depends on the target y i y_i y i alone. The input x i x_i x i records the location in input space at which this certificate is observed. Thus Phase 2 produces the coefficient-labeled cloud
C t r a i n : = { ( x i , β i , c i ) } i = 1 n , \mathcal{C}_{\mathrm{train}}:=\{(x_i,\beta_i,c_i)\}_{i=1}^{n}, C train := {( x i , β i , c i ) } i = 1 n ,
and Phase 3 extends this finite collection to unseen inputs.
Phases 1 and 2 have now identified a scaffold, shown that its projected target is constructively and sparsely realizable on each training target, and established that this mechanism survives the relaxed interpolation used in practice.
Phase 3: Prediction from CCDS certificates.. Phase 3 extend Phases 1-2 realizations to unseen inputs. Phase 3 coefficient extension map is defined by
E ϑ ⋆ ( ⋅ ; C t r a i n ) : R d ⟶ R P , C t r a i n = { ( x i , β i , c i ) } i = 1 n , \mathcal{E}_{\vartheta^\star}(\,\cdot\,;\mathcal{C}_{\mathrm{train}}):\mathbb{R}^{d}\longrightarrow\mathbb{R}^{P},\qquad\mathcal{C}_{\mathrm{train}}=\{(x_i,\beta_i,c_i)\}_{i=1}^{n}, E ϑ ⋆ ( ⋅ ; C train ) : R d ⟶ R P , C train = {( x i , β i , c i ) } i = 1 n ,
fitted from the training data. The associated predictor is
f ~ ϑ ⋆ ( x ) = S D ϑ ⋆ ( E ϑ ⋆ ( x ; C t r a i n ) ) . (19) \widetilde{f}_{\vartheta^\star}(x)=S_{\mathcal{D}_{\vartheta^\star}}\bigl(\mathcal{E}_{\vartheta^\star}(x;\mathcal{C}_{\mathrm{train}})\bigr). \tag*{(19)} f ϑ ⋆ ( x ) = S D ϑ ⋆ ( E ϑ ⋆ ( x ; C train ) ) . (19)
Definition 3.12 (Weighted Backward Shift Neural Network). A Weighted Backward Shift Neural Network (W B S N N WBSNN W B S N N ) associated with Ξ t r a i n \Xi_{\mathrm{train}} Ξ train is the predictor f ~ \widetilde{f} f of (19) produced by the three-phase construction of this paper.
In the predictive experiments, E ϑ ⋆ ( x ; C t r a i n ) = α θ ( x ) \mathcal{E}_{\vartheta^\star}(x;\mathcal{C}_{\mathrm{train}})=\alpha_{\theta}(x) E ϑ ⋆ ( x ; C train ) = α θ ( x ) is a learned coefficient head. Writing g θ = S D ∘ α θ g_{\theta}=S_{\mathcal{D}}\circ\alpha_{\theta} g θ = S D ∘ α θ , it may be trained with
L 3 ( θ ) = 1 n ∑ i = 1 n [ ℓ p r e d ( g θ ( x i ) , y i ) + λ C C D S ∥ g θ ( x i ) − c i ∥ 2 2 + λ c o e f f ∥ α θ ( x i ) − β i ∥ 2 2 + λ 1 ∥ α θ ( x i ) ∥ 1 ] , \mathcal{L}_3(\theta)=\frac{1}{n}\sum_{i=1}^{n}\left[\ell_{\mathrm{pred}}\bigl(g_{\theta}(x_i),y_i\bigr)+\lambda_{\mathrm{CCDS}}\lVert g_{\theta}(x_i)-c_i\rVert_2^2+\lambda_{\mathrm{coeff}}\lVert\alpha_{\theta}(x_i)-\beta_i\rVert_2^2+\lambda_1\lVert\alpha_{\theta}(x_i)\rVert_1\right], L 3 ( θ ) = n 1 i = 1 ∑ n [ ℓ pred ( g θ ( x i ) , y i ) + λ CCDS ∥ g θ ( x i ) − c i ∥ 2 2 + λ coeff ∥ α θ ( x i ) − β i ∥ 2 2 + λ 1 ∥ α θ ( x i ) ∥ 1 ] ,
where the nonnegative weights specify which forms of constructive supervision are used.
The distinction between realization and prediction is visible without imposing a particular extension rule. For any test pair ( x , y ) (x, y) ( x , y ) and any training index i i i ,
y − f ~ ϑ ⋆ ( x ) = ( y − Π U ϑ ⋆ y ) + Π U ϑ ⋆ ( y − y i ) + ( Π U ϑ ⋆ y i − c i ) + ( c i − f ~ ϑ ⋆ ( x i ) ) + ( f ~ ϑ ⋆ ( x i ) − f ~ ϑ ⋆ ( x ) ) . y - \widetilde{f}_{\vartheta^\star}(x) = (y - \Pi_{U_{\vartheta^\star}} y) + \Pi_{U_{\vartheta^\star}}(y - y_i) + (\Pi_{U_{\vartheta^\star}} y_i - c_i)
+ (c_i - \widetilde{f}_{\vartheta^\star}(x_i)) + (\widetilde{f}_{\vartheta^\star}(x_i) - \widetilde{f}_{\vartheta^\star}(x)). y − f ϑ ⋆ ( x ) = ( y − Π U ϑ ⋆ y ) + Π U ϑ ⋆ ( y − y i ) + ( Π U ϑ ⋆ y i − c i ) + ( c i − f ϑ ⋆ ( x i )) + ( f ϑ ⋆ ( x i ) − f ϑ ⋆ ( x )) .
The five terms expose scaffold projection, target transfer, CCDS realization, training prediction, and predictor variation.
Experiments
We evaluate three separate questions: whether a reduced scaffold captures target energy, whether CCDS realizes a projected target with controlled deviations, and whether a learned extension predicts unseen inputs. We then examine dictionary structure, relaxed interpolation, and discovery budget. Reported uncertainties are sample standard deviations across the stated seeds. Configuration details and the recorded implementation conventions appear in Appendix B.
The experiments are designed as mechanism tests rather than as an unconstrained benchmark contest. All matched baselines operate on the same compressed features and training information, while the orbit scaffold is constructed from only a small discovery subset. This separates the contributions of scaffold geometry, constructive realization, and coefficient prediction, and tests whether the proposed structure provides useful data and representation leverage under controlled computational conditions.
Scaffold geometry and controlled realization
Target energy at matched rank. On a synthetic linear-response problem, we compare spectral selection within the candidate orbit span with random orbit-atom selection and Gaussian subspaces of the same rank. Across ten anchor seeds, each random reference averages twenty draws per rank. Table 4.1 shows that two selected directions capture 99.05% of target energy, compared with 34.74% for random orbit selection and 28.35% for Gaussian subspaces. Across ranks one through six, the selected scaffold has lower projection error than the random orbit reference in 57/60 seed–rank comparisons and than the Gaussian reference in all sixty. This experiment evaluates the maximal-drop spectral endpoint of the scaffold-selection principle; it does not test an interior prescribed energy profile.
Table 4.1. Mean Euclidean projection error at matched rank, averaged over ten anchor seeds. Spectral selection and random orbit selection are restricted to the same candidate orbit span; Gaussian subspaces are sampled in the ambient output space.
Because the compared subspaces have matched rank, and the orbit alternatives are restricted to the same candidate span, this result isolates the effect of data-adaptive scaffold selection. The gain cannot be attributed merely to a larger subspace or a more favorable ambient dimension: the selected orbit directions capture the target geometry substantially more effectively than either random orbit choices or unstructured Gaussian directions. Figure 4.1 shows the selected scaffold’s lower mean projection error across all six ranks.
Figure 4.1. Matched-rank scaffold quality. Mean projection error across scaffold ranks for the selected orbit, random orbit, and Gaussian constructions. Error bars show the reported standard deviations.
The OMP boundary and interior paths. A weak-alignment stress test uses 500 inputs, a 350-atom dictionary, and a seven-step nested realization. At the minimal-deviation boundary, CCDS and OMP on the same dictionary have mean realization errors 7.31 × 10 − 8 7.31 \times10^{-8} 7.31 × 1 0 − 8 and 7.35 × 10 − 8 7.35 \times10^{-8} 7.35 × 1 0 − 8 , respectively; their outputs differ by 9.62 × 10 − 8 9.62 \times10^{-8} 9.62 × 1 0 − 8 on average. Interior schedules remain feasible for all 500 inputs, while exposing the distinction between prescribed deviation and terminal error (Table 4.2). With γ = 0.5 \gamma= 0.5 γ = 0.5 , 96.8% of inputs encounter an interior step; with γ = 0.9 \gamma= 0.9 γ = 0.9 , all do. The larger terminal errors reflect coordinate discrepancies retained from earlier innovations, as predicted by the residual identity in Remark 3.7. Thus interior control supplies additional path freedom, rather than an automatic improvement in endpoint accuracy.
This comparison establishes the intended separation between endpoint realization and path control. At the minimal-deviation boundary, CCDS reproduces the residual-minimizing behavior associated with the selected nested span. Interior schedules remain feasible while deliberately retaining controlled coordinate discrepancies, thereby providing a path-level degree of freedom unavailable at the boundary. In the nested orthogonal setting, OMP is confined to the minimal-deviation boundary: its least-squares refit selects λ t = α t \lambda_t = \alpha_t λ t = α t and therefore cannot realize a prescribed interior deviation d t > d t , min d_t > d_{t,\min} d t > d t , m i n . Thus the interior CCDS trajectories are genuinely inaccessible to OMP on the same dictionary, rather than merely alternative OMP choices.
Interior realization across operator families. We next hold a randomly constructed 900-atom dictionary fixed and evaluate eight linear operator families on 2,000 inputs each. A six-step CCDS schedule allocates a relative terminal error budget of 10 − 3 10^{-3} 1 0 − 3 . All 16,000 paths complete
caption: Nested CCDS on the weak-alignment problem. The dictionary, target responses, and seven-step horizon are fixed; the interior schedule changes.
:::
without a reported numerical failure. Depending on the family, 57.10%–70.65% of inputs encounter an interior step, with mean realization errors between 1.51 × 10 − 4 1.51 \times10^{-4} 1.51 × 1 0 − 4 and 7.71 × 10 − 4 7.71 \times10^{-4} 7.71 × 1 0 − 4 and mean supports between 5.99 and 6.00. The separate trivial-reference solver also realizes these targets, with errors between 2.40 × 10 − 8 2.40 \times10^{-8} 2.40 × 1 0 − 8 and 1.06 × 10 − 7 1.06 \times10^{-7} 1.06 × 1 0 − 7 . These results demonstrate feasible sparse interior paths across different response geometries; the low frequency of the logged MP-branch certificate does not establish failure of MP or OMP.
The fact that the same sparse construction remains feasible across substantially different operator geometries is important: the observed behavior is not tied to one favorable response map. The experiment supports CCDS as a geometry-aware realization mechanism whose interior certificates remain usable even when the available dictionary does not provide a uniformly dominant greedy direction.
Prediction from constructive certificates
The main predictive runs use global coefficient heads on Gas Sensor Drift, ISOLET, and MNIST, with five runs per setting. The tabular baselines receive the same feature representation and training subset. Table 4.3 reports held-out accuracy; the MNIST holdout is the final 12,000 examples of the official training pool, rather than the official test set.
Table 4.3. Held-out accuracy (%), mean ± \pm ± standard deviation over five runs. The number after each dataset is the feature dimension; Gas at 128 uses raw features, and the remaining settings use PCA. LR, RF, and GBT denote logistic regression, random forest, and gradient boosted trees. The MLP matches the coefficient head’s hidden widths and depth, but differs in activations, normalization, regularization, and output dimension.
WBSNN has the highest mean accuracy among these feature-based baselines in both Gas settings and both MNIST settings. On Gas with 25 features, its advantage over logistic regression is 10.58 percentage points. On MNIST, it exceeds RBF SVM by 0.91 and 1.77 points at 25 and 100 features. On ISOLET, its accuracy remains within 0.46 and 0.59 points of RBF SVM. Raw-image CNN references reach 97.29 ± 0.18 % 97.29 \pm0.18\% 97.29 ± 0.18% and 97.86 ± 0.44 % 97.86 \pm0.44\% 97.86 ± 0.44% on the two MNIST training budgets; their access to image structure distinguishes them from the PCA-feature comparison. Additional Gas and ISOLET references are reported in the appendix.
The main predictive result is therefore structural rather than merely numerical. WBSNN remains competitive, and often superior, while operating on the same compressed representation as the baselines and using a scaffold discovered from only a small fraction of the training data. On the more difficult speech task, the method remains close to the strongest kernel baseline rather than relying on a large unconstrained predictor.
Across the six settings, the mean projection errors are at most 3.42 × 10 − 9 3.42 \times10^{-9} 3.42 × 1 0 − 9 , and mean realization errors are at most 8.74 × 10 − 8 8.74 \times10^{-8} 8.74 × 1 0 − 8 , using only 1.52–3.19 atoms per training certificate on average. These sparse certificates concern Phase 2, not the support of the learned predictive head. The small projection errors therefore verify numerical consistency, whereas prediction and the structured-dictionary comparison below provide the substantive empirical tests.
These diagnostics show that the learned predictor is not compensating for a failed Phase 1 or Phase 2 construction. The orbit scaffold captures the target geometry, CCDS realizes the projected targets with negligible residual, and the remaining predictive difficulty lies in extending the resulting sparse coefficient law to unseen inputs.
Dictionary and interpolation comparisons
Orbit structure under a matched dictionary span. On a waveform regression task, we replace the orbit dictionary with random directions in its numerical span while preserving atom count, atom norms, and the selected-depth anchor atoms. Both arms share the training data, shift, block interpolant, proxy-network architecture, and a two-atom greedy readout. Across ten paired seeds, the orbit dictionary reduces test MSE by 89.44 ± \pm ± 8.25% with 20 anchors and 87.52 ± \pm ± 10.16% with 28 anchors (Table 4.4 ). Because the full span is matched, this difference isolates the utility of dictionary geometry for sparse approximation in this task. The orbit variant approaches the direct MLP’s mean MSE, while the unstructured variant remains substantially worse. This is a proxy-prediction experiment with an MP readout, rather than the global coefficient-head architecture used in Table 4.3 .
Table 4.4. Waveform test MSE multiplied by 10 3 10^{3} 1 0 3 , mean ± \pm ± standard deviation over ten seeds. The dictionaries contain 640 and 896 atoms, respectively. The direct MLP is trained once per seed and reused across anchor budgets.
This is the most direct test that orbit geometry itself matters. The two dictionaries have the same numerical span, comparable atom norms and counts, and the same selected anchor directions; only their internal geometry differs. The resulting performance gap therefore cannot be explained by span dimension or dictionary size, and instead isolates the benefit of the orbit-induced organization for sparse approximation.
Exact and relaxed construction under label noise. On a synthetic binary classification task, we corrupt only the training labels and retain clean test labels. Table 4.5 compares the two construction variants over five paired seeds. Their mean accuracies differ by at most 0.07 points at 0% and 20% corruption. At 40%, the relaxed variant has a 1.77-point higher mean, although variability is larger in both arms. All thirty runs retain projection and realization errors below 1.79 × 10 − 8 1.79 \times10^{-8} 1.79 × 1 0 − 8 and 8.53 × 10 − 8 8.53 \times10^{-8} 8.53 × 1 0 − 8 , respectively. Within each noise level and seed, the exact and relaxed interpolants use the same discovered partition, dictionary, and CCDS path. Their comparison therefore matches the fixed-block, fixed-path perturbation setting of Theorem 3.11 ; the construction is rerun only across independent seeds and noise levels.
Table 4.5. Clean-test accuracy (%), mean ± \pm ± standard deviation over five paired seeds. The same corrupted training labels are used in both arms.
The two constructions have nearly identical clean-test accuracies at 0% and 20% label corruption and remain broadly comparable at 40%, where the relaxed variant has the higher mean. Across these tested settings, exact and relaxed constructions are comparably effective for prediction, so the choice between them can be guided by the application and numerical conditioning. Moreover, both constructions retain negligible projection and realization errors, while regularization offers the conditioning advantages expected under noisy supervision. These findings directly support the stability claim of Theorem 3.11 .
Exploratory discovery-budget sweeps. Single-seed sweeps reach 68.62% on Gas at a 3% anchor budget and 93.56% on MNIST at 7%. Across all tested budgets, projection and realization errors remain below 3.31 × 10 − 10 3.31 \times10^{-10} 3.31 × 1 0 − 10 and 6.98 × 10 − 8 6.98 \times10^{-8} 6.98 × 1 0 − 8 . Thus numerical realizability is already achieved at the smallest budget, while predictive accuracy initially improves before leveling off or declining at larger budgets. Table 4.6 reports the complete accuracy trajectories and corresponding anchor counts.
Table 4.6. Single-seed configuration sweeps. Atom counts equal anchor count times PCA dimension. Optimization settings also vary with budget, as specified below.
The resulting saturation pattern supports a data-efficient discovery principle: once the scaffold has captured the relevant target geometry, additional anchors do not automatically improve prediction. The limiting factor then moves from scaffold construction and realization to the learned extension of the coefficient map.
Proofs
Wrapped weighted backward shifts
To prove Lemma 3.2 , we first establish its action on the canonical basis.
Lemma A.1. For every m ≥ 1 m \ge1 m ≥ 1 , W m e j = ( ∏ s = 0 m − 1 w j − s ( m o d d ) ) e j − m ( m o d d ) W^{m}e_j = \left(\prod_{s=0}^{m-1} w_{j-s\ (\mathrm{mod}\ d)}\right)e_{j-m\ (\mathrm{mod}\ d)} W m e j = ( ∏ s = 0 m − 1 w j − s ( mod d ) ) e j − m ( mod d ) .
Proof. Indeed, the claim follows by induction. For r = 1 r=1 r = 1 , it is the definition. Assuming it for r r r ,
W r + 1 e j = W [ ( ∏ s = 0 r − 1 w j − s ) e j − r ] = ( ∏ s = 0 r − 1 w j − s ) w j − r e j − r − 1 = ( ∏ s = 0 r w j − s ) e j − r − 1 . W^{r+1}e_j = W\left[\left(\prod_{s=0}^{r-1}w_{j-s}\right)e_{j-r}\right] = \left(\prod_{s=0}^{r-1}w_{j-s}\right)w_{j-r}e_{j-r-1} = \left(\prod_{s=0}^{r}w_{j-s}\right)e_{j-r-1}. W r + 1 e j = W [ ( s = 0 ∏ r − 1 w j − s ) e j − r ] = ( s = 0 ∏ r − 1 w j − s ) w j − r e j − r − 1 = ( s = 0 ∏ r w j − s ) e j − r − 1 .
where all indices are taken modulo d d d . ■ \blacksquare ■
Proof of Lemma 3.2 . Write z = ∑ q = 0 d − 1 z q e q z = \sum_{q=0}^{d-1} z_qe_q z = ∑ q = 0 d − 1 z q e q . By Lemma A.1,
W m z = ∑ q = 0 d − 1 z q ( ∏ s = 0 m − 1 w q − s ( m o d d ) ) e q − m ( m o d d ) . W^{m}z = \sum_{q=0}^{d-1}z_q\left(\prod_{s=0}^{m-1}w_{q-s\ (\mathrm{mod}\ d)}\right)e_{q-m\ (\mathrm{mod}\ d)}. W m z = q = 0 ∑ d − 1 z q ( s = 0 ∏ m − 1 w q − s ( mod d ) ) e q − m ( mod d ) .
The coefficient of e i − 1 e_{i-1} e i − 1 is obtained for q = i + m − 1 ( m o d d ) q = i+m-1\ (\mathrm{mod}\ d) q = i + m − 1 ( mod d ) . Therefore
( W m z ) i − 1 = z ( i + m − 1 ) m o d d ∏ s = 0 m − 1 w i + m − 1 − s ( m o d d ) . \left(W^{m}z\right)_{i-1} = z_{(i+m-1)\ \mathrm{mod}\ d}\prod_{s=0}^{m-1}w_{i+m-1-s\ (\mathrm{mod}\ d)}. ( W m z ) i − 1 = z ( i + m − 1 ) mod d s = 0 ∏ m − 1 w i + m − 1 − s ( mod d ) .
Reindexing with r = m − 1 − s r=m-1-s r = m − 1 − s gives
( W m z ) i − 1 = ( ∏ r = 0 m − 1 w ( i + r ) m o d d ) z ( i + m − 1 ) m o d d , i = 1 , … , d . \left(W^{m}z\right)_{i-1} = \left(\prod_{r=0}^{m-1}w_{(i+r)\ \mathrm{mod}\ d}\right)z_{(i+m-1)\ \mathrm{mod}\ d},\qquad i=1,\ldots,d. ( W m z ) i − 1 = ( r = 0 ∏ m − 1 w ( i + r ) mod d ) z ( i + m − 1 ) mod d , i = 1 , … , d .
For m = 0 m=0 m = 0 , this reduces to W 0 = I W^0=I W 0 = I . ■ \blacksquare ■
Exact interpolation Theorem in infinite dimensions
Thanks to Hahn–Banach Theorem, we show that for infinite dimensional Banach spaces, under a technical independence condition, any finite dataset admits an exact realization within a class of transformed weighted shifts. We now present and prove an explicit construction of such a realization.
Theorem A.2 (Exact interpolation in infinite dimensional Banach spaces). Let X X X and Y Y Y be infinite-dimensional Banach spaces. Let T : X → X T:X\to X T : X → X be a bounded linear operator and let { ( x i , y i ) } i = 1 n 0 ⊂ X × Y \{(x_i,y_i)\}_{i=1}^{n_0}\subset X\times Y {( x i , y i ) } i = 1 n 0 ⊂ X × Y be a finite input–target set. Suppose that for each i = 1 , … , n 0 i=1,\ldots,n_0 i = 1 , … , n 0 there exists a nonnegative integer L i L_i L i such that
z 1 : = T L 1 x 1 ≠ 0 , z i : = T L i x i ∉ span { z 1 , … , z i − 1 } , i = 2 , … , n 0 . (20) z_1 := T^{L_1}x_1 \ne0,\qquad z_i := T^{L_i}x_i \notin\operatorname{span}\{z_1,\ldots,z_{i-1}\},\qquad i=2,\ldots,n_0. \tag*{(20)} z 1 := T L 1 x 1 = 0 , z i := T L i x i ∈ / span { z 1 , … , z i − 1 } , i = 2 , … , n 0 . (20) Then there exists a bounded linear operator J : X → Y J:X\to Y J : X → Y such that J T L i x i = y i , i = 1 , … , n 0 JT^{L_i}x_i=y_i,\ i=1,\ldots,n_0 J T L i x i = y i , i = 1 , … , n 0 .
Proof. We construct J J J recursively. Let J 0 : = 0 ∈ L ( X , Y ) J_0:=0\in\mathcal{L}(X,Y) J 0 := 0 ∈ L ( X , Y ) . For i = 1 i=1 i = 1 , pick any L 1 ≥ 0 L_1\ge0 L 1 ≥ 0 , set z 1 : = T L 1 x 1 z_1:=T^{L_1}x_1 z 1 := T L 1 x 1 and find a linear functional f 1 ∈ X ∗ f_1\in X^* f 1 ∈ X ∗ with f 1 ( z 1 ) = 1 f_1(z_1)=1 f 1 ( z 1 ) = 1 . Define J 1 : = J_1:= J 1 := J 0 + ( y 1 − J 0 z 1 ) ⊗ f 1 J_0+(y_1-J_0z_1)\otimes f_1 J 0 + ( y 1 − J 0 z 1 ) ⊗ f 1 , where ( y ⊗ f ) ( v ) : = f ( v ) y (y\otimes f)(v):=f(v)y ( y ⊗ f ) ( v ) := f ( v ) y . Equivalently, for all v ∈ X v\in X v ∈ X we have J 1 v : = J 0 v + ( y 1 − J 0 z 1 ) ⊗ f 1 ( v ) = 0 + ( y 1 − 0 ) ⊗ f 1 ( v ) = f 1 ( v ) y 1 J_1v:=J_0v+(y_1-J_0z_1)\otimes f_1(v)=0+(y_1-0)\otimes f_1(v)=f_1(v)y_1 J 1 v := J 0 v + ( y 1 − J 0 z 1 ) ⊗ f 1 ( v ) = 0 + ( y 1 − 0 ) ⊗ f 1 ( v ) = f 1 ( v ) y 1 . Thus, J 1 ∈ L ( X , Y ) J_1\in\mathcal{L}(X,Y) J 1 ∈ L ( X , Y ) and J 1 z 1 = 1 ⋅ y 1 = y 1 J_1z_1=1\cdot y_1=y_1 J 1 z 1 = 1 ⋅ y 1 = y 1 .
Set z i : = T L i x i z_i:=T^{L_i}x_i z i := T L i x i , for i ≥ 2 i\ge2 i ≥ 2 satisfying (A.1). Suppose that for some i ≥ 2 i\ge2 i ≥ 2 , the operator J i − 1 ∈ L ( X , Y ) J_{i-1}\in\mathcal{L}(X,Y) J i − 1 ∈ L ( X , Y ) has already been constructed so that
J i − 1 z j = y j , j = 1 , … , i − 1. J_{i-1}z_j=y_j,\qquad j=1,\ldots,i-1. J i − 1 z j = y j , j = 1 , … , i − 1.
By (A.1), we have z i ∉ span { z 1 , … , z i − 1 } z_i\notin\operatorname{span}\{z_1,\ldots,z_{i-1}\} z i ∈ / span { z 1 , … , z i − 1 } . Let M i : = span { z 1 , … , z i − 1 , z i } M_i:=\operatorname{span}\{z_1,\ldots,z_{i-1},z_i\} M i := span { z 1 , … , z i − 1 , z i } . Define a linear functional g i : M i → R g_i:M_i\to\mathbb{R} g i : M i → R by g i ( z j ) = 0 g_i(z_j)=0 g i ( z j ) = 0 , j = 1 , … , i − 1 j=1,\ldots,i-1 j = 1 , … , i − 1 , g i ( z i ) = 1 g_i(z_i)=1 g i ( z i ) = 1 , and extending linearly on M i M_i M i . This is well-defined because z i ∉ span { z 1 , … , z i − 1 } z_i\notin\operatorname{span}\{z_1,\ldots,z_{i-1}\} z i ∈ / span { z 1 , … , z i − 1 } . Since M i M_i M i is finite-dimensional, g i g_i g i is continuous. By the Hahn–Banach Theorem [7 Corollary 3.15, p.112] , there exists a bounded linear functional f i ∈ X ∗ f_i\in X^* f i ∈ X ∗ extending g i g_i g i , hence f i ( z j ) = 0 f_i(z_j)=0 f i ( z j ) = 0 , j < i j<i j < i , f i ( z i ) = 1 f_i(z_i)=1 f i ( z i ) = 1 . Define
J i v : = J i − 1 v + f i ( v ) ( y i − J i − 1 z i ) , v ∈ X . J_iv:=J_{i-1}v+f_i(v)(y_i-J_{i-1}z_i),\qquad v\in X. J i v := J i − 1 v + f i ( v ) ( y i − J i − 1 z i ) , v ∈ X .
Equivalently, J i = J i − 1 + ( y i − J i − 1 z i ) ⊗ f i J_i=J_{i-1}+(y_i-J_{i-1}z_i)\otimes f_i J i = J i − 1 + ( y i − J i − 1 z i ) ⊗ f i . Since J i − 1 J_{i-1} J i − 1 and f i f_i f i are bounded, J i ∈ L ( X , Y ) J_i\in\mathcal{L}(X,Y) J i ∈ L ( X , Y ) .
Now, J i z i = J i − 1 z i + f i ( z i ) ( y i − J i − 1 z i ) = J i − 1 z i + ( y i − J i − 1 z i ) = y i J_iz_i=J_{i-1}z_i+f_i(z_i)(y_i-J_{i-1}z_i)=J_{i-1}z_i+(y_i-J_{i-1}z_i)=y_i J i z i = J i − 1 z i + f i ( z i ) ( y i − J i − 1 z i ) = J i − 1 z i + ( y i − J i − 1 z i ) = y i . For j < i j<i j < i , we have f i ( z j ) = 0 f_i(z_j)=0 f i ( z j ) = 0 , so J i z j = J i − 1 z j + f i ( z j ) ( y i − J i − 1 z i ) = J i − 1 z j = y j J_iz_j=J_{i-1}z_j+f_i(z_j)(y_i-J_{i-1}z_i)=J_{i-1}z_j=y_j J i z j = J i − 1 z j + f i ( z j ) ( y i − J i − 1 z i ) = J i − 1 z j = y j . Thus J i z j = y j J_iz_j=y_j J i z j = y j for every j ≤ i j\le i j ≤ i . By induction, after n 0 n_0 n 0 steps, for 1 ≤ i ≤ n 0 1\le i\le n_0 1 ≤ i ≤ n 0 : J i z j = y j J_iz_j=y_j J i z j = y j for j ≤ i j\le i j ≤ i . Finally, by setting J : = J n 0 ∈ L ( X , Y ) J:=J_{n_0}\in\mathcal{L}(X,Y) J := J n 0 ∈ L ( X , Y ) we have J z i = J T L i x i = y i Jz_i=JT^{L_i}x_i=y_i J z i = J T L i x i = y i , i = 1 , … , n 0 i=1,\ldots,n_0 i = 1 , … , n 0 .
Remark A.3 (Invertible interpolation when X = Y X=Y X = Y ). In the special case X = Y X=Y X = Y , the interpolation map may be chosen as an invertible perturbation of the identity. Indeed, if the recursive construction is initialized with J 0 = I X J_0=I_X J 0 = I X , then
J = I X + ∑ i = 1 N ( y i − J i − 1 T L i x i ) ⊗ f i . J=I_X+\sum_{i=1}^{N}(y_i-J_{i-1}T^{L_i}x_i)\otimes f_i. J = I X + i = 1 ∑ N ( y i − J i − 1 T L i x i ) ⊗ f i .
Hence, if
∑ i = 1 N ∥ y i − J i − 1 T L i x i ∥ ∥ f i ∥ < 1 (21) \sum_{i=1}^{N}\lVert y_i-J_{i-1}T^{L_i}x_i\rVert\lVert f_i\rVert<1 \tag*{(21)} i = 1 ∑ N ∥ y i − J i − 1 T L i x i ∥ ∥ f i ∥ < 1 (21)
then ∥ J − I X ∥ < 1 \lVert J-I_X\rVert<1 ∥ J − I X ∥ < 1 , so J J J is an isomorphism by the Neumann lemma [7 Lemma 2.1, p 192] . Thus, under the hypothesis of Theorem 3.4 and condition (A.2), when X = Y X=Y X = Y , exact interpolation can be realized by an isomorphism J = I X + F J=I_X+F J = I X + F , where F F F has finite rank.
Proof of Theorem 3.4 (Generic orbit independence). We first prove that Ω D \Omega_D Ω D is open and dense in Ω \Omega Ω .
For each depth tuple L = ( L 1 , … , L s ) ∈ { 0 , … , d − 1 } s L=(L_1,\ldots,L_s)\in\{0,\ldots,d-1\}^s L = ( L 1 , … , L s ) ∈ { 0 , … , d − 1 } s , define
M L ( w ) : = [ W w L 1 x 1 ⋯ W w L s x s ] . M_L(w):=[W_w^{L_1}x_1\ \cdots\ W_w^{L_s}x_s]. M L ( w ) := [ W w L 1 x 1 ⋯ W w L s x s ] .
Every entry of M L ( w ) M_L(w) M L ( w ) , and hence every s × s s\times s s × s minor of M L ( w ) M_L(w) M L ( w ) , is a polynomial in w w w . Define
Ω L : = { w ∈ Ω : rank M L ( w ) = s } . \Omega_L:=\{w\in\Omega:\operatorname{rank}M_L(w)=s\}. Ω L := { w ∈ Ω : rank M L ( w ) = s } .
By the definition of Ω D \Omega_D Ω D ,
Ω D = ⋃ L ∈ { 0 , … , d − 1 } s Ω L . \Omega_D = \bigcup_{L\in\{0,\ldots,d-1\}^{s}} \Omega_L. Ω D = L ∈ { 0 , … , d − 1 } s ⋃ Ω L .
Let M L \mathcal{M}_L M L denote the finite collection of all s × s s \times s s × s minors of M L ( w ) M_L(w) M L ( w ) . Then
Ω L = { w ∈ Ω : rank M L ( w ) = s } = ⋃ p ∈ M L { w ∈ Ω : p ( w ) ≠ 0 } . \Omega_L = \{w \in\Omega: \operatorname{rank} M_L(w) = s\} = \bigcup_{p\in\mathcal{M}_L} \{w \in\Omega: p(w) \ne0\}. Ω L = { w ∈ Ω : rank M L ( w ) = s } = p ∈ M L ⋃ { w ∈ Ω : p ( w ) = 0 } .
The union is finite and each set in the union is open (because p p p is a polynomial, then continuous and its nonvanishing set is open in Ω \Omega Ω ). Hence Ω L \Omega_L Ω L is open in Ω \Omega Ω . Since there are finitely many depth tuples, Ω D = ⋃ L Ω L \Omega_D = \bigcup_L \Omega_L Ω D = ⋃ L Ω L is open in Ω \Omega Ω .
To prove density, use the hypothesis Ω D ≠ ∅ \Omega_D \ne\varnothing Ω D = ∅ . Choose w 0 ∈ Ω D w_0 \in\Omega_D w 0 ∈ Ω D . By the finite-union representation above, there exists a depth tuple L ∗ L_* L ∗ such that rank M L ∗ ( w 0 ) = s \operatorname{rank} M_{L_*}(w_0) = s rank M L ∗ ( w 0 ) = s . Hence some s × s s \times s s × s minor p p p of M L ∗ M_{L_*} M L ∗ satisfies p ( w 0 ) ≠ 0 p(w_0) \ne0 p ( w 0 ) = 0 . Thus p p p is not the zero polynomial.
Since p p p is a nonzero polynomial on R d \mathbb{R}^d R d , its zero set Z ( p ) : = { w ∈ R d : p ( w ) = 0 } Z(p) := \{w \in\mathbb{R}^d : p(w) = 0\} Z ( p ) := { w ∈ R d : p ( w ) = 0 } has empty interior. Equivalently, the set { w ∈ R d : p ( w ) ≠ 0 } \{w \in\mathbb{R}^d : p(w) \ne0\} { w ∈ R d : p ( w ) = 0 } is dense in R d \mathbb{R}^d R d . Intersecting with Ω = ( R ∖ { 0 } ) d \Omega= (\mathbb{R} \setminus\{0\})^d Ω = ( R ∖ { 0 } ) d , which is open in R d \mathbb{R}^d R d , we conclude that { w ∈ Ω : p ( w ) ≠ 0 } \{w \in\Omega: p(w) \ne0\} { w ∈ Ω : p ( w ) = 0 } is dense in Ω \Omega Ω . Since p p p is a minor of M L ∗ M_{L_*} M L ∗ ,
{ w ∈ Ω : p ( w ) ≠ 0 } ⊆ Ω L ∗ ⊆ Ω D , \{w \in\Omega: p(w) \ne0\} \subseteq\Omega_{L_*} \subseteq\Omega_D, { w ∈ Ω : p ( w ) = 0 } ⊆ Ω L ∗ ⊆ Ω D ,
it follows that Ω D \Omega_D Ω D is dense in Ω \Omega Ω .
For the measure-zero statement, use the same nonzero minor p p p chosen above. Since
{ w ∈ Ω : p ( w ) ≠ 0 } ⊆ Ω D , \{w \in\Omega: p(w) \ne0\} \subseteq\Omega_D, { w ∈ Ω : p ( w ) = 0 } ⊆ Ω D ,
we have
Ω ∖ Ω D ⊆ { w ∈ Ω : p ( w ) = 0 } ⊆ Z ( p ) . \Omega\setminus\Omega_D \subseteq\{w \in\Omega: p(w) = 0\} \subseteq Z(p). Ω ∖ Ω D ⊆ { w ∈ Ω : p ( w ) = 0 } ⊆ Z ( p ) .
Because p p p is a nonzero polynomial on R d \mathbb{R}^d R d , its zero set Z ( p ) Z(p) Z ( p ) has Lebesgue measure zero in R d \mathbb{R}^d R d . Therefore
Leb ( Ω ∖ Ω D ) = 0. \operatorname{Leb}(\Omega\setminus\Omega_D) = 0. Leb ( Ω ∖ Ω D ) = 0.
CCDS
The proof of Theorem 3.6 relies on the following elementary Hilbert-space calculation, which characterizes exactly the feasible values of the one-step CCDS deviation.
Lemma A.4 (Distance equation: explicit solutions and feasibility). Let Y ⊂ H Y \subset H Y ⊂ H be closed, let u ∈ Y ⊥ u \in Y^\perp u ∈ Y ⊥ with ∥ u ∥ = 1 \lVert u\rVert= 1 ∥ u ∥ = 1 , and let r ∈ H r \in H r ∈ H . Set a : = ( I − Π Y ) r ∈ Y ⊥ a := (I - \Pi_Y)r \in Y^\perp a := ( I − Π Y ) r ∈ Y ⊥ , α : = ⟨ a , u ⟩ \alpha:= \langle a, u\rangle α := ⟨ a , u ⟩ . Then, for any d ≥ 0 d \ge0 d ≥ 0 , the equation dist ( r − λ u , Y ) = d \operatorname{dist}(r - \lambda u, Y) = d dist ( r − λ u , Y ) = d has a real solution λ ∈ R \lambda\in\mathbb{R} λ ∈ R if and only if d ≥ d min : = inf λ ∈ R dist ( r − λ u , Y ) = ∥ a ∥ 2 − α 2 d \ge d_{\min} := \inf_{\lambda\in\mathbb{R}} \operatorname{dist}(r - \lambda u, Y) = \sqrt{\lVert a\rVert^2 - \alpha^2} d ≥ d m i n := inf λ ∈ R dist ( r − λ u , Y ) = ∥ a ∥ 2 − α 2 . When feasible, the solutions are λ ± = α ± d 2 − d min 2 \lambda_{\pm} = \alpha\pm\sqrt{d^2 - d_{\min}^2} λ ± = α ± d 2 − d m i n 2 . Moreover, the unique minimizer is λ ⋆ = α \lambda^\star= \alpha λ ⋆ = α , attaining dist ( r − λ ⋆ u , Y ) = d min \operatorname{dist}(r - \lambda^\star u, Y) = d_{\min} dist ( r − λ ⋆ u , Y ) = d m i n .
Proof. Since u ∈ Y ⊥ u \in Y^\perp u ∈ Y ⊥ and ∥ u ∥ = 1 \lVert u\rVert= 1 ∥ u ∥ = 1 , we obtain dist ( r − λ u , Y ) 2 = ∥ ( I − Π Y ) ( r − λ u ) ∥ 2 = ∥ a − λ u ∥ 2 = ∥ a ∥ 2 − 2 λ ⟨ a , u ⟩ + λ 2 = ( λ − α ) 2 + ( ∥ a ∥ 2 − α 2 ) \operatorname{dist}(r - \lambda u, Y)^2 = \lVert(I - \Pi_Y)(r - \lambda u)\rVert^2 = \lVert a - \lambda u\rVert^2 = \lVert a\rVert^2 - 2\lambda\langle a, u\rangle+ \lambda^2 = (\lambda- \alpha)^2 + (\lVert a\rVert^2 - \alpha^2) dist ( r − λ u , Y ) 2 = ∥( I − Π Y ) ( r − λ u ) ∥ 2 = ∥ a − λ u ∥ 2 = ∥ a ∥ 2 − 2 λ ⟨ a , u ⟩ + λ 2 = ( λ − α ) 2 + (∥ a ∥ 2 − α 2 ) . Hence dist ( r − λ u , Y ) = d \operatorname{dist}(r - \lambda u, Y) = d dist ( r − λ u , Y ) = d is equivalent to ( λ − α ) 2 = d 2 − ( ∥ a ∥ 2 − α 2 ) (\lambda-\alpha)^2=d^2-(\lVert a\rVert^2-\alpha^2) ( λ − α ) 2 = d 2 − (∥ a ∥ 2 − α 2 ) . A real solution therefore exists if and only if d 2 ≥ ∥ a ∥ 2 − α 2 d^2\ge\lVert a\rVert^2-\alpha^2 d 2 ≥ ∥ a ∥ 2 − α 2 , equivalently d ≥ d min d\ge d_{\min} d ≥ d m i n , and in that case λ = α ± d 2 − d min 2 \lambda=\alpha\pm\sqrt{d^2-d_{\min}^2} λ = α ± d 2 − d m i n 2 . Finally, the squared distance is minimized uniquely at λ ⋆ = α \lambda^\star=\alpha λ ⋆ = α , where its value is d min 2 d_{\min}^2 d m i n 2 .
Derivation of Equation (13) in Remark 3.7 . Recall that
Y t = span { u 1 , … , u t } , Y 0 = { 0 } , Y_t=\operatorname{span}\{u_1,\ldots,u_t\},\qquad Y_0=\{0\}, Y t = span { u 1 , … , u t } , Y 0 = { 0 } ,
where u 1 , … , u t u_1,\ldots,u_t u 1 , … , u t are orthonormal. Also,
r 0 = y , r s = r s − 1 − λ s u s , d s = dist ( r s , Y s − 1 ) . r_0=y,\qquad r_s=r_{s-1}-\lambda_su_s,\qquad d_s=\operatorname{dist}(r_s,Y_{s-1}). r 0 = y , r s = r s − 1 − λ s u s , d s = dist ( r s , Y s − 1 ) .
By definition, α s : = ⟨ r s − 1 , u s ⟩ \alpha_s:=\langle r_{s-1},u_s\rangle α s := ⟨ r s − 1 , u s ⟩ . Since
r s − 1 = y − ∑ j = 1 s − 1 λ j u j r_{s-1}=y-\sum_{j=1}^{s-1}\lambda_ju_j r s − 1 = y − j = 1 ∑ s − 1 λ j u j
and u s ⊥ u j u_s\perp u_j u s ⊥ u j for every j < s j<s j < s , we obtain
α s = ⟨ y − ∑ j = 1 s − 1 λ j u j , u s ⟩ = ⟨ y , u s ⟩ . \alpha_s=\left\langle y-\sum_{j=1}^{s-1}\lambda_ju_j,u_s\right\rangle=\langle y,u_s\rangle. α s = ⟨ y − j = 1 ∑ s − 1 λ j u j , u s ⟩ = ⟨ y , u s ⟩ .
Set b s : = ( I − Π Y s ) y b_s:=(I-\Pi_{Y_s})y b s := ( I − Π Y s ) y . Iterating the residual recursion gives r t = y − ∑ s = 1 t λ s u s r_t=y-\sum_{s=1}^t\lambda_su_s r t = y − ∑ s = 1 t λ s u s . Since u 1 , … , u t u_1,\ldots,u_t u 1 , … , u t are an orthonormal basis of Y t Y_t Y t ,
Π Y t y = ∑ s = 1 t ⟨ y , u s ⟩ u s = ∑ s = 1 t α s u s . \Pi_{Y_t}y=\sum_{s=1}^t\langle y,u_s\rangle u_s=\sum_{s=1}^t\alpha_su_s. Π Y t y = s = 1 ∑ t ⟨ y , u s ⟩ u s = s = 1 ∑ t α s u s .
Therefore, y = b t + ∑ s = 1 t α s u s y=b_t+\sum_{s=1}^t\alpha_su_s y = b t + ∑ s = 1 t α s u s , and hence
r t = b t + ∑ s = 1 t ( α s − λ s ) u s . r_t=b_t+\sum_{s=1}^t(\alpha_s-\lambda_s)u_s. r t = b t + s = 1 ∑ t ( α s − λ s ) u s .
Because b t ⊥ Y t b_t\perp Y_t b t ⊥ Y t and the vectors u 1 , … , u t u_1,\ldots,u_t u 1 , … , u t are orthonormal,
∥ r t ∥ 2 = ∥ b t ∥ 2 + ∑ s = 1 t ( λ s − α s ) 2 (22) \lVert r_t\rVert^2=\lVert b_t\rVert^2+\sum_{s=1}^t(\lambda_s-\alpha_s)^2 \tag*{(22)} ∥ r t ∥ 2 = ∥ b t ∥ 2 + s = 1 ∑ t ( λ s − α s ) 2 (22)
Since b t = ( I − Π Y t ) y b_t=(I-\Pi_{Y_t})y b t = ( I − Π Y t ) y ,
∥ b t ∥ 2 = dist ( y , Y t ) 2 . (23) \lVert b_t\rVert^2=\operatorname{dist}(y,Y_t)^2. \tag*{(23)} ∥ b t ∥ 2 = dist ( y , Y t ) 2 . (23)
It remains to relate the coefficient discrepancies to the prescribed distances. Fix s ≤ t s\le t s ≤ t . Since
r s − 1 = y − ∑ j = 1 s − 1 λ j u j r_{s-1}=y-\sum_{j=1}^{s-1}\lambda_ju_j r s − 1 = y − j = 1 ∑ s − 1 λ j u j
and ∑ j = 1 s − 1 λ j u j ∈ Y s − 1 \sum_{j=1}^{s-1}\lambda_j u_j \in Y_{s-1} ∑ j = 1 s − 1 λ j u j ∈ Y s − 1 , we have
( I − Π Y s − 1 ) r s − 1 = ( I − Π Y s − 1 ) y . (24) (I-\Pi_{Y_{s-1}})r_{s-1}=(I-\Pi_{Y_{s-1}})y. \tag*{(24)} ( I − Π Y s − 1 ) r s − 1 = ( I − Π Y s − 1 ) y . (24)
Furthermore, because y = b s + ∑ j = 1 s α j u j y=b_s+\sum_{j=1}^{s}\alpha_j u_j y = b s + ∑ j = 1 s α j u j , we have
( I − Π Y s − 1 ) y = b s + α s u s . (25) (I-\Pi_{Y_{s-1}})y=b_s+\alpha_su_s. \tag*{(25)} ( I − Π Y s − 1 ) y = b s + α s u s . (25)
The two terms on the right-hand side are orthogonal. Therefore,
∥ ( I − Π Y s − 1 ) y ∥ 2 = ∥ b s ∥ 2 + α s 2 . \|(I-\Pi_{Y_{s-1}})y\|^2=\|b_s\|^2+\alpha_s^2. ∥ ( I − Π Y s − 1 ) y ∥ 2 = ∥ b s ∥ 2 + α s 2 .
Consequently,
d s , min 2 = ∥ a s ∥ 2 − α s 2 = ∥ ( I − Π Y s − 1 ) r s − 1 ∥ 2 − α s 2 = ∥ b s ∥ 2 . (26) d_{s,\min}^2=\|a_s\|^2-\alpha_s^2=\|(I-\Pi_{Y_{s-1}})r_{s-1}\|^2-\alpha_s^2=\|b_s\|^2. \tag*{(26)} d s , m i n 2 = ∥ a s ∥ 2 − α s 2 = ∥ ( I − Π Y s − 1 ) r s − 1 ∥ 2 − α s 2 = ∥ b s ∥ 2 . (26)
On the other hand, by (A.5) and (A.6) we have
( I − Π Y s − 1 ) r s = ( I − Π Y s − 1 ) ( r s − 1 − λ s u s ) = b s + ( α s − λ s ) u s . (I-\Pi_{Y_{s-1}})r_s=(I-\Pi_{Y_{s-1}})(r_{s-1}-\lambda_su_s)=b_s+(\alpha_s-\lambda_s)u_s. ( I − Π Y s − 1 ) r s = ( I − Π Y s − 1 ) ( r s − 1 − λ s u s ) = b s + ( α s − λ s ) u s .
The two terms on the right-hand side are orthogonal. Therefore,
d s 2 = dist ( r s , Y s − 1 ) 2 = ∥ b s ∥ 2 + ( λ s − α s ) 2 . d_s^2=\operatorname{dist}(r_s,Y_{s-1})^2=\|b_s\|^2+(\lambda_s-\alpha_s)^2. d s 2 = dist ( r s , Y s − 1 ) 2 = ∥ b s ∥ 2 + ( λ s − α s ) 2 .
By (A.7) we obtain ( λ s − α s ) 2 = d s 2 − d s , min 2 (\lambda_s-\alpha_s)^2=d_s^2-d_{s,\min}^2 ( λ s − α s ) 2 = d s 2 − d s , m i n 2 . Applying this identity for s = 1 , … , t s=1,\ldots,t s = 1 , … , t , and using ∥ b t ∥ 2 = d t , min 2 \|b_t\|^2=d_{t,\min}^2 ∥ b t ∥ 2 = d t , m i n 2 , Equation (A.3) gives
∥ r t ∥ 2 = d t , min 2 + ∑ s = 1 t ( d s 2 − d s , min 2 ) = d t 2 + ∑ s = 1 t − 1 ( d s 2 − d s , min 2 ) . \|r_t\|^2=d_{t,\min}^2+\sum_{s=1}^{t}(d_s^2-d_{s,\min}^2)=d_t^2+\sum_{s=1}^{t-1}(d_s^2-d_{s,\min}^2). ∥ r t ∥ 2 = d t , m i n 2 + s = 1 ∑ t ( d s 2 − d s , m i n 2 ) = d t 2 + s = 1 ∑ t − 1 ( d s 2 − d s , m i n 2 ) .
This proves Equation (13) . Finally, combining (A.4) and (A.7) we obtain d t , min = dist ( y , Y t ) d_{t,\min}=\operatorname{dist}(y,Y_t) d t , m i n = dist ( y , Y t ) .
Explicit computation of the CCDS dictionary-coordinate vector. Let q 1 , … , q T q_1,\ldots,q_T q 1 , … , q T be the atoms selected along the CCDS path, with u t u_t u t and Y t Y_t Y t defined as in (14) . Let η t : = ∥ q t − Π Y t − 1 q t ∥ > 0 \eta_t:=\|q_t-\Pi_{Y_{t-1}}q_t\|>0 η t := ∥ q t − Π Y t − 1 q t ∥ > 0 , and let e t ∈ R t e_t\in\mathbb{R}^t e t ∈ R t denote the t t t -th canonical basis vector. Define recursively coefficient vectors c ( t ) ∈ R t c^{(t)}\in\mathbb{R}^t c ( t ) ∈ R t by c ( 1 ) : = ( 1 ) c^{(1)}:=(1) c ( 1 ) := ( 1 ) , and, for t ≥ 2 t\ge2 t ≥ 2 ,
c ( t ) : = 1 η t ( e t − ∑ s = 1 t − 1 ⟨ q t , u s ⟩ c ~ ( s , t ) ) . (27) c^{(t)}:=\frac{1}{\eta_t}\left(e_t-\sum_{s=1}^{t-1}\langle q_t,u_s\rangle\widetilde{c}^{(s,t)}\right). \tag*{(27)} c ( t ) := η t 1 ( e t − s = 1 ∑ t − 1 ⟨ q t , u s ⟩ c ( s , t ) ) . (27)
where c ~ ( s , t ) ∈ R t \widetilde{c}^{(s,t)}\in\mathbb{R}^t c ( s , t ) ∈ R t is the zero-padded extension of c ( s ) c^{(s)} c ( s ) , namely c ~ ( s , t ) : = ( c 1 ( s ) , … , c s ( s ) , 0 , … , 0 ) \widetilde{c}^{(s,t)}:=(c_1^{(s)},\ldots,c_s^{(s)},0,\ldots,0) c ( s , t ) := ( c 1 ( s ) , … , c s ( s ) , 0 , … , 0 ) . Set β ( 0 ) : = 0 ∈ R 0 \beta^{(0)}:=0\in\mathbb{R}^0 β ( 0 ) := 0 ∈ R 0 , and recursively define
β ( t ) : = ( β ( t − 1 ) , 0 ) + λ t c ( t ) ∈ R t . (28) \beta^{(t)}:=(\beta^{(t-1)},0)+\lambda_tc^{(t)}\in\mathbb{R}^t. \tag*{(28)} β ( t ) := ( β ( t − 1 ) , 0 ) + λ t c ( t ) ∈ R t . (28)
Proposition A.5 (Explicit CCDS dictionary-coordinate recursion). For each t = 1 , … , T t=1,\ldots,T t = 1 , … , T one has u t = ∑ j = 1 t c j ( t ) q j u_t=\sum_{j=1}^{t}c_j^{(t)}q_j u t = ∑ j = 1 t c j ( t ) q j , and consequently y ^ T = ∑ t = 1 T λ t u t = ∑ j = 1 s β j ( T ) q j \hat{y}_T=\sum_{t=1}^{T}\lambda_tu_t=\sum_{j=1}^{s}\beta_j^{(T)}q_j y ^ T = ∑ t = 1 T λ t u t = ∑ j = 1 s β j ( T ) q j .
Proof. We argue by induction on t t t . For t = 1 t=1 t = 1 , since Y 0 = { 0 } Y_0=\{0\} Y 0 = { 0 } , one has u 1 = q 1 u_1=q_1 u 1 = q 1 , so c ( 1 ) = ( 1 ) c^{(1)}=(1) c ( 1 ) = ( 1 ) and the claim holds. Assume now that for each s < t s<t s < t , u s = ∑ j = 1 s c j ( s ) q j u_s=\sum_{j=1}^{s}c_j^{(s)}q_j u s = ∑ j = 1 s c j ( s ) q j . Since { u s } s = 1 t − 1 \{u_s\}_{s=1}^{t-1} { u s } s = 1 t − 1 is an orthonormal basis of Y t − 1 Y_{t-1} Y t − 1 , we have Π Y t − 1 q t = ∑ s = 1 t − 1 ⟨ q t , u s ⟩ u s \Pi_{Y_{t-1}}q_t=\sum_{s=1}^{t-1}\langle q_t,u_s\rangle u_s Π Y t − 1 q t = ∑ s = 1 t − 1 ⟨ q t , u s ⟩ u s . Substituting the inductive representation of each u s u_s u s ,
q t − Π Y t − 1 q t = q t − ∑ s = 1 t − 1 ⟨ q t , u s ⟩ ∑ j = 1 s c j ( s ) q j . q_t-\Pi_{Y_{t-1}}q_t=q_t-\sum_{s=1}^{t-1}\langle q_t,u_s\rangle\sum_{j=1}^{s}c_j^{(s)}q_j. q t − Π Y t − 1 q t = q t − s = 1 ∑ t − 1 ⟨ q t , u s ⟩ j = 1 ∑ s c j ( s ) q j .
After zero-padding the vectors c ( s ) c^{(s)} c ( s ) to R t \mathbb{R}^{t} R t , this becomes
q t − Π Y t − 1 q t = ∑ j = 1 t ( e t − ∑ s = 1 t − 1 ⟨ q t , u s ⟩ c ~ ( s , t ) ) j q j . q_t-\Pi_{Y_{t-1}}q_t=\sum_{j=1}^{t}\left(e_t-\sum_{s=1}^{t-1}\langle q_t,u_s\rangle\widetilde{c}^{(s,t)}\right)_j q_j. q t − Π Y t − 1 q t = j = 1 ∑ t ( e t − s = 1 ∑ t − 1 ⟨ q t , u s ⟩ c ( s , t ) ) j q j .
Dividing by η t = ∥ q t − Π Y t − 1 q t ∥ \eta_t=\lVert q_t-\Pi_{Y_{t-1}}q_t\rVert η t = ∥ q t − Π Y t − 1 q t ∥ yields u t = ∑ j = 1 t c j ( t ) q j u_t=\sum_{j=1}^{t}c_j^{(t)}q_j u t = ∑ j = 1 t c j ( t ) q j . This proves the first claim. Finally,
y ^ T = ∑ t = 1 T λ t u t = ∑ t = 1 T λ t ∑ j = 1 t c j ( t ) q j = ∑ j = 1 s β j ( T ) q j , \hat{y}_T=\sum_{t=1}^{T}\lambda_tu_t=\sum_{t=1}^{T}\lambda_t\sum_{j=1}^{t}c_j^{(t)}q_j=\sum_{j=1}^{s}\beta_j^{(T)}q_j, y ^ T = t = 1 ∑ T λ t u t = t = 1 ∑ T λ t j = 1 ∑ t c j ( t ) q j = j = 1 ∑ s β j ( T ) q j ,
by the recursive definition of β ( t ) \beta^{(t)} β ( t ) . This proves the result.
Proof of Proposition 3.8 (Minimal deviation CCDS recovers orthogonal coordinates). Starting from Y 0 = { 0 } Y_0=\{0\} Y 0 = { 0 } , define for t = 1 , … , s t=1,\ldots,s t = 1 , … , s , as in (14) ,
η t : = ∥ q t − Π Y t − 1 q t ∥ > 0 , u t : = q t − Π Y t − 1 q t η t , Y t : = Y t − 1 ⊕ span { u t } . \eta_t:=\lVert q_t-\Pi_{Y_{t-1}}q_t\rVert>0,\qquad u_t:=\frac{q_t-\Pi_{Y_{t-1}}q_t}{\eta_t},\qquad Y_t:=Y_{t-1}\oplus\operatorname{span}\{u_t\}. η t := ∥ q t − Π Y t − 1 q t ∥ > 0 , u t := η t q t − Π Y t − 1 q t , Y t := Y t − 1 ⊕ span { u t } .
Since q 1 , … , q s q_1,\ldots,q_s q 1 , … , q s are linearly independent, q t ∉ Y t − 1 q_t\notin Y_{t-1} q t ∈ / Y t − 1 for every t t t , hence η t > 0 \eta_t>0 η t > 0 and each u t u_t u t is well defined. By construction, u t ⊥ Y t − 1 u_t\perp Y_{t-1} u t ⊥ Y t − 1 , ∥ u t ∥ = 1 \lVert u_t\rVert=1 ∥ u t ∥ = 1 , and therefore Y t = span { q 1 , … , q t } = span { u 1 , … , u t } Y_t=\operatorname{span}\{q_1,\ldots,q_t\}=\operatorname{span}\{u_1,\ldots,u_t\} Y t = span { q 1 , … , q t } = span { u 1 , … , u t } . Thus u 1 , … , u s u_1,\ldots,u_s u 1 , … , u s is an orthonormal basis of E E E . Write the orthonormal expansion of Π E y \Pi_Ey Π E y as Π E y = ∑ j = 1 s γ j u j \Pi_Ey=\sum_{j=1}^{s}\gamma_ju_j Π E y = ∑ j = 1 s γ j u j , with γ j : = ⟨ Π E y , u j ⟩ \gamma_j:=\langle\Pi_Ey,u_j\rangle γ j := ⟨ Π E y , u j ⟩ . Set
h : = y − Π E y . h:=y-\Pi_Ey. h := y − Π E y .
Since h ⊥ E h\perp E h ⊥ E , we have
y = h + ∑ j = 1 s γ j u j . y=h+\sum_{j=1}^{s}\gamma_ju_j. y = h + j = 1 ∑ s γ j u j .
Set CCDS D t ( y ; q 1 : t , d min , 1 : t ) : = y ^ t \operatorname{CCDS}_{\mathcal{D}}^t(y;q_{1:t},d_{\min,1:t}):=\hat{y}_t CCDS D t ( y ; q 1 : t , d m i n , 1 : t ) := y ^ t . We prove by induction that
y ^ t = ∑ j = 1 t γ j u j , r t = h + ∑ j = t + 1 s γ j u j . \hat{y}_t=\sum_{j=1}^{t}\gamma_ju_j,\qquad r_t=h+\sum_{j=t+1}^{s}\gamma_ju_j. y ^ t = j = 1 ∑ t γ j u j , r t = h + j = t + 1 ∑ s γ j u j .
For t = 1 t=1 t = 1 , this follows from y ^ 0 = 0 \hat{y}_0=0 y ^ 0 = 0 and r 0 = y = h + ∑ j = 1 s γ j u j r_0=y=h+\sum_{j=1}^{s}\gamma_j u_j r 0 = y = h + ∑ j = 1 s γ j u j . Assume the claim holds before step t t t . Since Y t − 1 = span { u 1 , … , u t − 1 } Y_{t-1}=\operatorname{span}\{u_1,\ldots,u_{t-1}\} Y t − 1 = span { u 1 , … , u t − 1 } and
r t − 1 = h + ∑ j = t s γ j u j r_{t-1}=h+\sum_{j=t}^{s}\gamma_j u_j r t − 1 = h + j = t ∑ s γ j u j
where h ⊥ E h\perp E h ⊥ E and u t , … , u s ⊥ Y t − 1 u_t,\ldots,u_s\perp Y_{t-1} u t , … , u s ⊥ Y t − 1 , we have r t − 1 ⊥ Y t − 1 r_{t-1}\perp Y_{t-1} r t − 1 ⊥ Y t − 1 . Hence the CCDS off-scaffold residual is
a t : = ( I − Π Y t − 1 ) r t − 1 = r t − 1 . a_t:=(I-\Pi_{Y_{t-1}})r_{t-1}=r_{t-1}. a t := ( I − Π Y t − 1 ) r t − 1 = r t − 1 .
Therefore
α t : = ⟨ a t , u t ⟩ = ⟨ h + ∑ j = t s γ j u j , u t ⟩ = γ t . \alpha_t:=\langle a_t,u_t\rangle=\left\langle h+\sum_{j=t}^{s}\gamma_j u_j,u_t\right\rangle=\gamma_t. α t := ⟨ a t , u t ⟩ = ⟨ h + j = t ∑ s γ j u j , u t ⟩ = γ t .
Choosing d t = d t , min d_t=d_{t,\min} d t = d t , m i n in the CCDS root formula gives λ t = α t ± d t 2 − d t , min 2 = α t = γ t \lambda_t=\alpha_t\pm\sqrt{d_t^2-d_{t,\min}^2}=\alpha_t=\gamma_t λ t = α t ± d t 2 − d t , m i n 2 = α t = γ t . Consequently, y ^ t = y ^ t − 1 + λ t u t = ∑ j = 1 t γ j u j \hat{y}_t=\hat{y}_{t-1}+\lambda_tu_t=\sum_{j=1}^{t}\gamma_j u_j y ^ t = y ^ t − 1 + λ t u t = ∑ j = 1 t γ j u j , and r t = r t − 1 − γ t u t = h + ∑ j = t + 1 s γ j u j r_t=r_{t-1}-\gamma_tu_t=h+\sum_{j=t+1}^{s}\gamma_j u_j r t = r t − 1 − γ t u t = h + ∑ j = t + 1 s γ j u j . This closes the induction. Thus,
y ^ s = Π E y , r s = h = y − Π E y . \hat{y}_s=\Pi_Ey,\qquad r_s=h=y-\Pi_Ey. y ^ s = Π E y , r s = h = y − Π E y .
In particular, r s = 0 r_s=0 r s = 0 when y ∈ E y\in E y ∈ E . We conclude by Proposition A.5 . ■
Proof of Proposition 3.9 (MP and OMP as CCDS boundaries). We show that the classical greedy pursuits MP and OMP arise as extremal regimes of the CCDS distance equation, while strict interior CCDS updates are globally inaccessible to OMP, marking a geometric separation between OMP and CCDS.
(i) (MP boundary). For Matching Pursuit (MP), keep the reference space trivial, Y t − 1 = { 0 } Y_{t-1}=\{0\} Y t − 1 = { 0 } , at every step and select q t ∈ arg max q ∈ D ∣ ⟨ r t − 1 , q ⟩ ∣ q_t\in\operatorname*{arg\,max}_{q\in D}|\langle r_{t-1},q\rangle| q t ∈ arg max q ∈ D ∣ ⟨ r t − 1 , q ⟩ ∣ , that is, use the MP atom-selection rule. Then u t = q t u_t=q_t u t = q t , a t = ( I − Π Y t − 1 ) r t − 1 = r t − 1 a_t=(I-\Pi_{Y_{t-1}})r_{t-1}=r_{t-1} a t = ( I − Π Y t − 1 ) r t − 1 = r t − 1 , and α t = ⟨ a t , u t ⟩ = ⟨ r t − 1 , q t ⟩ \alpha_t=\langle a_t,u_t\rangle=\langle r_{t-1},q_t\rangle α t = ⟨ a t , u t ⟩ = ⟨ r t − 1 , q t ⟩ . At the minimal-deviation boundary d t = d t , min d_t=d_{t,\min} d t = d t , m i n , the CCDS root satisfies λ t = α t = ⟨ r t − 1 , q t ⟩ \lambda_t=\alpha_t=\langle r_{t-1},q_t\rangle λ t = α t = ⟨ r t − 1 , q t ⟩ , so the CCDS updates become
y ^ t = y ^ t − 1 + λ t q t , r t = r t − 1 − λ t q t , \hat{y}_t=\hat{y}_{t-1}+\lambda_tq_t,\qquad r_t=r_{t-1}-\lambda_tq_t, y ^ t = y ^ t − 1 + λ t q t , r t = r t − 1 − λ t q t ,
which are exactly the Matching Pursuit iterates.
(ii) (OMP boundary). In contrast, when the previously selected directions are retained through the nested spaces Y t = span { q 1 , … , q t } Y_t=\operatorname{span}\{q_1,\ldots,q_t\} Y t = span { q 1 , … , q t } , Proposition 3.8 shows that, for any fixed linearly independent atom ordering q 1 : T q_{1:T} q 1 : T , the choice d t = d t , min d_t=d_{t,\min} d t = d t , m i n gives the CCDS output y ^ t = Π Y t y \hat{y}_t=\Pi_{Y_t}y y ^ t = Π Y t y . Hence, if q t q_t q t is selected at each step by the OMP atom-selection rule, minimal-deviation CCDS and OMP produce the same iterates until termination. Thus MP and OMP correspond respectively to the minimal-deviation boundary without and with accumulated subspace geometry, whereas full CCDS retains the nested geometry while allowing the interior regime d t > d t , min d_t>d_{t,\min} d t > d t , m i n .
(iii) (Global geometric separation from OMP). First, we establish a global necessary condition for every OMP iterate, independent of the atom ordering. Note that every OMP iterate is the orthogonal projection of y y y onto some dictionary-generated selected subspace Z Z Z : y ^ O M P = Π Z y \hat{y}^{\mathrm{OMP}}=\Pi_Zy y ^ OMP = Π Z y . Hence y − y ^ O M P ⊥ Z y-\hat{y}^{\mathrm{OMP}}\perp Z y − y ^ OMP ⊥ Z , and y ^ O M P ∈ Z \hat{y}^{\mathrm{OMP}}\in Z y ^ OMP ∈ Z , and therefore every OMP iterate satisfies the global invariant
⟨ y − y ^ O M P , y ^ O M P ⟩ = 0. (29) \langle y-\hat{y}^{\mathrm{OMP}},\hat{y}^{\mathrm{OMP}}\rangle=0. \tag*{(29)} ⟨ y − y ^ OMP , y ^ OMP ⟩ = 0. (29)
Now, in order to establish the global separation result, we show that any interior CCDS iterate violates the invariant (A.10). Assume we depart from an OMP boundary state y ^ t − 1 = Π Y t − 1 y \widehat{y}_{t-1} = \Pi_{Y_{t-1}}y y t − 1 = Π Y t − 1 y , so we have r t − 1 = y − Π Y t − 1 y ∈ Y t − 1 ⊥ r_{t-1} = y - \Pi_{Y_{t-1}}y \in Y_{t-1}^{\perp} r t − 1 = y − Π Y t − 1 y ∈ Y t − 1 ⊥ , and therefore
a t = ( I − Π Y t − 1 ) r t − 1 = r t − 1 . a_t = (I-\Pi_{Y_{t-1}})r_{t-1} = r_{t-1}. a t = ( I − Π Y t − 1 ) r t − 1 = r t − 1 .
Let u t ∈ Y t − 1 ⊥ u_t \in Y_{t-1}^{\perp} u t ∈ Y t − 1 ⊥ be unit norm, then
α t = ⟨ a t , u t ⟩ = ⟨ r t − 1 , u t ⟩ = ⟨ y − Π Y t − 1 y , u t ⟩ = ⟨ y , u t ⟩ . \alpha_t = \langle a_t,u_t\rangle= \langle r_{t-1},u_t\rangle= \langle y-\Pi_{Y_{t-1}}y,u_t\rangle= \langle y,u_t\rangle. α t = ⟨ a t , u t ⟩ = ⟨ r t − 1 , u t ⟩ = ⟨ y − Π Y t − 1 y , u t ⟩ = ⟨ y , u t ⟩ .
Consider the CCDS update y ^ t C C D S = y ^ t − 1 + λ t u t \widehat{y}^{\mathrm{CCDS}}_t = \widehat{y}_{t-1}+\lambda_tu_t y t CCDS = y t − 1 + λ t u t . Since y − y ^ t − 1 ⊥ Y t − 1 y-\widehat{y}_{t-1}\perp Y_{t-1} y − y t − 1 ⊥ Y t − 1 and u t ⊥ Y t − 1 u_t\perp Y_{t-1} u t ⊥ Y t − 1 ,
⟨ y − y ^ t C C D S , y ^ t C C D S ⟩ = ⟨ ( y − y ^ t − 1 ) − λ t u t , y ^ t − 1 + λ t u t ⟩ = λ t ⟨ y , u t ⟩ − λ t 2 = λ t ( α t − λ t ) . \langle y-\widehat{y}^{\mathrm{CCDS}}_t,\widehat{y}^{\mathrm{CCDS}}_t\rangle= \langle(y-\widehat{y}_{t-1})-\lambda_tu_t,\widehat{y}_{t-1}+\lambda_tu_t\rangle= \lambda_t\langle y,u_t\rangle-\lambda_t^2 = \lambda_t(\alpha_t-\lambda_t). ⟨ y − y t CCDS , y t CCDS ⟩ = ⟨( y − y t − 1 ) − λ t u t , y t − 1 + λ t u t ⟩ = λ t ⟨ y , u t ⟩ − λ t 2 = λ t ( α t − λ t ) .
Thus, whenever λ t ∉ { 0 , α t } \lambda_t\notin\{0,\alpha_t\} λ t ∈ / { 0 , α t } , we have ⟨ y − y ^ t C C D S , y ^ t C C D S ⟩ ≠ 0 \langle y-\widehat{y}^{\mathrm{CCDS}}_t,\widehat{y}^{\mathrm{CCDS}}_t\rangle\ne0 ⟨ y − y t CCDS , y t CCDS ⟩ = 0 . Hence y ^ t C C D S \widehat{y}^{\mathrm{CCDS}}_t y t CCDS violates the invariant (A.10) satisfied by every OMP iterate and therefore cannot be produced by OMP from any selected dictionary subspace.
For a strict CCDS interior choice d t > d t , min d_t>d_{t,\min} d t > d t , m i n , one has
λ t = α t ± d t 2 − d t , min 2 ≠ α t ; \lambda_t=\alpha_t\pm\sqrt{d_t^2-d_{t,\min}^2}\ne\alpha_t; λ t = α t ± d t 2 − d t , m i n 2 = α t ;
apart from the exceptional zero-update case λ t = 0 \lambda_t=0 λ t = 0 , the resulting CCDS iterate is therefore globally inaccessible to OMP.
Finite-dimensional CCDS feasibility obstruction and lifting
At step t t t , the prescribed deviation is feasible in the current ambient space if and only if d t ≥ d t , min d_t\ge d_{t,\min} d t ≥ d t , m i n . Hence any choice d t < d t , min d_t<d_{t,\min} d t < d t , m i n is geometrically unrealizable: no scalar λ t \lambda_t λ t can satisfy dist ( r t − 1 − λ t u t , Y t − 1 ) = d t \operatorname{dist}(r_{t-1}-\lambda_tu_t,Y_{t-1})=d_t dist ( r t − 1 − λ t u t , Y t − 1 ) = d t . In finite dimension this obstruction can arise when the available innovation direction is nearly orthogonal to the off-scaffold residual, motivating dimension lifting to restore feasibility.
Example A.6 (Finite-dimensional infeasibility). Let H = R 2 H=\mathbb{R}^2 H = R 2 , Y 0 = { 0 } Y_0=\{0\} Y 0 = { 0 } , and take the initial residual r 0 = e 1 = ( 1 , 0 ) r_0=e_1=(1,0) r 0 = e 1 = ( 1 , 0 ) . Suppose the only available innovation direction is u 1 = e 2 = ( 0 , 1 ) u_1=e_2=(0,1) u 1 = e 2 = ( 0 , 1 ) . Since Y 0 = { 0 } Y_0=\{0\} Y 0 = { 0 } , we have a 1 = ( I − Π Y 0 ) r 0 = e 1 a_1=(I-\Pi_{Y_0})r_0=e_1 a 1 = ( I − Π Y 0 ) r 0 = e 1 and hence α 1 = ⟨ a 1 , u 1 ⟩ = 0 \alpha_1=\langle a_1,u_1\rangle=0 α 1 = ⟨ a 1 , u 1 ⟩ = 0 . Therefore d 1 , min = ∥ a 1 ∥ 2 − α 1 2 = 1 d_{1,\min}=\sqrt{\lVert a_1\rVert^2-\alpha_1^2}=1 d 1 , m i n = ∥ a 1 ∥ 2 − α 1 2 = 1 . Thus no prescribed deviation d 1 < 1 d_1<1 d 1 < 1 is feasible: there is no λ ∈ R \lambda\in\mathbb{R} λ ∈ R such that dist ( r 0 − λ u 1 , Y 0 ) = d 1 \operatorname{dist}(r_0-\lambda u_1,Y_0)=d_1 dist ( r 0 − λ u 1 , Y 0 ) = d 1 . The obstruction comes from the available innovation direction being orthogonal to the residual; dimension lifting restores feasibility by introducing a direction with nonzero alignment with it.
Adding one new orthogonal dimension restores feasibility by allowing a new innovation direction with controlled alignment to a a a . This justifies the need for dimension lifting in order to guarantee universal deviation feasibility and, consequently, collapse of the parametrization error in CCDS.
Theorem A.7 (One-step feasibility by dimension lifting). Let H H H be a real Hilbert space, Y ⊂ H Y\subset H Y ⊂ H a closed subspace, and r ∈ H r\in H r ∈ H . Define a : = ( I − Π Y ) r ∈ Y ⊥ a:=(I-\Pi_Y)r\in Y^\perp a := ( I − Π Y ) r ∈ Y ⊥ . Fix a target deviation d d d satisfying $0\le d\le\lVert a\rVert$. Then there exists a Hilbert space H ~ : = H ⊕ R \widetilde{H}:=H\oplus\mathbb{R} H := H ⊕ R , an isometric embedding ι : H → H ~ \iota:H\to\widetilde{H} ι : H → H , and a unit vector u ∈ ( ι ( Y ) ) ⊥ ⊂ H ~ u\in(\iota(Y))^\perp\subset\widetilde{H} u ∈ ( ι ( Y ) ) ⊥ ⊂ H such that the CCDS distance equation dist ( ι ( r ) − λ u , ι ( Y ) ) = d \operatorname{dist}(\iota(r)-\lambda u,\iota(Y))=d dist ( ι ( r ) − λ u , ι ( Y )) = d admits a real solution λ ∈ R \lambda\in\mathbb{R} λ ∈ R . Moreover, one can choose u u u so that the minimal achievable deviation is exactly $d_{\min}(u)=d.
Proof. Define H ~ : = H ⊕ R \widetilde{H} := H \oplus\mathbb{R} H := H ⊕ R with inner product
⟨ ( x , s ) , ( y , t ) ⟩ H ~ : = ⟨ x , y ⟩ H + s t , \langle(x,s),(y,t)\rangle_{\widetilde{H}} := \langle x,y\rangle_H + st, ⟨( x , s ) , ( y , t ) ⟩ H := ⟨ x , y ⟩ H + s t ,
and the isometric embedding ι ( x ) = ( x , 0 ) \iota(x)=(x,0) ι ( x ) = ( x , 0 ) . Then ι ( Y ) \iota(Y) ι ( Y ) is a closed subspace and
( ι ( Y ) ) ⊥ = Y ⊥ ⊕ R . (\iota(Y))^\perp= Y^\perp\oplus\mathbb{R}. ( ι ( Y ) ) ⊥ = Y ⊥ ⊕ R .
Let
r ~ : = ι ( r ) , a ~ : = ( I − Π ι ( Y ) ) r ~ = ( a , 0 ) , \widetilde{r}:=\iota(r),\qquad\widetilde{a}:=(I-\Pi_{\iota(Y)})\widetilde{r}=(a,0), r := ι ( r ) , a := ( I − Π ι ( Y ) ) r = ( a , 0 ) ,
so that ∥ a ~ ∥ = A \|\widetilde{a}\|=A ∥ a ∥ = A . If A = 0 A=0 A = 0 , then d = 0 d=0 d = 0 and the claim is trivial. Assume A > 0 A>0 A > 0 and define e 1 : = a ~ A e_1:=\frac{\widetilde{a}}{A} e 1 := A a , e 2 : = ( 0 , 1 ) e_2:=(0,1) e 2 := ( 0 , 1 ) . Then e 1 , e 2 ∈ ( ι ( Y ) ) ⊥ e_1,e_2\in(\iota(Y))^\perp e 1 , e 2 ∈ ( ι ( Y ) ) ⊥ are orthonormal. Choose θ ∈ [ 0 , π / 2 ] \theta\in[0,\pi/2] θ ∈ [ 0 , π /2 ] such that sin θ = d A \sin\theta=\frac{d}{A} sin θ = A d . Define u : = cos θ e 1 + sin θ e 2 u:=\cos\theta e_1+\sin\theta e_2 u := cos θ e 1 + sin θ e 2 . Then u ∈ ( ι ( Y ) ) ⊥ u\in(\iota(Y))^\perp u ∈ ( ι ( Y ) ) ⊥ and ∥ u ∥ = 1 \|u\|=1 ∥ u ∥ = 1 . Moreover, α : = ⟨ a ~ , u ⟩ H ~ = A cos θ \alpha:=\langle\widetilde{a},u\rangle_{\widetilde{H}}=A\cos\theta α := ⟨ a , u ⟩ H = A cos θ .
By the CCDS feasibility formula,
d min ( u ) = ∥ a ~ ∥ 2 − α 2 = A 2 − A 2 cos 2 θ = A sin θ = d . d_{\min}(u)=\sqrt{\|\widetilde{a}\|^2-\alpha^2}=\sqrt{A^2-A^2\cos^2\theta}=A\sin\theta=d. d m i n ( u ) = ∥ a ∥ 2 − α 2 = A 2 − A 2 cos 2 θ = A sin θ = d .
Hence d ≥ d min ( u ) d\ge d_{\min}(u) d ≥ d m i n ( u ) , and the equation dist ( r ~ − λ u , ι ( Y ) ) = d \operatorname{dist}(\widetilde{r}-\lambda u,\iota(Y))=d dist ( r − λ u , ι ( Y )) = d admits a real solution λ \lambda λ . This completes the proof.
Resolution of Example A.6 by lifting one dimension. Embed H H H isometrically into H ~ = R 3 \widetilde{H}=\mathbb{R}^3 H = R 3 by x ↦ ( x , 0 ) x\mapsto(x,0) x ↦ ( x , 0 ) , and extend the orthogonal complement with the new basis vector e 3 e_3 e 3 . Choose the lifted innovation direction u ~ t = cos θ e 1 + sin θ e 3 \widetilde{u}_t=\cos\theta e_1+\sin\theta e_3 u t = cos θ e 1 + sin θ e 3 , sin θ = d t \sin\theta=d_t sin θ = d t . Then u ~ t ∈ ( ι ( Y t − 1 ) ) ⊥ \widetilde{u}_t\in(\iota(Y_{t-1}))^\perp u t ∈ ( ι ( Y t − 1 ) ) ⊥ , ∥ u ~ t ∥ = 1 \|\widetilde{u}_t\|=1 ∥ u t ∥ = 1 , and ⟨ a , u ~ t ⟩ = cos θ \langle a,\widetilde{u}_t\rangle=\cos\theta ⟨ a , u t ⟩ = cos θ , d min ( u ~ t ) = 1 − cos 2 θ = sin θ = d t d_{\min}(\widetilde{u}_t)=\sqrt{1-\cos^2\theta}=\sin\theta=d_t d m i n ( u t ) = 1 − cos 2 θ = sin θ = d t . Hence the CCDS equation
dist ( ι ( r t − 1 ( x 1 ) ) − λ u ~ t , ι ( Y t − 1 ) ) = d t \operatorname{dist}\left(\iota(r_{t-1}(x_1))-\lambda\widetilde{u}_t,\iota(Y_{t-1})\right)=d_t dist ( ι ( r t − 1 ( x 1 )) − λ u t , ι ( Y t − 1 ) ) = d t
admits a real solution, and the deviation d t d_t d t becomes feasible after adding a single orthogonal dimension.
Stability theorems
Proof of Theorem 3.11 (Stability of the scaffold/CCDS bottlenecks under relaxed interpolation). For each 1 ≤ k ≤ K 1\le k\le K 1 ≤ k ≤ K , let D k = { ( x k , 1 , y k , 1 ) , … , ( x k , ∣ D k ∣ , y k , ∣ D k ∣ ) } ⊆ Ξ s u b D_k=\{(x_{k,1},y_{k,1}),\ldots,(x_{k,|D_k|},y_{k,|D_k|})\}\subseteq\Xi_{\mathrm{sub}} D k = {( x k , 1 , y k , 1 ) , … , ( x k , ∣ D k ∣ , y k , ∣ D k ∣ )} ⊆ Ξ sub and choose depths L k , 1 , … , L k , ∣ D k ∣ L_{k,1},\ldots,L_{k,|D_k|} L k , 1 , … , L k , ∣ D k ∣ such that y k , j = J k W ( L k , j ) x k , j y_{k,j}=J_kW^{(L_{k,j})}x_{k,j} y k , j = J k W ( L k , j ) x k , j for all ( x k , j , y k , j ) ∈ D k (x_{k,j},y_{k,j})\in D_k ( x k , j , y k , j ) ∈ D k . Let I = { ( k , m , j ) : 1 ≤ k ≤ K , 0 ≤ m ≤ d − 1 , 1 ≤ j ≤ ∣ D k ∣ } \mathcal{I}=\{(k,m,j):1\le k\le K,\ 0\le m\le d-1,\ 1\le j\le|D_k|\} I = {( k , m , j ) : 1 ≤ k ≤ K , 0 ≤ m ≤ d − 1 , 1 ≤ j ≤ ∣ D k ∣ } be the fixed finite atom index set of the corresponding scaffold as defined in (4) . Write the reference atoms as g i = J k W ( m ) x k , j g_i=J_kW^{(m)}x_{k,j} g i = J k W ( m ) x k , j , with i = ( k , m , j ) ∈ I i=(k,m,j)\in\mathcal{I} i = ( k , m , j ) ∈ I , and the perturbed atoms as g i ′ = J k ′ W ( m ) x k , j g'_i=J'_kW^{(m)}x_{k,j} g i ′ = J k ′ W ( m ) x k , j . Let G = [ g i ] i ∈ I G=[g_i]_{i\in\mathcal{I}} G = [ g i ] i ∈ I , G ′ = [ g i ′ ] i ∈ I G'=[g'_i]_{i\in\mathcal{I}} G ′ = [ g i ′ ] i ∈ I , U = range ( G ) U=\operatorname{range}(G) U = range ( G ) , U ′ = range ( G ′ ) U'=\operatorname{range}(G') U ′ = range ( G ′ ) , and η : = ∥ G ′ − G ∥ 2 \eta:=\|G'-G\|_2 η := ∥ G ′ − G ∥ 2 . Also set V : = ∑ k = 1 K range ( Y k ) V:=\sum_{k=1}^K\operatorname{range}(Y_k) V := ∑ k = 1 K range ( Y k ) .
Since J k ′ = Y k R k ′ J'_k=Y_kR'_k J k ′ = Y k R k ′ , every perturbed atom g i ′ g'_i g i ′ belongs to range ( Y k ) \operatorname{range}(Y_k) range ( Y k ) , hence U ′ ⊆ V U'\subseteq V U ′ ⊆ V . By the scaffold identity (7) , V = U V=U V = U . Therefore U ′ ⊆ U U'\subseteq U U ′ ⊆ U .
Let r = rank ( G ) = dim U r=\operatorname{rank}(G)=\dim U r = rank ( G ) = dim U and γ = σ r ( G ) > 0 \gamma=\sigma_r(G)>0 γ = σ r ( G ) > 0 . Choose δ 0 < γ / 2 \delta_0<\gamma/2 δ 0 < γ /2 . If η < δ 0 \eta<\delta_0 η < δ 0 , then Weyl’s singular-value perturbation inequality [9 ] gives σ r ( G ′ ) ≥ σ r ( G ) − η > γ / 2 > 0 \sigma_r(G')\ge\sigma_r(G)-\eta>\gamma/2>0 σ r ( G ′ ) ≥ σ r ( G ) − η > γ /2 > 0 . Hence rank ( G ′ ) ≥ r \operatorname{rank}(G')\ge r rank ( G ′ ) ≥ r . Since U ′ ⊆ U U'\subseteq U U ′ ⊆ U and dim U = r \dim U=r dim U = r , also rank ( G ′ ) ≤ r \operatorname{rank}(G')\le r rank ( G ′ ) ≤ r . Therefore rank ( G ′ ) = r \operatorname{rank}(G')=r rank ( G ′ ) = r , and so U ′ = U U'=U U ′ = U . It follows immediately that Π U ′ = Π U \Pi_{U'}=\Pi_U Π U ′ = Π U , and hence ε p r o j ( f Ξ , U ′ ; Ξ ) = ε p r o j ( f Ξ , U ; Ξ ) \varepsilon_{\mathrm{proj}}(f_{\Xi},U';\Xi)=\varepsilon_{\mathrm{proj}}(f_{\Xi},U;\Xi) ε proj ( f Ξ , U ′ ; Ξ ) = ε proj ( f Ξ , U ; Ξ ) .
It remains to prove the parametrization bound. Since U ′ = U U'=U U ′ = U , the projected targets are identical: b ℓ : = Π U f Ξ ℓ = Π U ′ f Ξ ℓ b_\ell:=\Pi_U f_{\Xi_\ell}=\Pi_{U'}f_{\Xi_\ell} b ℓ := Π U f Ξ ℓ = Π U ′ f Ξ ℓ . Let n : = ∣ Ξ t r a i n ∣ n:=|\Xi_{\mathrm{train}}| n := ∣ Ξ train ∣ , fix ℓ ∈ { 1 , … , n } \ell\in\{1,\ldots,n\} ℓ ∈ { 1 , … , n } , and suppress the index ℓ \ell ℓ . Let r 0 = b ℓ r_0=b_\ell r 0 = b ℓ , and let r t r_t r t , t = 0 , … , T t=0,\ldots,T t = 0 , … , T , be the residuals of the reference CCDS path of the CCDS realizer C C D S D \mathrm{CCDS}_{\mathcal{D}} CCDS D . At step t t t , the reference path uses a prescribed atom label i t i_t i t , prescribed deviation d t d_t d t , and prescribed root branch ε t ∈ { − 1 , 1 } \varepsilon_t\in\{-1,1\} ε t ∈ { − 1 , 1 } . Let Y t − 1 : = span { u 1 , … , u t − 1 } Y_{t-1}:=\operatorname{span}\{u_1,\ldots,u_{t-1}\} Y t − 1 := span { u 1 , … , u t − 1 } , P t − 1 : = Π Y t − 1 P_{t-1}:=\Pi_{Y_{t-1}} P t − 1 := Π Y t − 1 , q t : = ( I − P t − 1 ) g i t q_t:=(I-P_{t-1})g_{i_t} q t := ( I − P t − 1 ) g i t , u t : = q t / ∥ q t ∥ u_t:=q_t/\lVert q_t\rVert u t := q t / ∥ q t ∥ , a t : = ( I − P t − 1 ) r t − 1 a_t:=(I-P_{t-1})r_{t-1} a t := ( I − P t − 1 ) r t − 1 , α t : = ⟨ a t , u t ⟩ \alpha_t:=\langle a_t,u_t\rangle α t := ⟨ a t , u t ⟩ , and d t , min 2 : = ∥ a t ∥ 2 − α t 2 d_{t,\min}^2:=\lVert a_t\rVert^2-\alpha_t^2 d t , m i n 2 := ∥ a t ∥ 2 − α t 2 . The CCDS coefficient is λ t = α t + ε t d t 2 − d t , min 2 \lambda_t=\alpha_t+\varepsilon_t\sqrt{d_t^2-d_{t,\min}^2} λ t = α t + ε t d t 2 − d t , m i n 2 , and the residual update is r t = r t − 1 − λ t u t r_t=r_{t-1}-\lambda_tu_t r t = r t − 1 − λ t u t .
We transport exactly this finite prescription to the perturbed atoms: the same labels i t i_t i t , the same deviations d t d_t d t , and the same root branches ε t \varepsilon_t ε t . Thus g i t g_{i_t} g i t is replaced by the corresponding g i t ′ g'_{i_t} g i t ′ , and all perturbed quantities Y t − 1 ′ Y'_{t-1} Y t − 1 ′ , P t − 1 ′ P'_{t-1} P t − 1 ′ , q t ′ q'_t q t ′ , u t ′ u'_t u t ′ , a t ′ a'_t a t ′ , α t ′ \alpha'_t α t ′ , λ t ′ \lambda'_t λ t ′ , and r t ′ r'_t r t ′ are defined by the same formulas.
We prove by induction that ∥ r t ′ − r t ∥ ≤ B t η \lVert r'_t-r_t\rVert\le B_t\eta ∥ r t ′ − r t ∥ ≤ B t η and ∥ u t ′ − u t ∥ ≤ A t η \lVert u'_t-u_t\rVert\le A_t\eta ∥ u t ′ − u t ∥ ≤ A t η for constants depending only on the reference trajectory. The base residual estimate is ∥ r 0 ′ − r 0 ∥ = 0 \lVert r'_0-r_0\rVert=0 ∥ r 0 ′ − r 0 ∥ = 0 , because b ℓ ′ = b ℓ b'_\ell=b_\ell b ℓ ′ = b ℓ . Assume the estimates are known up to step t − 1 t-1 t − 1 . Since the directions u 1 , … , u t − 1 u_1,\ldots,u_{t-1} u 1 , … , u t − 1 and u 1 ′ , … , u t − 1 ′ u'_1,\ldots,u'_{t-1} u 1 ′ , … , u t − 1 ′ are orthonormal along the CCDS innovation construction, if U t − 1 : = [ u 1 ⋯ u t − 1 ] U_{t-1}:=[u_1\ \cdots\ u_{t-1}] U t − 1 := [ u 1 ⋯ u t − 1 ] and U t − 1 ′ : = [ u 1 ′ ⋯ u t − 1 ′ ] U'_{t-1}:=[u'_1\ \cdots\ u'_{t-1}] U t − 1 ′ := [ u 1 ′ ⋯ u t − 1 ′ ] , then P t − 1 = U t − 1 U t − 1 T P_{t-1}=U_{t-1}U_{t-1}^{\mathsf{T}} P t − 1 = U t − 1 U t − 1 T and P t − 1 ′ = U t − 1 ′ ( U t − 1 ′ ) T P'_{t-1}=U'_{t-1}(U'_{t-1})^{\mathsf{T}} P t − 1 ′ = U t − 1 ′ ( U t − 1 ′ ) T . Add and subtract U t − 1 ( U t − 1 ′ ) T U_{t-1}(U'_{t-1})^{\mathsf{T}} U t − 1 ( U t − 1 ′ ) T : P t − 1 ′ − P t − 1 = ( U t − 1 ′ − U t − 1 ) ( U t − 1 ′ ) T + U t − 1 ( ( U t − 1 ′ ) T − U t − 1 T ) P'_{t-1}-P_{t-1}=(U'_{t-1}-U_{t-1})(U'_{t-1})^{\mathsf{T}}+U_{t-1}((U'_{t-1})^{\mathsf{T}}-U_{t-1}^{\mathsf{T}}) P t − 1 ′ − P t − 1 = ( U t − 1 ′ − U t − 1 ) ( U t − 1 ′ ) T + U t − 1 (( U t − 1 ′ ) T − U t − 1 T ) . Taking operator norms, ∥ P t − 1 ′ − P t − 1 ∥ o p ≤ ∥ U t − 1 ′ − U t − 1 ∥ 2 ∥ ( U t − 1 ′ ) T ∥ 2 + ∥ U t − 1 ∥ 2 ∥ ( U t − 1 ′ ) T − U t − 1 T ∥ 2 \lVert P'_{t-1}-P_{t-1}\rVert_{\mathrm{op}}\le\lVert U'_{t-1}-U_{t-1}\rVert_2\lVert(U'_{t-1})^{\mathsf{T}}\rVert_2+\lVert U_{t-1}\rVert_2\lVert(U'_{t-1})^{\mathsf{T}}-U_{t-1}^{\mathsf{T}}\rVert_2 ∥ P t − 1 ′ − P t − 1 ∥ op ≤ ∥ U t − 1 ′ − U t − 1 ∥ 2 ∥( U t − 1 ′ ) T ∥ 2 + ∥ U t − 1 ∥ 2 ∥( U t − 1 ′ ) T − U t − 1 T ∥ 2 . Since U t − 1 U_{t-1} U t − 1 and U t − 1 ′ U'_{t-1} U t − 1 ′ have orthonormal columns, ∥ U t − 1 ∥ 2 = ∥ U t − 1 ′ ∥ 2 = 1 \lVert U_{t-1}\rVert_2=\lVert U'_{t-1}\rVert_2=1 ∥ U t − 1 ∥ 2 = ∥ U t − 1 ′ ∥ 2 = 1 . Thus ∥ P t − 1 ′ − P t − 1 ∥ o p ≤ 2 ∥ U t − 1 ′ − U t − 1 ∥ 2 ≤ 2 ∥ U t − 1 ′ − U t − 1 ∥ F = 2 ( ∑ s = 1 t − 1 ∥ u s ′ − u s ∥ 2 ) 1 / 2 \lVert P'_{t-1}-P_{t-1}\rVert_{\mathrm{op}}\le2\lVert U'_{t-1}-U_{t-1}\rVert_2\le2\lVert U'_{t-1}-U_{t-1}\rVert_F=2\left(\sum_{s=1}^{t-1}\lVert u'_s-u_s\rVert^2\right)^{1/2} ∥ P t − 1 ′ − P t − 1 ∥ op ≤ 2 ∥ U t − 1 ′ − U t − 1 ∥ 2 ≤ 2 ∥ U t − 1 ′ − U t − 1 ∥ F = 2 ( ∑ s = 1 t − 1 ∥ u s ′ − u s ∥ 2 ) 1/2 . Now the induction hypothesis says that for all previous steps s < t s<t s < t , ∥ u s ′ − u s ∥ ≤ A s η \lVert u'_s-u_s\rVert\le A_s\eta ∥ u s ′ − u s ∥ ≤ A s η for some constants A s A_s A s depending only on the reference trajectory. Since there are only finitely many steps, define A t − 1 max : = max 1 ≤ s < t A s A^{\max}_{t-1}:=\max_{1\le s<t}A_s A t − 1 m a x := max 1 ≤ s < t A s . Then ( ∑ s = 1 t − 1 ∥ u s ′ − u s ∥ 2 ) 1 / 2 ≤ t − 1 A t − 1 max η \left(\sum_{s=1}^{t-1}\lVert u'_s-u_s\rVert^2\right)^{1/2}\le\sqrt{t-1}A^{\max}_{t-1}\eta ( ∑ s = 1 t − 1 ∥ u s ′ − u s ∥ 2 ) 1/2 ≤ t − 1 A t − 1 m a x η . Hence
∥ P t − 1 ′ − P t − 1 ∥ o p ≤ 2 t − 1 A t − 1 max η = C P , t η . (30) \lVert P'_{t-1}-P_{t-1}\rVert_{\mathrm{op}}\le2\sqrt{t-1}A^{\max}_{t-1}\eta=C_{P,t}\eta. \tag*{(30)} ∥ P t − 1 ′ − P t − 1 ∥ op ≤ 2 t − 1 A t − 1 m a x η = C P , t η . (30)
Since corresponding atom columns differ by at most η \eta η , we have ∥ g i t ′ − g i t ∥ ≤ η \lVert g'_{i_t}-g_{i_t}\rVert\le\eta ∥ g i t ′ − g i t ∥ ≤ η . Therefore q t ′ − q t = ( I − P t − 1 ′ ) ( g i t ′ − g i t ) + ( P t − 1 − P t − 1 ′ ) g i t q'_t-q_t=(I-P'_{t-1})(g'_{i_t}-g_{i_t})+(P_{t-1}-P'_{t-1})g_{i_t} q t ′ − q t = ( I − P t − 1 ′ ) ( g i t ′ − g i t ) + ( P t − 1 − P t − 1 ′ ) g i t , and so
∥ q t ′ − q t ∥ ≤ η + C P , t η ∥ g i t ∥ ≤ C q , t η . (31) \lVert q'_t-q_t\rVert\le\eta+C_{P,t}\eta\lVert g_{i_t}\rVert\le C_{q,t}\eta. \tag*{(31)} ∥ q t ′ − q t ∥ ≤ η + C P , t η ∥ g i t ∥ ≤ C q , t η . (31)
By the nondegeneracy assumption, ∥ q t ∥ ≥ ν > 0 \lVert q_t\rVert\ge\nu>0 ∥ q t ∥ ≥ ν > 0 . After decreasing δ 0 \delta_0 δ 0 , we may assume ∥ q t ′ − q t ∥ ≤ ν / 2 \lVert q'_t-q_t\rVert\le\nu/2 ∥ q t ′ − q t ∥ ≤ ν /2 . Then by the reverse triangle inequality, ∥ q t ′ ∥ ≥ ∥ q t ∥ − ∥ q t ′ − q t ∥ ≥ ν − ν / 2 = ν / 2 \lVert q'_t\rVert\ge\lVert q_t\rVert-\lVert q'_t-q_t\rVert\ge\nu-\nu/2=\nu/2 ∥ q t ′ ∥ ≥ ∥ q t ∥ − ∥ q t ′ − q t ∥ ≥ ν − ν /2 = ν /2 . So both q t q_t q t and q t ′ q'_t q t ′ stay away from zero. Now prove the Lipschitz bound. We write q t ′ ∥ q t ′ ∥ − q t ∥ q t ∥ = q t ′ − q t ∥ q t ′ ∥ + q t ( 1 ∥ q t ′ ∥ − 1 ∥ q t ∥ ) \frac{q'_t}{\lVert q'_t\rVert}-\frac{q_t}{\lVert q_t\rVert}=\frac{q'_t-q_t}{\lVert q'_t\rVert}+q_t\left(\frac{1}{\lVert q'_t\rVert}-\frac{1}{\lVert q_t\rVert}\right) ∥ q t ′ ∥ q t ′ − ∥ q t ∥ q t = ∥ q t ′ ∥ q t ′ − q t + q t ( ∥ q t ′ ∥ 1 − ∥ q t ∥ 1 ) . Taking norms, ∥ q t ′ ∥ q t ′ ∥ − q t ∥ q t ∥ ∥ ≤ ∥ q t ′ − q t ∥ ∥ q t ′ ∥ + ∥ q t ∥ ∣ 1 ∥ q t ′ ∥ − 1 ∥ q t ∥ ∣ \left\lVert\frac{q'_t}{\lVert q'_t\rVert}-\frac{q_t}{\lVert q_t\rVert}\right\rVert\le\frac{\lVert q'_t-q_t\rVert}{\lVert q'_t\rVert}+\lVert q_t\rVert\left\lvert\frac{1}{\lVert q'_t\rVert}-\frac{1}{\lVert q_t\rVert}\right\rvert ∥ q t ′ ∥ q t ′ − ∥ q t ∥ q t ≤ ∥ q t ′ ∥ ∥ q t ′ − q t ∥ + ∥ q t ∥ ∥ q t ′ ∥ 1 − ∥ q t ∥ 1 . For the second term, ∣ 1 ∥ q t ′ ∥ − 1 ∥ q t ∥ ∣ = ∣ ∥ q t ∥ − ∥ q t ′ ∥ ∣ ∥ q t ′ ∥ ∥ q t ∥ \left\lvert\frac{1}{\lVert q'_t\rVert}-\frac{1}{\lVert q_t\rVert}\right\rvert=\frac{\left\lvert\lVert q_t\rVert-\lVert q'_t\rVert\right\rvert}{\lVert q'_t\rVert\lVert q_t\rVert} ∥ q t ′ ∥ 1 − ∥ q t ∥ 1 = ∥ q t ′ ∥ ∥ q t ∥ ∣ ∥ q t ∥ − ∥ q t ′ ∥ ∣ . By the reverse triangle inequality, ∣ ∥ q t ∥ − ∥ q t ′ ∥ ∣ ≤ ∥ q t − q t ′ ∥ \left\lvert\lVert q_t\rVert-\lVert q'_t\rVert\right\rvert\le\lVert q_t-q'_t\rVert ∣ ∥ q t ∥ − ∥ q t ′ ∥ ∣ ≤ ∥ q t − q t ′ ∥ . Therefore ∥ q t ∥ ∣ 1 ∥ q t ′ ∥ − 1 ∥ q t ∥ ∣ ≤ ∥ q t ∥ ∥ q t − q t ′ ∥ ∥ q t ′ ∥ ∥ q t ∥ = ∥ q t − q t ′ ∥ ∥ q t ′ ∥ \lVert q_t\rVert\left\lvert\frac{1}{\lVert q'_t\rVert}-\frac{1}{\lVert q_t\rVert}\right\rvert\le\lVert q_t\rVert\frac{\lVert q_t-q'_t\rVert}{\lVert q'_t\rVert\lVert q_t\rVert}=\frac{\lVert q_t-q'_t\rVert}{\lVert q'_t\rVert} ∥ q t ∥ ∥ q t ′ ∥ 1 − ∥ q t ∥ 1 ≤ ∥ q t ∥ ∥ q t ′ ∥ ∥ q t ∥ ∥ q t − q t ′ ∥ = ∥ q t ′ ∥ ∥ q t − q t ′ ∥ . So ∥ q t ′ ∥ q t ′ ∥ − q t ∥ q t ∥ ∥ ≤ 2 ∥ q t ′ − q t ∥ ∥ q t ′ ∥ \left\lVert\frac{q'_t}{\lVert q'_t\rVert}-\frac{q_t}{\lVert q_t\rVert}\right\rVert\le\frac{2\lVert q'_t-q_t\rVert}{\lVert q'_t\rVert} ∥ q t ′ ∥ q t ′ − ∥ q t ∥ q t ≤ ∥ q t ′ ∥ 2 ∥ q t ′ − q t ∥ . Since ∥ q t ′ ∥ ≥ ν / 2 \lVert q'_t\rVert\ge\nu/2 ∥ q t ′ ∥ ≥ ν /2 , we get 1 ∥ q t ′ ∥ ≤ 2 ν \frac{1}{\lVert q'_t\rVert}\le\frac{2}{\nu} ∥ q t ′ ∥ 1 ≤ ν 2 . Hence ∥ u t ′ − u t ∥ = ∥ q t ′ ∥ q t ′ ∥ − q t ∥ q t ∥ ∥ ≤ 4 ν ∥ q t ′ − q t ∥ \lVert u'_t-u_t\rVert=\left\lVert\frac{q'_t}{\lVert q'_t\rVert}-\frac{q_t}{\lVert q_t\rVert}\right\rVert\le\frac{4}{\nu}\lVert q'_t-q_t\rVert ∥ u t ′ − u t ∥ = ∥ q t ′ ∥ q t ′ − ∥ q t ∥ q t ≤ ν 4 ∥ q t ′ − q t ∥ . And by (A.12) we have
∥ u t ′ − u t ∥ ≤ A t η . (32) \lVert u'_t-u_t\rVert\le A_t\eta. \tag*{(32)} ∥ u t ′ − u t ∥ ≤ A t η . (32)
Now compare the CCDS coefficients. We have a t ′ − a t = ( I − P t − 1 ′ ) ( r t − 1 ′ − r t − 1 ) + ( P t − 1 − P t − 1 ′ ) r t − 1 a_t' - a_t = (I - P_{t-1}')(r_{t-1}' - r_{t-1}) + (P_{t-1} - P_{t-1}')r_{t-1} a t ′ − a t = ( I − P t − 1 ′ ) ( r t − 1 ′ − r t − 1 ) + ( P t − 1 − P t − 1 ′ ) r t − 1 . Since the reference trajectory is finite, its residuals are bounded. Together with (A.11), this gives
∥ a t ′ − a t ∥ ≤ C a , t ( ∥ r t − 1 ′ − r t − 1 ∥ + η ) . (33) \lVert a_t' - a_t \rVert\le C_{a,t}(\lVert r_{t-1}' - r_{t-1} \rVert+ \eta). \tag*{(33)} ∥ a t ′ − a t ∥ ≤ C a , t (∥ r t − 1 ′ − r t − 1 ∥ + η ) . (33)
Also α t ′ − α t = ⟨ a t ′ − a t , u t ′ ⟩ + ⟨ a t , u t ′ − u t ⟩ \alpha_t' - \alpha_t = \langle a_t' - a_t, u_t' \rangle+ \langle a_t, u_t' - u_t \rangle α t ′ − α t = ⟨ a t ′ − a t , u t ′ ⟩ + ⟨ a t , u t ′ − u t ⟩ , hence
∣ α t ′ − α t ∣ ≤ C α , t ( ∥ r t − 1 ′ − r t − 1 ∥ + η ) . (34) |\alpha_t' - \alpha_t| \le C_{\alpha,t}(\lVert r_{t-1}' - r_{t-1} \rVert+ \eta). \tag*{(34)} ∣ α t ′ − α t ∣ ≤ C α , t (∥ r t − 1 ′ − r t − 1 ∥ + η ) . (34)
Recall d t , min 2 = ∥ a t ∥ 2 − α t 2 d_{t,\min}^2 = \lVert a_t \rVert^2 - \alpha_t^2 d t , m i n 2 = ∥ a t ∥ 2 − α t 2 . Similarly, ( d t , min ′ ) 2 = ∥ a t ′ ∥ 2 − ( α t ′ ) 2 (d_{t,\min}')^2 = \lVert a_t' \rVert^2 - (\alpha_t')^2 ( d t , m i n ′ ) 2 = ∥ a t ′ ∥ 2 − ( α t ′ ) 2 . Then, ( d t , min ′ ) 2 − d t , min 2 = ( ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ) − ( ( α t ′ ) 2 − α t 2 ) (d_{t,\min}')^2 - d_{t,\min}^2 = (\lVert a_t' \rVert^2 - \lVert a_t \rVert^2) - ((\alpha_t')^2 - \alpha_t^2) ( d t , m i n ′ ) 2 − d t , m i n 2 = (∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ) − (( α t ′ ) 2 − α t 2 ) . Taking absolute values, ∣ ( d t , min ′ ) 2 − d t , min 2 ∣ ≤ ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ + ∣ ( α t ′ ) 2 − α t 2 ∣ |(d_{t,\min}')^2 - d_{t,\min}^2| \le|\lVert a_t' \rVert^2 - \lVert a_t \rVert^2| + |(\alpha_t')^2 - \alpha_t^2| ∣ ( d t , m i n ′ ) 2 − d t , m i n 2 ∣ ≤ ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ + ∣ ( α t ′ ) 2 − α t 2 ∣ . Now ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ = ∣ ( ∥ a t ′ ∥ − ∥ a t ∥ ) ( ∥ a t ′ ∥ + ∥ a t ∥ ) ∣ |\lVert a_t' \rVert^2 - \lVert a_t \rVert^2| = |(\lVert a_t' \rVert- \lVert a_t \rVert)(\lVert a_t' \rVert+ \lVert a_t \rVert)| ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ = ∣ (∥ a t ′ ∥ − ∥ a t ∥) (∥ a t ′ ∥ + ∥ a t ∥) ∣ . Using ∣ ∥ a t ′ ∥ − ∥ a t ∥ ∣ ≤ ∥ a t ′ − a t ∥ |\lVert a_t' \rVert- \lVert a_t \rVert| \le\lVert a_t' - a_t \rVert ∣ ∥ a t ′ ∥ − ∥ a t ∥ ∣ ≤ ∥ a t ′ − a t ∥ , we get ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ ≤ ( ∥ a t ′ ∥ + ∥ a t ∥ ) ∥ a t ′ − a t ∥ |\lVert a_t' \rVert^2 - \lVert a_t \rVert^2| \le(\lVert a_t' \rVert+ \lVert a_t \rVert)\lVert a_t' - a_t \rVert ∣ ∥ a t ′ ∥ 2 − ∥ a t ∥ 2 ∣ ≤ (∥ a t ′ ∥ + ∥ a t ∥) ∥ a t ′ − a t ∥ . Similarly, ∣ ( α t ′ ) 2 − α t 2 ∣ = ∣ α t ′ − α t ∣ ∣ α t ′ + α t ∣ |(\alpha_t')^2 - \alpha_t^2| = |\alpha_t' - \alpha_t||\alpha_t' + \alpha_t| ∣ ( α t ′ ) 2 − α t 2 ∣ = ∣ α t ′ − α t ∣∣ α t ′ + α t ∣ . Along the finite trajectory, ∥ a t ∥ \lVert a_t \rVert ∥ a t ∥ , ∥ a t ′ ∥ \lVert a_t' \rVert ∥ a t ′ ∥ , ∣ α t ∣ |\alpha_t| ∣ α t ∣ , and ∣ α t ′ ∣ |\alpha_t'| ∣ α t ′ ∣ stay bounded for sufficiently small perturbations. Therefore by (A.14) and (A.15) we have
∣ ( d t , min ′ ) 2 − d t , min 2 ∣ ≤ C m , t ( ∥ r t − 1 ′ − r t − 1 ∥ + η ) . (35) |(d_{t,\min}')^2 - d_{t,\min}^2| \le C_{m,t}(\lVert r_{t-1}' - r_{t-1} \rVert+ \eta). \tag*{(35)} ∣ ( d t , m i n ′ ) 2 − d t , m i n 2 ∣ ≤ C m , t (∥ r t − 1 ′ − r t − 1 ∥ + η ) . (35)
Choose the same deterministic root branch in the reference and perturbed problem, for example the minus root: λ t = α t − d t 2 − d t , min 2 \lambda_t = \alpha_t - \sqrt{d_t^2 - d_{t,\min}^2} λ t = α t − d t 2 − d t , m i n 2 , λ t ′ = α t ′ − ( d t ′ ) 2 − ( d t , min ′ ) 2 \lambda_t' = \alpha_t' - \sqrt{(d_t')^2 - (d_{t,\min}')^2} λ t ′ = α t ′ − ( d t ′ ) 2 − ( d t , m i n ′ ) 2 . Then ∣ λ t ′ − λ t ∣ ≤ ∣ α t ′ − α t ∣ + ∣ ( d t ′ ) 2 − ( d t , min ′ ) 2 − d t 2 − d t , min 2 ∣ |\lambda_t' - \lambda_t| \le|\alpha_t' - \alpha_t| + |\sqrt{(d_t')^2 - (d_{t,\min}')^2} - \sqrt{d_t^2 - d_{t,\min}^2}| ∣ λ t ′ − λ t ∣ ≤ ∣ α t ′ − α t ∣ + ∣ ( d t ′ ) 2 − ( d t , m i n ′ ) 2 − d t 2 − d t , m i n 2 ∣ . By the feasibility-margin assumption, d t 2 − d t , min 2 ≥ η 0 2 > 0 d_t^2-d_{t,\min}^2 \ge\eta_0^2 > 0 d t 2 − d t , m i n 2 ≥ η 0 2 > 0 . So if the perturbation is small enough that C m , t ( ∥ r t − 1 ′ − r t − 1 ∥ + η ) ≤ η 0 2 / 2 C_{m,t}(\lVert r_{t-1}' - r_{t-1} \rVert+\eta) \le\eta_0^2/2 C m , t (∥ r t − 1 ′ − r t − 1 ∥ + η ) ≤ η 0 2 /2 , then by (A.16) we have d t 2 − ( d t , min ′ ) 2 ≥ d t 2 − d t , min 2 − ∣ ( d t 2 − ( d t , min ′ ) 2 ) − ( d t 2 − d t , min 2 ) ∣ ≥ η 0 2 − η 0 2 / 2 = η 0 2 / 2 d_t^2-(d_{t,\min}')^2 \ge d_t^2-d_{t,\min}^2-|(d_t^2-(d_{t,\min}')^2)-(d_t^2-d_{t,\min}^2)| \ge\eta_0^2-\eta_0^2/2=\eta_0^2/2 d t 2 − ( d t , m i n ′ ) 2 ≥ d t 2 − d t , m i n 2 − ∣ ( d t 2 − ( d t , m i n ′ ) 2 ) − ( d t 2 − d t , m i n 2 ) ∣ ≥ η 0 2 − η 0 2 /2 = η 0 2 /2 . Thus the perturbed distance equation remains strictly feasible. The map s ↦ s s \mapsto\sqrt{s} s ↦ s is Lipschitz on [ η 0 2 / 2 , ∞ ) [\eta_0^2/2,\infty) [ η 0 2 /2 , ∞ ) . Therefore the square-root Lipschitz estimate gives ∣ ( d t ′ ) 2 − ( d t , min ′ ) 2 − d t 2 − d t , min 2 ∣ ≤ C x ∣ ( d t ′ ) 2 − ( d t , min ′ ) 2 − ( d t 2 − d t , min 2 ) ∣ = C x ∣ ( d t , min ′ ) 2 − d t , min 2 ∣ |\sqrt{(d_t')^2-(d_{t,\min}')^2}-\sqrt{d_t^2-d_{t,\min}^2}| \le C_{\sqrt{\phantom{x}}}|(d_t')^2-(d_{t,\min}')^2-(d_t^2-d_{t,\min}^2)| = C_{\sqrt{\phantom{x}}}|(d_{t,\min}')^2-d_{t,\min}^2| ∣ ( d t ′ ) 2 − ( d t , m i n ′ ) 2 − d t 2 − d t , m i n 2 ∣ ≤ C x ∣ ( d t ′ ) 2 − ( d t , m i n ′ ) 2 − ( d t 2 − d t , m i n 2 ) ∣ = C x ∣ ( d t , m i n ′ ) 2 − d t , m i n 2 ∣ . By (A.15) and (A.16) we obtain
∣ λ t ′ − λ t ∣ ≤ C λ , t ( ∥ r t − 1 ′ − r t − 1 ∥ + η ) . (36) |\lambda_t' - \lambda_t| \le C_{\lambda,t}(\lVert r_{t-1}' - r_{t-1} \rVert+ \eta). \tag*{(36)} ∣ λ t ′ − λ t ∣ ≤ C λ , t (∥ r t − 1 ′ − r t − 1 ∥ + η ) . (36)
Finally, r t ′ − r t = ( r t − 1 ′ − r t − 1 ) − ( λ t ′ u t ′ − λ t u t ) r_t' - r_t = (r_{t-1}' - r_{t-1}) - (\lambda_t'u_t' - \lambda_tu_t) r t ′ − r t = ( r t − 1 ′ − r t − 1 ) − ( λ t ′ u t ′ − λ t u t ) , and λ t ′ u t ′ − λ t u t = ( λ t ′ − λ t ) u t ′ + λ t ( u t ′ − u t ) \lambda_t'u_t' - \lambda_tu_t = (\lambda_t' - \lambda_t)u_t' + \lambda_t(u_t' - u_t) λ t ′ u t ′ − λ t u t = ( λ t ′ − λ t ) u t ′ + λ t ( u t ′ − u t ) . Since ∥ u t ′ ∥ = 1 \lVert u_t' \rVert= 1 ∥ u t ′ ∥ = 1 , λ t \lambda_t λ t is bounded along the finite reference trajectory, and by (A.13) and (A.17), we get ∥ r t ′ − r t ∥ ≤ L t ∥ r t − 1 ′ − r t − 1 ∥ + D t η \lVert r_t' - r_t \rVert\le L_t\lVert r_{t-1}' - r_{t-1}\rVert+ D_t\eta ∥ r t ′ − r t ∥ ≤ L t ∥ r t − 1 ′ − r t − 1 ∥ + D t η . The induction hypothesis then gives
∥ r t ′ − r t ∥ ≤ B t η (37) \lVert r_t' - r_t \rVert\le B_t\eta \tag*{(37)} ∥ r t ′ − r t ∥ ≤ B t η (37)
for a suitable constant B t B_t B t . This closes the induction.
Taking the maximum of the finitely many constants over all samples and all steps, we obtain C C C D S > 0 C_{\mathrm{CCDS}}>0 C CCDS > 0 such that ∥ r ℓ , T ℓ ′ − r ℓ , T ℓ ∥ ≤ C C C D S η \lVert r_{\ell,T_\ell}' - r_{\ell,T_\ell}\rVert\le C_{\mathrm{CCDS}}\eta ∥ r ℓ , T ℓ ′ − r ℓ , T ℓ ∥ ≤ C CCDS η for every ℓ \ell ℓ . The transported perturbed path is an admissible CCDS realizer C C D S D ′ \mathrm{CCDS}_{D'} CCDS D ′ on U ′ = U U'=U U ′ = U . Therefore ϵ p a r a m ( f Ξ , U ′ , C C D S D ′ ) = 1 n ∑ ℓ = 1 n ∥ r ℓ , T ℓ ′ ∥ ≤ 1 n ∑ ℓ = 1 n ∥ r ℓ , T ℓ ∥ + 1 n ∑ ℓ = 1 n ∥ r ℓ , T ℓ ′ − r ℓ , T ℓ ∥ ≤ ϵ p a r a m ( f Ξ , U , C C D S D ) + C C C D S η \epsilon_{\mathrm{param}}(f_{\Xi},U',\mathrm{CCDS}_{D'}) = \frac{1}{n}\sum_{\ell=1}^{n}\lVert r_{\ell,T_\ell}'\rVert\le\frac{1}{n}\sum_{\ell=1}^{n}\lVert r_{\ell,T_\ell}\rVert+ \frac{1}{n}\sum_{\ell=1}^{n}\lVert r_{\ell,T_\ell}'-r_{\ell,T_\ell}\rVert\le\epsilon_{\mathrm{param}}(f_{\Xi},U,\mathrm{CCDS}_{D}) + C_{\mathrm{CCDS}}\eta ϵ param ( f Ξ , U ′ , CCDS D ′ ) = n 1 ∑ ℓ = 1 n ∥ r ℓ , T ℓ ′ ∥ ≤ n 1 ∑ ℓ = 1 n ∥ r ℓ , T ℓ ∥ + n 1 ∑ ℓ = 1 n ∥ r ℓ , T ℓ ′ − r ℓ , T ℓ ∥ ≤ ϵ param ( f Ξ , U , CCDS D ) + C CCDS η . Recalling that η = ∥ G ′ − G ∥ 2 \eta=\lVert G'-G\rVert_2 η = ∥ G ′ − G ∥ 2 gives the desired bound.
How to choose δ 0 \delta_0 δ 0 explicitly: For each trajectory ℓ \ell ℓ and step t t t , the positive nondegeneracy and feasibility margins in the preceding induction provide radii δ 1 , ℓ , t > 0 \delta_{1,\ell,t}>0 δ 1 , ℓ , t > 0 and δ 2 , ℓ , t > 0 \delta_{2,\ell,t}>0 δ 2 , ℓ , t > 0 for which the normalization and root-feasibility arguments remain valid. Indeed, for each trajectory ℓ \ell ℓ and step t t t , let μ ℓ , t : = d ℓ , t 2 − d ℓ , t , min 2 > 0 \mu_{\ell,t}:=d_{\ell,t}^{2}-d_{\ell,t,\min}^{2}>0 μ ℓ , t := d ℓ , t 2 − d ℓ , t , m i n 2 > 0 be the reference feasibility margin. Display (A.12) gives ∥ q ℓ , t ′ − q ℓ , t ∥ ≤ C q , ℓ , t η \lVert q'_{\ell,t}-q_{\ell,t}\rVert\le C_{q,\ell,t}\eta ∥ q ℓ , t ′ − q ℓ , t ∥ ≤ C q , ℓ , t η . Define
δ 1 , ℓ , t : = ν 2 C q , ℓ , t . \delta_{1,\ell,t}:=\frac{\nu}{2C_{q,\ell,t}}. δ 1 , ℓ , t := 2 C q , ℓ , t ν .
Then η < δ 1 , ℓ , t \eta<\delta_{1,\ell,t} η < δ 1 , ℓ , t implies ∥ q ℓ , t ′ − q ℓ , t ∥ < ν / 2 \lVert q'_{\ell,t}-q_{\ell,t}\rVert<\nu/2 ∥ q ℓ , t ′ − q ℓ , t ∥ < ν /2 , preserving the nonzero normalization. After the induction estimate, (A.18) gives
∥ r ℓ , t − 1 ′ − r ℓ , t − 1 ∥ ≤ B ℓ , t − 1 η \lVert r'_{\ell,t-1}-r_{\ell,t-1}\rVert\le B_{\ell,t-1}\eta ∥ r ℓ , t − 1 ′ − r ℓ , t − 1 ∥ ≤ B ℓ , t − 1 η
and by (A.16) we obtain
∣ ( d ℓ , t , min ′ ) 2 − d ℓ , t , min 2 ∣ ≤ C m , ℓ , t ( B ℓ , t − 1 + 1 ) η . \left|(d'_{\ell,t,\min})^{2}-d_{\ell,t,\min}^{2}\right|\le C_{m,\ell,t}(B_{\ell,t-1}+1)\eta. ( d ℓ , t , m i n ′ ) 2 − d ℓ , t , m i n 2 ≤ C m , ℓ , t ( B ℓ , t − 1 + 1 ) η .
Therefore define
δ 2 , ℓ , t : = μ ℓ , t 2 C m , ℓ , t ( B ℓ , t − 1 + 1 ) . \delta_{2,\ell,t}:=\frac{\mu_{\ell,t}}{2C_{m,\ell,t}(B_{\ell,t-1}+1)}. δ 2 , ℓ , t := 2 C m , ℓ , t ( B ℓ , t − 1 + 1 ) μ ℓ , t .
Then η < δ 2 , ℓ , t \eta<\delta_{2,\ell,t} η < δ 2 , ℓ , t implies
d ℓ , t 2 − ( d ℓ , t , min ′ ) 2 ≥ μ ℓ , t 2 > 0 , d_{\ell,t}^{2}-(d'_{\ell,t,\min})^{2}\ge\frac{\mu_{\ell,t}}{2}>0, d ℓ , t 2 − ( d ℓ , t , m i n ′ ) 2 ≥ 2 μ ℓ , t > 0 ,
so the perturbed square-root equation remains feasible. Define
δ j : = min 1 ≤ ℓ ≤ n min 1 ≤ t ≤ T ℓ δ j , ℓ , t , j = 1 , 2 , \delta_j:=\min_{1\le\ell\le n}\ \min_{1\le t\le T_\ell}\delta_{j,\ell,t},\qquad j=1,2, δ j := 1 ≤ ℓ ≤ n min 1 ≤ t ≤ T ℓ min δ j , ℓ , t , j = 1 , 2 ,
and set
δ 0 : = min { γ / 2 , δ 1 , δ 2 } . \delta_0:=\min\{\gamma/2,\delta_1,\delta_2\}. δ 0 := min { γ /2 , δ 1 , δ 2 } .
For a zero-step trajectory, the inner minimum is taken to be + ∞ +\infty + ∞ . ■
Proof of Theorem 3.5 (observable sparse-stability theorem). We first establish a quantitative comparison between the orbit interpolants J k J_k J k and the canonical local-chart operators A k A_k A k , then transfer this comparison to their dictionaries and the corresponding constrained sparse approximation problems.
Step 1: Comparison of the local interpolation operators.
Fix a block D k D_k D k . By assumption,
ker X k ⊆ ker Y k . \ker X_k\subseteq\ker Y_k. ker X k ⊆ ker Y k .
Since X k † X k X_k^{\dagger}X_k X k † X k is the orthogonal projector onto ( ker X k ) ⊥ (\ker X_k)^\perp ( ker X k ) ⊥ , this inclusion implies
Y k = Y k X k † X k . Y_k=Y_kX_k^{\dagger}X_k. Y k = Y k X k † X k .
Indeed, every c ∈ R s k c\in\mathbb{R}^{s_k} c ∈ R s k admits an orthogonal decomposition
c = c 0 + c 1 , c 0 ∈ ker X k , c 1 ∈ ( ker X k ) ⊥ . c=c_0+c_1,\qquad c_0\in\ker X_k,\quad c_1\in(\ker X_k)^\perp. c = c 0 + c 1 , c 0 ∈ ker X k , c 1 ∈ ( ker X k ) ⊥ .
Consequently,
Y k X k † X k c = Y k c 1 = Y k ( c 0 + c 1 ) = Y k c , Y_kX_k^\dagger X_kc = Y_kc_1 = Y_k(c_0+c_1) = Y_kc, Y k X k † X k c = Y k c 1 = Y k ( c 0 + c 1 ) = Y k c ,
because Y k c 0 = 0 Y_kc_0=0 Y k c 0 = 0 .
With A k : = Y k X k † A_k:=Y_kX_k^\dagger A k := Y k X k † , we therefore have A k X k = Y k A_kX_k=Y_k A k X k = Y k . In particular,
A k x k , j = y k , j , j = 1 , … , s k . A_kx_{k,j}=y_{k,j}, \qquad j=1,\ldots,s_k. A k x k , j = y k , j , j = 1 , … , s k .
Moreover,
∥ A k ∥ = ∥ Y k X k † ∥ ≤ ∥ Y k ∥ F ∥ X k † ∥ = ∥ Y k ∥ F σ min + ( X k ) . \lVert A_k\rVert= \lVert Y_kX_k^\dagger\rVert\leq\lVert Y_k\rVert_F\lVert X_k^\dagger\rVert= \frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)}. ∥ A k ∥ = ∥ Y k X k † ∥ ≤ ∥ Y k ∥ F ∥ X k † ∥ = σ m i n + ( X k ) ∥ Y k ∥ F .
Recall that Z k Z_k Z k has full column rank and E k = range ( Z k ) E_k=\operatorname{range}(Z_k) E k = range ( Z k ) . Hence
Z k Z k † = Π E k . Z_kZ_k^\dagger=\Pi_{E_k}. Z k Z k † = Π E k .
Using J k = Y k Z k † = A k X k Z k † J_k=Y_kZ_k^\dagger=A_kX_kZ_k^\dagger J k = Y k Z k † = A k X k Z k † , we obtain
J k − A k Π E k = A k X k Z k † − A k Z k Z k † = A k ( X k − Z k ) Z k † . J_k-A_k\Pi_{E_k}=A_kX_kZ_k^\dagger-A_kZ_kZ_k^\dagger=A_k(X_k-Z_k)Z_k^\dagger. J k − A k Π E k = A k X k Z k † − A k Z k Z k † = A k ( X k − Z k ) Z k † .
Taking operator norms gives
∥ J k − A k Π E k ∥ ≤ ∥ A k ∥ ∥ X k − Z k ∥ F ∥ Z k † ∥ ≤ ∥ Y k ∥ F σ min + ( X k ) σ min ( Z k ) ∥ X k − Z k ∥ F . \begin{aligned}
\lVert J_k-A_k\Pi_{E_k}\rVert
&\leq\lVert A_k\rVert\lVert X_k-Z_k\rVert_F\lVert Z_k^\dagger\rVert\\
&\leq\frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)\sigma_{\min}(Z_k)}\lVert X_k-Z_k\rVert_F.
\end{aligned} ∥ J k − A k Π E k ∥ ≤ ∥ A k ∥ ∥ X k − Z k ∥ F ∥ Z k † ∥ ≤ σ m i n + ( X k ) σ m i n ( Z k ) ∥ Y k ∥ F ∥ X k − Z k ∥ F .
Since
∥ X k − Z k ∥ F = ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1 / 2 , \lVert X_k-Z_k\rVert_F=\left(\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}-z_{k,\ell}\rVert^2\right)^{1/2}, ∥ X k − Z k ∥ F = ( ℓ = 1 ∑ s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1/2 ,
we conclude that
∥ J k − A k Π E k ∥ ≤ ∥ Y k ∥ F σ min + ( X k ) σ min ( Z k ) ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1 / 2 . (38) \lVert J_k-A_k\Pi_{E_k}\rVert\leq\frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)\sigma_{\min}(Z_k)}\left(\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}-z_{k,\ell}\rVert^2\right)^{1/2}. \tag*{(38)} ∥ J k − A k Π E k ∥ ≤ σ m i n + ( X k ) σ m i n ( Z k ) ∥ Y k ∥ F ( ℓ = 1 ∑ s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1/2 . (38)
Step 2: Control by the observable partition score.
For each block, set
δ k : = ∥ Y k ∥ F σ min + ( X k ) σ min ( Z k ) ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1 / 2 . \delta_k:=\frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)\sigma_{\min}(Z_k)}\left(\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}-z_{k,\ell}\rVert^2\right)^{1/2}. δ k := σ m i n + ( X k ) σ m i n ( Z k ) ∥ Y k ∥ F ( ℓ = 1 ∑ s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1/2 .
Then (A.19) reads
∥ J k − A k Π E k ∥ ≤ δ k . \lVert J_k-A_k\Pi_{E_k}\rVert\leq\delta_k. ∥ J k − A k Π E k ∥ ≤ δ k .
By the definition of S ( P ) S(\mathcal{P}) S ( P ) ,
N S ( P ) = ∑ k = 1 K ∑ j = 1 s k ∥ Y k ∥ F σ min + ( X k ) dist ( x k , j , E k ) + ∑ k = 1 K ∑ j = 1 s k ∥ Y k ∥ F ∥ x k , j ∥ σ min + ( X k ) σ min ( Z k ) ( ∑ ℓ = 1 s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1 / 2 = ∑ k = 1 K ∑ j = 1 s k ∥ Y k ∥ F σ min + ( X k ) dist ( x k , j , E k ) + ∑ k = 1 K δ k ∑ j = 1 s k ∥ x k , j ∥ . \begin{aligned}
NS(\mathcal{P}) = \sum_{k=1}^{K}\sum_{j=1}^{s_k}\frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)}\operatorname{dist}(x_{k,j},E_k)
+ \sum_{k=1}^{K}\sum_{j=1}^{s_k}\frac{\lVert Y_k\rVert_F\lVert x_{k,j}\rVert}{\sigma_{\min}^{+}(X_k)\sigma_{\min}(Z_k)}
\left(\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}-z_{k,\ell}\rVert^2\right)^{1/2} \\
&= \sum_{k=1}^{K}\sum_{j=1}^{s_k}\frac{\lVert Y_k\rVert_F}{\sigma_{\min}^{+}(X_k)}\operatorname{dist}(x_{k,j},E_k) + \sum_{k=1}^{K}\delta_k\sum_{j=1}^{s_k}\lVert x_{k,j}\rVert.
\end{aligned} N S ( P ) = k = 1 ∑ K j = 1 ∑ s k σ m i n + ( X k ) ∥ Y k ∥ F dist ( x k , j , E k ) + k = 1 ∑ K j = 1 ∑ s k σ m i n + ( X k ) σ m i n ( Z k ) ∥ Y k ∥ F ∥ x k , j ∥ ( ℓ = 1 ∑ s k ∥ x k , ℓ − z k , ℓ ∥ 2 ) 1/2 = k = 1 ∑ K j = 1 ∑ s k σ m i n + ( X k ) ∥ Y k ∥ F dist ( x k , j , E k ) + k = 1 ∑ K δ k j = 1 ∑ s k ∥ x k , j ∥ .
All terms in the first sum are nonnegative. Therefore,
∑ k = 1 K δ k ∑ j = 1 s k ∥ x k , j ∥ ≤ N S ( P ) . (39) \sum_{k=1}^{K}\delta_k\sum_{j=1}^{s_k}\lVert x_{k,j}\rVert\le NS(\mathcal{P}). \tag*{(39)} k = 1 ∑ K δ k j = 1 ∑ s k ∥ x k , j ∥ ≤ N S ( P ) . (39)
In particular, for every block D k D_k D k ,
δ k ∑ j = 1 s k ∥ x k , j ∥ ≤ N S ( P ) . (40) \delta_k\sum_{j=1}^{s_k}\lVert x_{k,j}\rVert\le NS(\mathcal{P}). \tag*{(40)} δ k j = 1 ∑ s k ∥ x k , j ∥ ≤ N S ( P ) . (40)
Step 3: Stability of the orbit dictionary atoms.
Fix an arbitrary index
r = ( k , j , m ) ∈ I . r=(k,j,m)\in\mathcal{I}. r = ( k , j , m ) ∈ I .
The corresponding atoms in D \mathcal{D} D and D c h a r t \mathcal{D}_{\mathrm{chart}} D chart are
g r = J k W m x k , j , g ~ r = A k Π E k W m x k , j . g_r=J_kW^m x_{k,j},\qquad\widetilde{g}_r=A_k\Pi_{E_k}W^m x_{k,j}. g r = J k W m x k , j , g r = A k Π E k W m x k , j .
Their difference is
g r − g ~ r = ( J k − A k Π E k ) W m x k , j . g_r-\widetilde{g}_r=(J_k-A_k\Pi_{E_k})W^m x_{k,j}. g r − g r = ( J k − A k Π E k ) W m x k , j .
Hence
∥ g r − g ~ r ∥ ≤ ∥ J k − A k Π E k ∥ ∥ W m x k , j ∥ ≤ δ k ∥ W m x k , j ∥ . \lVert g_r-\widetilde{g}_r\rVert\le\lVert J_k-A_k\Pi_{E_k}\rVert\lVert W^m x_{k,j}\rVert\le\delta_k\lVert W^m x_{k,j}\rVert. ∥ g r − g r ∥ ≤ ∥ J k − A k Π E k ∥ ∥ W m x k , j ∥ ≤ δ k ∥ W m x k , j ∥ .
By the definition of κ ( P ) \kappa(\mathcal{P}) κ ( P ) ,
∥ W m x k , j ∥ ≤ κ ( P ) ∑ ℓ = 1 s k ∥ x k , ℓ ∥ . \lVert W^m x_{k,j}\rVert\le\kappa(\mathcal{P})\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}\rVert. ∥ W m x k , j ∥ ≤ κ ( P ) ℓ = 1 ∑ s k ∥ x k , ℓ ∥ .
Therefore,
∥ g r − g ~ r ∥ ≤ κ ( P ) δ k ∑ ℓ = 1 s k ∥ x k , ℓ ∥ ≤ N κ ( P ) S ( P ) , \lVert g_r-\widetilde{g}_r\rVert\le\kappa(\mathcal{P})\delta_k\sum_{\ell=1}^{s_k}\lVert x_{k,\ell}\rVert\le N\kappa(\mathcal{P})S(\mathcal{P}), ∥ g r − g r ∥ ≤ κ ( P ) δ k ℓ = 1 ∑ s k ∥ x k , ℓ ∥ ≤ N κ ( P ) S ( P ) ,
where the final inequality follows from (A.21).
Since r ∈ I r \in\mathcal{I} r ∈ I was arbitrary,
max r ∈ I ∥ g r − g ~ r ∥ ≤ N κ ( P ) S ( P ) . (41) \max_{r\in\mathcal{I}}\lVert g_r-\tilde{g}_r\rVert\le N\kappa(\mathcal{P})S(\mathcal{P}). \tag*{(41)} r ∈ I max ∥ g r − g ~ r ∥ ≤ N κ ( P ) S ( P ) . (41)
This estimate controls the perturbation of every atom in the complete orbit dictionary, not only those corresponding to the selected interpolation depths.
Step 4: Stability of bounded-coefficient sparse synthesis.
Let a ∈ R P a \in\mathbb{R}^{P} a ∈ R P satisfy
∣ { r ∈ I : a r ≠ 0 } ∣ ≤ s , ∑ r ∈ I ∣ a r ∣ ≤ B . \left|\{r \in\mathcal{I}:a_r\ne0\}\right|\le s,\qquad\sum_{r\in\mathcal{I}}|a_r|\le B. ∣ { r ∈ I : a r = 0 } ∣ ≤ s , r ∈ I ∑ ∣ a r ∣ ≤ B .
The corresponding realizations are
S D ( a ) = ∑ r ∈ I a r g r , S D c h a r t ( a ) = ∑ r ∈ I a r g ~ r . S_{\mathcal{D}}(a)=\sum_{r\in\mathcal{I}}a_rg_r,\qquad S_{\mathcal{D}_{\mathrm{chart}}}(a)=\sum_{r\in\mathcal{I}}a_r\tilde{g}_r. S D ( a ) = r ∈ I ∑ a r g r , S D chart ( a ) = r ∈ I ∑ a r g ~ r .
Consequently,
∥ S D ( a ) − S D c h a r t ( a ) ∥ = ∥ ∑ r ∈ I a r ( g r − g ~ r ) ∥ ≤ ∑ r ∈ I ∣ a r ∣ ∥ g r − g ~ r ∥ ≤ ( ∑ r ∈ I ∣ a r ∣ ) max r ∈ I ∥ g r − g ~ r ∥ ≤ B N κ ( P ) S ( P ) , \begin{aligned}
\lVert S_{\mathcal{D}}(a)-S_{\mathcal{D}_{\mathrm{chart}}}(a)\rVert
&=\left\lVert\sum_{r\in\mathcal{I}}a_r(g_r-\tilde{g}_r)\right\rVert\\
&\le\sum_{r\in\mathcal{I}}|a_r|\lVert g_r-\tilde{g}_r\rVert\\
&\le\left(\sum_{r\in\mathcal{I}}|a_r|\right)\max_{r\in\mathcal{I}}\lVert g_r-\tilde{g}_r\rVert\\
&\le BN\kappa(\mathcal{P})S(\mathcal{P}),
\end{aligned} ∥ S D ( a ) − S D chart ( a )∥ = r ∈ I ∑ a r ( g r − g ~ r ) ≤ r ∈ I ∑ ∣ a r ∣ ∥ g r − g ~ r ∥ ≤ ( r ∈ I ∑ ∣ a r ∣ ) r ∈ I max ∥ g r − g ~ r ∥ ≤ B N κ ( P ) S ( P ) ,
by (A.22). Thus
∥ S D ( a ) − S D c h a r t ( a ) ∥ ≤ B N κ ( P ) S ( P ) (42) \lVert S_{\mathcal{D}}(a)-S_{\mathcal{D}_{\mathrm{chart}}}(a)\rVert\le BN\kappa(\mathcal{P})S(\mathcal{P}) \tag*{(42)} ∥ S D ( a ) − S D chart ( a )∥ ≤ B N κ ( P ) S ( P ) (42)
uniformly over every coefficient vector satisfying the prescribed constraints.
Step 5: Stability of optimal sparse realization errors.
Fix y ∈ R C y \in\mathbb{R}^{C} y ∈ R C , and write
A s , B : = { a ∈ R P : ∣ { r ∈ I : a r ≠ 0 } ∣ ≤ s , ∑ r ∈ I ∣ a r ∣ ≤ B } . \mathcal{A}_{s,B}:=\left\{a\in\mathbb{R}^{P}:\left|\{r\in\mathcal{I}:a_r\ne0\}\right|\le s,\ \sum_{r\in\mathcal{I}}|a_r|\le B\right\}. A s , B := { a ∈ R P : ∣ { r ∈ I : a r = 0 } ∣ ≤ s , r ∈ I ∑ ∣ a r ∣ ≤ B } .
For every a ∈ A s , B a \in\mathcal{A}_{s,B} a ∈ A s , B , the reverse triangle inequality and (A.23) give
∥ y − S D ( a ) ∥ − ∥ y − S D c h a r t ( a ) ∥ ≤ ∥ S D ( a ) − S D c h a r t ( a ) ∥ ≤ B N κ ( P ) S ( P ) . \lVert y-S_{\mathcal{D}}(a)\rVert-\lVert y-S_{\mathcal{D}_{\mathrm{chart}}}(a)\rVert
\le\lVert S_{\mathcal{D}}(a)-S_{\mathcal{D}_{\mathrm{chart}}}(a)\rVert
\le BN\kappa(\mathcal{P})S(\mathcal{P}). ∥ y − S D ( a )∥ − ∥ y − S D chart ( a )∥ ≤ ∥ S D ( a ) − S D chart ( a )∥ ≤ B N κ ( P ) S ( P ) .
In particular,
∥ y − S D ( a ) ∥ ≤ ∥ y − S D c h a r t ( a ) ∥ + B N κ ( P ) S ( P ) \lVert y-S_{\mathcal{D}}(a)\rVert\le\lVert y-S_{\mathcal{D}_{\mathrm{chart}}}(a)\rVert+BN\kappa(\mathcal{P})S(\mathcal{P}) ∥ y − S D ( a )∥ ≤ ∥ y − S D chart ( a )∥ + B N κ ( P ) S ( P )
for every a ∈ A s , B a \in\mathcal{A}_{s,B} a ∈ A s , B .
Taking the infimum over this common admissible set yields
e s , B ( y ; D ) ≤ e s , B ( y ; D c h a r t ) + B N κ ( P ) S ( P ) . e_{s,B}(y;\mathcal{D}) \le e_{s,B}(y;\mathcal{D}_{\mathrm{chart}}) + BN_{\kappa}(\mathcal{P})\mathcal{S}(\mathcal{P}). e s , B ( y ; D ) ≤ e s , B ( y ; D chart ) + B N κ ( P ) S ( P ) .
Interchanging the roles of the two dictionaries gives
e s , B ( y ; D c h a r t ) ≤ e s , B ( y ; D ) + B N κ ( P ) S ( P ) . e_{s,B}(y;\mathcal{D}_{\mathrm{chart}}) \le e_{s,B}(y;\mathcal{D}) + BN_{\kappa}(\mathcal{P})\mathcal{S}(\mathcal{P}). e s , B ( y ; D chart ) ≤ e s , B ( y ; D ) + B N κ ( P ) S ( P ) .
Combining the two inequalities, we conclude that
∣ e s , B ( y ; D ) − e s , B ( y ; D c h a r t ) ∣ ≤ B N κ ( P ) S ( P ) . \left|e_{s,B}(y;\mathcal{D}) - e_{s,B}(y;\mathcal{D}_{\mathrm{chart}})\right| \le BN_{\kappa}(\mathcal{P})\mathcal{S}(\mathcal{P}). ∣ e s , B ( y ; D ) − e s , B ( y ; D chart ) ∣ ≤ B N κ ( P ) S ( P ) .
Since y y y , s s s , and B B B were arbitrary, the assertion follows. ■
Experimental configurations
Data splits, preprocessing, and repetition
Gas Sensor Drift batches are concatenated in batch order and split at 80%: training subsets are sampled from the first part, and the final 20% is held out. ISOLET uses the first 6,238 examples for training and the remaining 1,559 for testing. MNIST uses the standard 60,000-example training pool, with the first 48,000 forming the training pool and the last 12,000 held out, kept untouched during model fitting and shared by all methods. MNIST pixels are divided by 255 before preprocessing.
Standardization, randomized PCA (random state 0), and subsequent coordinate standardization are fitted on the selected training subset and then applied to held-out data. Gas at 128 features omits PCA. The main runs use subset seeds 13–17 and construction seeds 1000–1004. The Gas and ISOLET heads use the corresponding construction seed; the MNIST head uses seed 1000 in all five runs. Consequently, the reported standard deviations concern the specified repeated training and construction procedure, not independent test splits.
This matched preprocessing protocol is essential for interpretation: differences among the feature-based methods cannot be attributed to different input representations or access to additional training information. The experiments therefore compare how each method uses the same compressed geometry, while the orbit method additionally exposes the role of scaffold discovery and constructive realization.
The anchor budget is a discovery budget, not the amount of data available to the final predictor. After the scaffold is selected, all designated training targets are projected onto that scaffold, realized by Phase 2, and used to train the Phase 3 coefficient head. This distinction separates structural discovery from subsequent coefficient learning.
Construction and coefficient prediction
The main predictive runs fix w j = 0.5 1 / d w_j = 0.5^{1/d} w j = 0. 5 1/ d , so the cycle product is 0.5; these runs do not learn the shift weights. Up to five disjoint farthest-first anchor candidates are considered. A greedy orbit-independence test uses threshold 0.1, followed by splitting large blocks. Target block sizes are ⌈ d / 3 ⌉ \lceil d/3\rceil ⌈ d /3 ⌉ for PCA Gas and MNIST, ⌈ d / 12 ⌉ \lceil d/12\rceil ⌈ d /12 ⌉ for raw Gas, and ⌈ d / 7 ⌉ \lceil d/7\rceil ⌈ d /7 ⌉ for ISOLET. Candidate selection uses training projection error, with an early stopping threshold of 10 − 7 10^{-7} 1 0 − 7 . The local chart score uses normalized scalar class indices as a partition heuristic; the block interpolants used for synthesis use one-hot class targets.
Table B.1. Main construction settings. PCA variance is approximate and varies slightly with the selected subset; 100% for raw Gas denotes omission of PCA. Anchor counts are the actual integer counts. An anchor budget limits dictionary construction: all selected training labels are used for target projection, realization, and prediction.
Interpolants use a pseudoinverse of the regularized normal matrix with ridge 10 − 6 10^{-6} 1 0 − 6 in float32. The synthesis dictionary contains all d d d recorded depths of each anchor under its own block interpolant, with P = d ∣ Ξ s u b ∣ P = d|\Xi_{\mathrm{sub}}| P = d ∣ Ξ sub ∣ . Phase 2 primarily uses the trivial-reference distance-equation solver with γ = 0 \gamma= 0 γ = 0 , alignment threshold 0.99, batch size 256, and an iteration cap of P P P . Its stopping threshold is 10 − 7 ∥ Π U y ∥ + 10 − 10 10^{-7}\|\Pi_U y\| + 10^{-10} 1 0 − 7 ∥ Π U y ∥ + 1 0 − 10 . Final certificate support in the main summaries counts coefficients with absolute value greater than 10 − 8 10^{-8} 1 0 − 8 .
The primary Phase 2 configuration deliberately uses the minimal-deviation boundary, making it a residual-collapse reference and explaining the near-zero realization errors reported above. The interior CCDS experiments are separate diagnostics: they retain the same dictionary while testing the additional path-control freedom created by prescribing nonminimal feasible deviations.
The global head has two hidden layers of the same width, GELU activations and LayerNorm, with dropout 0.15 after the first hidden layer. Its linear output has P P P coefficient coordinates. For a fit set F F F , the implemented objective is
L F ( θ ) = 1 ∣ F ∣ ∑ i ∈ F [ CE ( G α θ ( x i ) , y i ) + λ c o e f f ∥ α θ ( x i ) − β i ∥ 2 + λ o u t C ∥ G α θ ( x i ) − c i ∥ 2 2 + λ 1 P ∥ α θ ( x i ) ∥ 1 ] . \mathcal{L}_{F}(\theta) = \frac{1}{|F|}\sum_{i\in F}\left[\operatorname{CE}(G_{\alpha_\theta}(x_i), y_i) + \lambda_{\mathrm{coeff}}\|\alpha_\theta(x_i)-\beta_i\|_2
+ \frac{\lambda_{\mathrm{out}}}{C}\|G_{\alpha_\theta}(x_i)-c_i\|_2^2 + \frac{\lambda_1}{P}\|\alpha_\theta(x_i)\|_1\right]. L F ( θ ) = ∣ F ∣ 1 i ∈ F ∑ [ CE ( G α θ ( x i ) , y i ) + λ coeff ∥ α θ ( x i ) − β i ∥ 2 + C λ out ∥ G α θ ( x i ) − c i ∥ 2 2 + P λ 1 ∥ α θ ( x i ) ∥ 1 ] .
The coefficient discrepancy is an unsquared Euclidean norm. AdamW uses batches of 128. After construction and realization on the full selected training set, 15% is reserved for head validation and 85% for head fitting. Validation therefore selects the extension head conditional on an already fitted representation. Checkpoints are evaluated every 25 epochs and at the final epoch, using the validation objective without its ℓ 1 \ell_1 ℓ 1 term. Validation and test coefficients with magnitude at most 10 − 5 10^{-5} 1 0 − 5 are set to zero before synthesis.
The coefficient head is therefore supervised by the constructive certificate itself, while the output-consistency term keeps its synthesized prediction aligned with the realized target. The resulting predictor is not an unconstrained classifier attached to the scaffold; it is an extension of the sparse orbit-coordinate rule produced by Phase 2.
Table B.2. Main coefficient-head configurations. Weight decay and ( λ c o e f f , λ o u t , λ 1 ) (\lambda_{\mathrm{coeff}}, \lambda_{\mathrm{out}}, \lambda_1) ( λ coeff , λ out , λ 1 ) are 10 − 2 10^{-2} 1 0 − 2 and ( 0 , 1 , 10 − 2 ) (0,1,10^{-2}) ( 0 , 1 , 1 0 − 2 ) for Gas, 10 − 3 10^{-3} 1 0 − 3 and ( 0 , 2 , 0 ) (0,2,0) ( 0 , 2 , 0 ) for ISOLET, and 10 − 2 10^{-2} 1 0 − 2 and ( 10 − 2 , 1 , 0 ) (10^{-2},1,0) ( 1 0 − 2 , 1 , 0 ) for MNIST.
Synthetic geometry and realization diagnostics
In the weak alignment and matched rank tests we use 900 synthetic inputs of dimension 10, seven classes, generator seed 4, and a 500-example training subset. Inputs have noisy class directions and sample-wise rotations. A normalized random readout B B B maps the operator response to seven outputs; the operator C C C has logarithmically spaced singular values from 1 to 10 − 4 10^{-4} 1 0 − 4 and spectral norm one. Readout seed is 456 and operator seed is 103. The block dictionary is constructed from one-hot labels obtained from these responses, whereas projection and realization diagnostics evaluate the continuous target B C x BCx B C x . The weak-alignment run uses 35 anchors, 14 blocks, and 350 atoms. Shift weights are optimized for 100 Adam steps at learning rate 10 − 3 10^{-3} 1 0 − 3 , starting from 0.5 1 / d 0.5^{1/d} 0. 5 1/ d . The nested solver uses seven innovations and alignment threshold 0.8. On weakly aligned steps, d t = max { d t , min , γ ∥ a t ∥ } d_t = \max\{d_{t,\min},\gamma\lVert a_t\rVert\} d t = max { d t , m i n , γ ∥ a t ∥} , clipped at ∥ a t ∥ \lVert a_t\rVert ∥ a t ∥ ; other steps use the boundary up to numerical tolerance. The minus root is used. The matched-rank test uses ten anchor seeds 101–110 and twenty random references at each rank one through six. Selection uses the leading singular direction of the training responses compressed to the remaining candidate space.
The operator-family test uses a near-parallel union of six three-dimensional subspaces in 35 dimensions, with class perturbation scale 0.02 and noise scale 0.05. Generator seed is 4. A 2,000-example training subset is standardized and reduced to 15 PCA coordinates, retaining approximately 98.2% of variance. A single random 60-anchor construction has 30 two-anchor blocks and 900 atoms. Its shift is fitted for 100 Adam steps at 10 − 3 10^{-3} 1 0 − 3 , initialized at one; the resulting dictionary is reused across all eight response operators. The families are an ill-conditioned SVD operator, identity, orthogonal, rank-five, spiked, sparse, Toeplitz, and an anisotropic diagonal operator.
The nested solver uses six innovations, alignment threshold 0.8, and γ = 0.05 \gamma= 0.05 γ = 0.05 . If b = 10 − 3 ∥ Π U y ∥ b = 10^{-3}\lVert\Pi_U y\rVert b = 1 0 − 3 ∥ Π U y ∥ and B t − 1 B_{t-1} B t − 1 is the accumulated squared coordinate discrepancy, its weak-alignment step allocates
δ t = min { γ ∣ a t ∣ , max { 0 , b 2 − B t − 1 } 6 − t + 1 } , d t 2 = d t , min 2 + δ t 2 . \delta_t = \min\left\{\gamma\lvert a_t\rvert,\sqrt{\frac{\max\{0,b^2-B_{t-1}\}}{6-t+1}}\right\}, \qquad d_t^2 = d_{t,\min}^2 + \delta_t^2. δ t = min { γ ∣ a t ∣ , 6 − t + 1 max { 0 , b 2 − B t − 1 } } , d t 2 = d t , m i n 2 + δ t 2 .
Dictionary structure and interpolation variants
The waveform task uses four Fourier motifs in dimension 32 with seven frequencies, random cyclic shifts, amplitudes in [ 0.7 , 1.3 ] [0.7,1.3] [ 0.7 , 1.3 ] , and shared random frequency-wise rotations of the targets. Each seed 101–110 generates 720 fit examples and 900 held-out examples, split into 150 validation and 750 test examples. Each 20- or 28-anchor dictionary uses one block, fixed cycle product 0.5, and ridge 10 − 6 10^{-6} 1 0 − 6 . The unstructured arm draws Gaussian directions within the orbit dictionary’s numerical span, using relative singular-value threshold 10 − 5 10^{-5} 1 0 − 5 , matches each row norm, and preserves the selected-depth anchor rows.
Three greedy updates form the training realization targets. Both proxy heads have two width-128 GELU/LayerNorm layers and dropout 0.15, and are trained for 200 epochs with AdamW, learning rate 10 − 3 10^{-3} 1 0 − 3 , weight decay 10 − 2 10^{-2} 1 0 − 2 , and batch size 128. The proxy loss is target MSE plus 0.25 times MSE to the three-step realization. Checkpoints minimize held-out validation MSE. Predictions use two MP updates on the proxy output. The direct MLP uses the same architecture and optimization settings with target MSE alone.
The interpolation comparison has 15,000 synthetic examples with five informative Gaussian coordinates, 44 correlated nuisance coordinates, and one mildly aligned spurious feature. The split is 12,000 training and 3,000 clean-test examples. Clean labels are the sign of the informative linear score. Exactly 0%, 20%, or 40% of training labels are flipped, with corruption seed 42 + 1000 q 42 + 1000q 42 + 1000 q at fraction q q q ; test labels are unchanged. Both arms use PCA dimension 10, 120 anchors, five paired subset seeds 13–17, and a width-51 global head trained for 300 epochs at 10 − 3 10^{-3} 1 0 − 3 , with weight decay 10 − 2 10^{-2} 1 0 − 2 and ( λ c o e f f , λ o u t , λ 1 ) = ( 1 , 1 , 0.1 ) (\lambda_{\mathrm{coeff}}, \lambda_{\mathrm{out}}, \lambda_1) = (1, 1, 0.1) ( λ coeff , λ out , λ 1 ) = ( 1 , 1 , 0.1 ) . The exact arm uses an unregularized pseudoinverse with a constructive correction fallback. The relaxed arm uses ridge 10 − 3 10^{-3} 1 0 − 3 . Each arm optimizes shift weights for 100 Adam steps at 10 − 3 10^{-3} 1 0 − 3 .
Discovery-budget configurations and values
Both sweeps use subset seed 13 and construction seed 1000, with one run per budget. Gas uses 3,000 training examples and ten PCA coordinates, retaining approximately 95.0% of variance. MNIST uses 5,000 training examples and twenty PCA coordinates, retaining approximately 41.9%. All heads use batches of 128 and train for 300 epochs, with λ o u t = 1 \lambda_{\mathrm{out}} = 1 λ out = 1 .
For Gas, the hidden width is 51 and weight decay is 10 − 2 10^{-2} 1 0 − 2 . Budgets 1%, 3%, and 5% use learning rate 10 − 3 10^{-3} 1 0 − 3 and λ c o e f f = 1 \lambda_{\mathrm{coeff}} = 1 λ coeff = 1 ; 7% uses the same rate and λ c o e f f = 0.2 \lambda_{\mathrm{coeff}} = 0.2 λ coeff = 0.2 ; 10% and 15% use 10 − 4 10^{-4} 1 0 − 4 and λ c o e f f = 0 \lambda_{\mathrm{coeff}} = 0 λ coeff = 0 . All use λ 1 = 0.1 \lambda_1 = 0.1 λ 1 = 0.1 . Shift optimization uses 100 Adam steps at 10 − 3 10^{-3} 1 0 − 3 , initialized at 0.5 1 / d 0.5^{1/d} 0. 5 1/ d .
For MNIST, learning rate is 10 − 3 10^{-3} 1 0 − 3 throughout. Budgets 1%, 3%, and 5% use width 64, weight decay 10 − 2 10^{-2} 1 0 − 2 , λ c o e f f = 1 \lambda_{\mathrm{coeff}} = 1 λ coeff = 1 , and λ 1 = 0.1 \lambda_1 = 0.1 λ 1 = 0.1 . At 7%, λ c o e f f = 0.15 \lambda_{\mathrm{coeff}} = 0.15 λ coeff = 0.15 . At 10%, width increases to 156, weight decay decreases to 10 − 3 10^{-3} 1 0 − 3 , and both coefficient tracking and ℓ 1 \ell_1 ℓ 1 penalties are removed. Shift learning uses 25 Adam steps at 10 − 3 10^{-3} 1 0 − 3 , relative-weight penalty 0.01, and
w j = exp ( log ( 0.5 ) d + θ j − 1 d ∑ k = 0 d − 1 θ k ) w_j = \exp\left(\frac{\log(0.5)}{d} + \theta_j - \frac{1}{d}\sum_{k=0}^{d-1}\theta_k\right) w j = exp ( d log ( 0.5 ) + θ j − d 1 k = 0 ∑ d − 1 θ k )
which fixes the cycle product at 0.5.
Baselines
The common baselines use logistic regression with at most 1,000 iterations, a 100-tree random forest, an RBF SVM with C = 1 C = 1 C = 1 and scale-based bandwidth, and histogram gradient boosting with learning rate 0.1. The MLP uses the corresponding head’s two hidden widths, ReLU, learning rate 10 − 3 10^{-3} 1 0 − 3 , a 10% early-stopping validation fraction, and at most 2,000 iterations. It is not a complete architecture or parameter-count match. Remaining unspecified parameters use the notebook’s library defaults.
ISOLET additionally uses a Nyström RBF feature map with 800 components, bandwidth parameter 0.002, and ridge classifier regularization 0.01, and a distance-weighted 15-nearest-neighbor classifier. Their accuracies are 91.20 ± 0.05 % 91.20 \pm0.05\% 91.20 ± 0.05% and 86.79 ± 0.00 % 86.79 \pm0.00\% 86.79 ± 0.00% at 25 features, and 92.89 ± 0.20 % 92.89 \pm0.20\% 92.89 ± 0.20% and 87.94 ± 0.00 % 87.94 \pm0.00\% 87.94 ± 0.00% at 100 features. Gas additionally reports CORAL logistic regression at 63.64 ± 2.97 % 63.64 \pm2.97\% 63.64 ± 2.97% and 69.31 ± 1.19 % 69.31 \pm1.19\% 69.31 ± 1.19% . The recorded delay-ridge reference reaches 65.36 ± 3.78 % 65.36 \pm3.78\% 65.36 ± 3.78% and 73.86 ± 2.65 % 73.86 \pm2.65\% 73.86 ± 2.65% , exceeding WBSNN in the raw-feature setting; however, it forms training delays after random subset ordering, so it is not a chronological temporal comparison. The corresponding Hankel/LDA reference reaches 34.13 ± 5.89 % 34.13 \pm5.89\% 34.13 ± 5.89% and 49.93 ± 1.90 % 49.93 \pm1.90\% 49.93 ± 1.90% .
The MNIST CNN uses two 3 × 3 3 \times3 3 × 3 convolutional layers with 16 and 32 channels, batch normalization, ReLU, and 2 × 2 2 \times2 2 × 2 max pooling, followed by a width-128 hidden layer and dropout 0.5. It is trained on raw images for seven epochs with Adam, learning rate 10 − 3 10^{-3} 1 0 − 3 , and batch size 32.