A Constructive Orbit-Based Theory of Learnability

Yunied Puig

cs.LGOct 30, 2026

A Constructive Orbit-Based Theory of Learnability

Authors: Yunied Puig

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.

Figures & tables

Rank	Selected	Random orbit	Gaussian
1	$0.1586\pm 0.0062$	$0.5798\pm 0.0184$	$0.5929\pm 0.0163$
2	$0.0620\pm 0.0122$	$0.5117\pm 0.0247$	$0.5352\pm 0.0252$
6	$0.0175\pm 0.0275$	$0.1490\pm 0.0739$	$0.2041\pm 0.0134$

Table 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.

Figure 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.

$\gamma$	Mean $\varepsilon_{\mathrm{param}}$	Interior steps (%)	Mean support
0	$7.31\times 10^{-8}$	0	7.00
0.5	$6.92\times 10^{-2}$	34.77	7.00
0.9	$5.11\times 10^{-1}$	76.43	6.99

Table 2: Nested CCDS on the weak-alignment problem. The dictionary, target responses, and seven-step horizon are fixed; the interior schedule changes.

Setting	WBSNN	LR	RF	RBF SVM	MLP	GBT
Gas, 25	$74.23\pm 2.23$	$63.65\pm 2.98$	$62.34\pm 4.57$	$52.25\pm 4.03$	$58.56\pm 6.70$	$58.25\pm 6.94$
Gas, 128	$71.98\pm 1.59$	$69.11\pm 1.19$	$64.58\pm 2.80$	$60.38\pm 0.64$	$64.03\pm 3.44$	$65.98\pm 2.13$
ISOLET, 25	$92.42\pm 0.43$	$91.52\pm 0.11$	$88.33\pm 0.44$	$92.88\pm 0.00$	$91.66\pm 0.42$	$88.97\pm 0.29$
ISOLET, 100	$94.47\pm 0.34$	$92.82\pm 0.00$	$91.62\pm 0.48$	$95.06\pm 0.00$	$93.66\pm 0.60$	$91.76\pm 0.12$
MNIST, 25	$93.95\pm 0.25$	$87.68\pm 0.23$	$90.53\pm 0.20$	$93.04\pm 0.08$	$92.59\pm 0.43$	$91.92\pm 0.18$
MNIST, 100	$96.18\pm 0.25$	$91.15\pm 0.26$	$92.82\pm 0.20$	$94.41\pm 0.13$	$94.80\pm 0.28$	$94.42\pm 0.13$

Table 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.

Anchors	Orbit	Unstructured	Direct MLP
20	$0.509\pm 0.397$	$4.815\pm 0.202$	$0.484\pm 0.054$
28	$0.492\pm 0.365$	$4.036\pm 0.248$	$0.484\pm 0.054$

Table 4: Waveform test MSE multiplied by

10^{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.

Training-label corruption (%)	Exact	Relaxed
0	$97.15\pm 0.12$	$97.08\pm 0.12$
20	$96.99\pm 0.12$	$97.01\pm 0.13$
40	$92.17\pm 3.28$	$93.94\pm 2.83$

Table 5: Clean-test accuracy (%), mean

\pm

standard deviation over five paired seeds. The same corrupted training labels are used in both arms.

Budget (%)	Gas anchors	Gas accuracy (%)	MNIST anchors	MNIST accuracy (%)
1	30	64.16	50	92.06
3	90	68.62	150	93.10
5	150	66.57	250	93.20
7	210	66.18	350	93.56
10	300	65.89	500	93.40
15	450	65.56	—	—

Table 6: Single-seed configuration sweeps. Atom counts equal anchor count times PCA dimension. Optimization settings also vary with budget, as specified below.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Setting	Training size	PCA variance (%)	Anchor budget (%)	Anchors	Atoms
Gas, 25	4,000	99.2	1.0	40	1,000
Gas, 128	8,000	100	0.7	56	7,168
ISOLET, 25	6,238	70.6	5.0	311	7,775
ISOLET, 100	6,238	88.8	5.0	311	31,100
MNIST, 25	5,000	46.0	3.0	150	3,750
MNIST, 100	10,000	74.8	0.7	70	7,000

Appendix

Table 7: 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.

Setting	Hidden width	Learning rate	Epochs
Gas, 25	53	$10^{-3}$	125
Gas, 128	126	$10^{-5}$	500
ISOLET, 25	196	$6\times 10^{-4}$	75
ISOLET, 100	286	$4\times 10^{-5}$	250
MNIST, 25	96	$10^{-3}$	250
MNIST, 100	256	$10^{-4}$	400

Appendix

Table 8: Main coefficient-head configurations. Weight decay and

(\lambda_{\mathrm{coeff}},\lambda_{\mathrm{out}},\lambda_{1})

are

10^{-2}

and

(0,1,10^{-2})

for Gas,

10^{-3}

and

(0,2,0)

for ISOLET, and

10^{-2}

and

(10^{-2},1,0)

for MNIST.

Sparse Recovery

Sparse recovery reconstructs signals or models with few active components from limited, noisy, or indirect measurements.

See all 77 papers

Sep 12, 2025

Multi-Dictionary Learning for Low Rank Sparse Coding

Sparse dictionary coding represents signals as linear combinations of a few dictionary atoms. It has been applied to images, time series, graph signals and multi-way spatio-temporal data by jointly employing temporal and spatial dictionaries. Data-agnostic analytical dictionaries, such as the discrete Fourier transform, wavelets and graph Fourier, have seen wide adoption due to efficient implementations and good practical performance. On the other hand, dictionaries learned from data offer sparser and more accurate solutions but require learning of both the dictionaries and the coding coefficients. This becomes especially challenging for multi-dictionary scenarios since encoding coefficients correspond to all atom combinations from the dictionaries. To address this challenge, we propose a low-rank coding model for 2-dictionary scenarios and study its data complexity. Namely, we establish upper and lower bounds on the number of samples needed to learn dictionaries that generalize to unseen samples from the same distribution. We propose an alternating convex optimization solution, called AODL, which employs alternating optimization between the sparse coding matrices and the learned dictionaries. We demonstrate its quality for data reconstruction and missing value imputation in both synthetic and real-world datasets. For a fixed reconstruction quality, AODL learns up to

90\%

sparser solutions compared to non-low-rank and analytical (fixed) dictionary baselines. In addition, the learned dictionaries reveal interpretable insights into patterns from training samples.

Boya Ma, Abram Magner, Maxwell McNeil +1

University at Albany – SUNY, Computer Science, Albany, NY, USA

Representation Learning Sample Complexity Dictionary Learning Sparse Coding

Ask PDF

Oct 9, 2026

Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity

We study dictionary learning for probability measure-valued data by embedding measures into Hilbert spaces using features derived from optimal transport geometry. We learn data-adapted dictionaries through sparse autoencoder parameterizations, producing fast, scalable representations of probability measures as sparse finite-dimensional codes. The resulting framework combines the rich, geometric structure of optimal transport with the interpretability and efficiency of sparse representation learning. We demonstrate its utility across diverse data modalities, including hyperspectral images, geometric point clouds, and document embeddings in large language model latent spaces. We also prove generalization bounds for sparse dictionary learning objectives on broad classes of

L^2

-valued measure embeddings, expressed in terms of the metric complexity of the atom class. For optimal transport and entropic transport map dictionaries, we derive new covering number bounds that yield explicit rates. Together, our computational and theoretical results support a new, scalable model for representation learning in the space of probability measures via embedding into Hilbert spaces.

Brendan Mallery, Shuchin Aeron, James Murphy

Independent Researcher · Department of Electrical and Computer Engineering, Tufts University · The NSF AI Institute for Artificial Intelligence and Fundamental Interactions (IAIFI) +1

Representation Learning Sparse Coding Sample Complexity Sparse Autoencoders

Ask PDF

Sep 20, 2026

Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning

Dictionary learning seeks to recover an unknown dictionary

A

from observations

{\bf y}_i = A{\bf x}_i

with sparse coefficient vectors

{\bf x}_i

. We introduce the Iterative Atom Refinement (IAR) algorithm, a simple procedure for recovering individual dictionary atoms. Starting from a random direction, IAR repeatedly selects the observations most strongly correlated with the current iterate and updates the direction by averaging the selected data. Our main contribution is a rigorous convergence theory of IAR. Using high-dimensional probabilistic estimates and a novel monotonicity principle for atom-selection probabilities, we show that a small initial advantage of one atom is amplified until that atom is isolated. Under our model assumptions, IAR identifies a generating atom after only three refinement steps. Numerical experiments support the theory and show that the resulting dynamics accurately capture the behavior observed in dictionary refinement.

Alexander Christie, Miguel Moscoso, Alexei Novikov +2

Department of Mathematics, Stanford University, Stanford, CA 94305, USA · Department of Mathematics, Universidad Carlos III de Madrid, Leganés, Madrid 28911, Spain · Department of Mathematics, Pennsylvania State University, University Park, PA 16802, USA +1

Sparse Recovery Dictionary Learning Iterative Refinement Sparse Coding

Ask PDF

Abstract

Sparse Recovery

Explore similar work

Multi-Dictionary Learning for Low Rank Sparse Coding

Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity

Iterative Atom Refinement: A Monotonicity Principle for Dictionary Learning