betaFeedback

WorksComputer Science

A Constructive Orbit-Based Theory of Learnability

Abstract

We develop a finite-dimensional orbit framework for constructing data-adapted dictionaries, sparse realizations, and predictive extensions. The method uses wrapped weighted shifts to generate orbit dictionaries and local interpolation maps from independent orbit representatives, turning the learning problem into three explicit tasks: scaffold discovery, sparse realization on the discovered dictionary, and prediction through learned sparse coordinates. We introduce CCDS as the main constructive ingredient: a deviation-controlled sparse realization procedure that recovers MP/OMP-type behavior at the minimal-deviation boundary while allowing feasible interior paths with prescribed residual geometry that is inaccessible to MP/OMP. We prove generic orbit independence, exact block interpolation with norm control, observable bounds on sparse approximation distortion, sparse realization guarantees on selected supports, and fixed-path stability under admissible perturbations of the block interpolants. These results connect sparse approximation, interpolation, and finite-dimensional operator dynamics through the construction and analysis of data-induced orbit dictionaries. Experiments on synthetic geometry, controlled realization tests, and standard classification benchmarks show that selected orbit scaffolds have substantially better matched-rank projection behavior than random orbit or unstructured alternatives, that CCDS attains near-zero realization error at the minimal-deviation boundary, and that predictors trained from the sparse CCDS certificates give competitive performance.

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 JkWmxk,jJ_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⊆RCU \subseteq\mathbb{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 Ξtrain={(xi,yi)}i=1n⊆Rd×RC\Xi_{\mathrm{train}} = \{(x_i,y_i)\}_{i=1}^{n} \subseteq\mathbb{R}^{d} \times\mathbb{R}^{C} be a finite input–target dataset generated by an empirical target map fΞ:Rd→RCf_{\Xi}:\mathbb{R}^{d} \to\mathbb{R}^{C}, so that fΞ(xi):=yif_{\Xi}(x_i) := y_i. We define the empirical mean seminorm for any map hh evaluated on the dataset by ∥h∥Ξ:=1n∑i=1n∥h(xi)∥2\lVert h\rVert_{\Xi} := \frac{1}{n}\sum_{i=1}^{n}\lVert h(x_i)\rVert_2.

Let Ξsub⊆Ξtrain\Xi_{\mathrm{sub}} \subseteq\Xi_{\mathrm{train}} be the anchor subset used for scaffold construction. We write

Ξsub=D1⊔⋯⊔DK,Dk={(xk,j,yk,j)}j=1sk.(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)}

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 dd. This provides the structured orbit backbone used throughout the framework.

Definition 3.1 (The wrapped weighted backward shift). A wrapped weighted backward shift W:Rd→RdW:\mathbb{R}^{d} \to\mathbb{R}^{d} is defined as Wej=wjej−1(modd)We_j = w_je_{j-1}\pmod d, where e0,…,ed−1e_0,\ldots,e_{d-1} is the canonical basis and wj≠0w_j \ne0.

Even within a block, the original assignments xk,j↦yk,jx_{k,j} \mapsto y_{k,j} need not admit a common linear interpolant. We therefore use anchor-dependent iterates of WW to seek orbit representatives on which a shared linear readout can realize the prescribed targets. Specifically, in the next subsection, for an anchor block DkD_k, we seek depths Lk,jL_{k,j} and a linear operator JkJ_k such that

xk,j⟼WLk,jxk,j⟼JkWLk,jxk,j=yk,j.x_{k,j} \longmapsto W^{L_{k,j}}x_{k,j} \longmapsto J_kW^{L_{k,j}}x_{k,j} = y_{k,j}.

The two operators have then distinct roles: WW generates the orbit geometry, while JkJ_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 Ξsub\Xi_{\mathrm{sub}}.

Lemma 3.2. For every m≥1m \ge1 and z∈Rdz \in\mathbb{R}^{d},

(Wmz)i−1=(∏r=0m−1w(i+r) mod d)z(i+m−1) mod 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.

The proof is deferred to Subsection A.1. For intuition, the reader may view WLxW^{L}x as a shift-and-scale transformation of xx, beginning at the LL-th entry and preserving the cyclic order of the components modulo dd.

Set ρ:=∏j=0d−1wj\rho:= \prod_{j=0}^{d-1}w_j. Since every coordinate crosses every weight exactly once in dd iterates, Wd=ρIRdW^d=\rho I_{\mathbb{R}^d}. Hence:

Lemma 3.3. If L=md+rL=md+r, 0≤r<d0\le r<d, then WL=ρmWrW^L=\rho^mW^r.

Blockwise orbit interpolation

Fix a partition as in (3.1) with sk≤ds_k\le d for every kk. We call the partition orbit-admissible for WW if, for each 1≤k≤K1\le k\le K, there exist depths

Lk,1,…,Lk,sk∈{0,…,d−1}L_{k,1},\ldots,L_{k,s_k}\in\{0,\ldots,d-1\}

such that the orbit representatives

zk,j:=WLk,jxk,j,j=1,…,sk,z_{k,j}:=W^{L_{k,j}}x_{k,j},\qquad j=1,\ldots,s_k,

are linearly independent. In what follows, assume that the partition is orbit-admissible and choose such depths for each block.

Define

Zk:=[zk,1⋯zk,sk]∈Rd×sk,Yk:=[yk,1⋯yk,sk]∈RC×sk.(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)}

Since ZkZ_k has full column rank, the canonical interpolant Jk:=YkZk†∈L(Rd,RC)J_k:=Y_kZ_k^\dagger\in\mathcal{L}(\mathbb{R}^{d},\mathbb{R}^{C}) satisfies

JkWLk,jxk,j=Jkzk,j=yk,j,j=1,…,sk.(3)J_kW^{L_{k,j}}x_{k,j}=J_kz_{k,j}=y_{k,j},\qquad j=1,\ldots,s_k. \tag*{(3)}

Moreover, ∥Jk∥≤∥Yk∥F/σmin⁡(Zk)\lVert J_k\rVert\le\lVert Y_k\rVert_F/\sigma_{\min}(Z_k), so the conditioning of the orbit matrix ZkZ_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=(xi,yi)i=1s⊂Rd×RCD = (x_i, y_i)_{i=1}^{s} \subset\mathbb{R}^{d} \times\mathbb{R}^{C}, s≤ds \le d, and let Ω:=(R\{0})d\Omega:= (\mathbb{R}\backslash\{0\})^{d}. For each w=(w0,…,wd−1)∈Ωw = (w_0, \ldots, w_{d-1}) \in\Omega, let WwW_w denote the wrapped weighted backward shift determined by ww. Define zi:=WwLixiz_i := W_w^{L_i}x_i and

ΩD:={w∈Ω:∃L1,…,Ls∈{0,…,d−1} such that zi∉span⁡{z1,…,zi−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\}.

If ΩD≠∅\Omega_D \ne\varnothing, then ΩD\Omega_D is open and dense in Ω\Omega. Moreover, Ω\ΩD\Omega\backslash\Omega_D has Lebesgue measure zero.

Proof sketch. For each depth tuple L=(L1,…,Ls)L = (L_1,\ldots,L_s), the entries and s×ss \times s minors of

ML(w)=[WwL1x1 ⋯ WwLsxs]M_L(w) = [W_w^{L_1}x_1\ \cdots\ W_w^{L_s}x_s]

are polynomial in ww. Thus ΩD\Omega_D is a finite union of polynomial nonvanishing sets and is open. If ΩD≠∅\Omega_D \ne\varnothing, some minor pp is nonzero at an admissible weight and hence is not the zero polynomial. Since

References

  1. [1]M. Aharon, M. Elad, and A. Bruckstein, K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation, IEEE Transactions on Signal Processing, 54 (2006), pp. 4311–4322.DOI
  2. [2]O. Azencot, N. B. Erichson, V. Lin, and M. W. Mahoney, Forecasting sequential data using consistent Koopman autoencoders, in Proceedings of the 37th International Conference on Machine Learning (ICML), vol. 119, PMLR, 2020, pp. 475–485.arxiv.org/abs/2003.02236
  3. [3]A. B. Bakushinsky and M. Y. Kokurin, Iterative Methods for Approximate Solution of Inverse Problems, vol. 577 of Mathematics and Its Applications, Springer, 2004.DOI
  4. [4]F. Bayart and E. Matheron, Dynamics of Linear Operators, vol. 179 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 2009.DOI
  5. [5]S. N. Bernstein, On the inverse problem of the theory of the best approximation of continuous functions, in Collected Works, vol. II, Academy of Sciences of the USSR, 1954, pp. 292–294. (Original work from 1938.).
  6. [6]S. L. Brunton, M. Budisic, E. Kaiser, and J. N. Kutz, Modern Koopman Theory for Dynamical Systems, SIAM Review, 64 (2022), pp. 229–340.arxiv.org/abs/2102.12086
  7. [7]J. B. Conway, A Course in Functional Analysis, vol. 96 of Graduate Texts in Mathematics, Springer, New York, second ed., 1990.
  8. [8]R. A. DeVore and V. N. Temlyakov, Some remarks on greedy algorithms, Adv Comput Math, 5 (1996), pp. 173–187.DOI
  9. [9]R. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge/United Kingdom, 2nd ed., 2012.
  10. [10]L. Lu, P. Jin, G. Pang, Z. Zhang, and G. E. Karniadakis, Learning nonlinear operators via DeepONet based on the universal approximation theorem of operators, Nat Mach Intell, 3 (2021), p. 218–229.
  11. [11]B. Lusch, J. N. Kutz, and S. L. Brunton, Deep learning for universal linear embeddings of nonlinear dynamics, Nature Communications, 9 (2018).DOI
  12. [12]J. Mairal, F. Bach, J. Ponce, and G. Sapiro, Online learning for matrix factorization and sparse coding, Journal of Machine Learning Research, 11 (2010), pp. 19–60.arxiv.org/abs/0908.0050
  13. [13]S. G. Mallat and Z. Zhang, Matching pursuit with time-frequency dictionaries, IEEE Transactions on Signal Processing, 41 (1993), pp. 3397–3415.
  14. [14]I. Mezić, Spectral properties of dynamical systems, model reduction and decompositions, Nonlinear Dynamics, 41 (2005), pp. 309–325.DOI
  15. [15]V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7 (1966), pp. 414–417.
  16. [16]Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, in Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, vol. 1, IEEE, 1993, pp. 40–44.
  17. [17]H. S. Shapiro, Some negative theorems of approximation theory, Michigan Mathematical Journal, 11 (1964), pp. 211–217.DOI
  18. [18]V. Temlyakov, Greedy Approximation, vol. 20 of Cambridge Monographs on Applied and Computational Mathematics, Cambridge University Press, 2011.
  19. [19]J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Transactions on Information Theory, 53 (2007), pp. 4655–4666.
  20. [20]E. Zappala, A. O. Fonseca, J. Caro, and A. H. Moberly, Learning integral operators via neural integral equations, Nat Mach Intell, 6 (2024), p. 1046–1062.DOI

Paper details

vlnc:W_h6fyvnts
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents