Many signal and image pipelines first compress data to a few dimensions and then describe each compressed sample as a sparse combination of a few learned "atoms," the columns of a dictionary. Methods that learn the compression and the dictionary together beat the two-step version by large margins, because the compression step otherwise keeps loud noise and throws away the quiet structure the dictionary needs. Every such method assumes one machine holds all the data. We propose a federated version: hospitals, sensors or phones jointly learn one shared projection and one shared dictionary without pooling raw data. The new idea is a structural one. The alternating updates of these joint objectives depend on the data only through sums of small per-client matrices. Clients can therefore send those sums instead of model updates, and every round reproduces the centralized algorithm exactly, however skewed the data split is.
This matters because the usual federated recipe would not hold up here. In federated averaging (FedAvg), each client trains its own copy and the server averages the copies. Applied to a projection with orthonormal rows, averaging is ill-posed: two equally good projections that differ by a rotation average to a worse one, and local alternating steps drift apart when client data differ. Exchanging sufficient statistics avoids both problems by construction. The empirical question we care most about is whether the large advantage of joint over sequential learning, so far measured only on centralized data, survives once the data are split across clients.
Core Claim
Take a Sparse-Embedding-style objective, following Sparse Embedding: A Framework for Sparsity Promoting Dimensionality Reduction. That paper alternates between a projection $P$ and a dictionary $D$ in a compressed space, and shows that the joint model recovers nearly 40 planted atoms where PCA followed by K-SVD recovers none. Here client $m$ holds a data matrix $X_m \in \mathbb{R}^{D \times N_m}$ and keeps its sparse codes $A_m$ private:
$$ \min_{P,\,D,\,\{A_m\}} \sum_{m=1}^{M} \Big( \|P X_m - D A_m\|_F^2 + \lambda \|X_m - P^\top P X_m\|_F^2 + \mu \|A_m\|_1 \Big) \quad \text{s.t. } P P^\top = I_d . $$
In this objective, $P \in \mathbb{R}^{d\times D}$ is the shared projection, $D \in \mathbb{R}^{d \times K}$ is the shared dictionary with $K$ atoms, the $\lambda$ term stops the projection from discarding the data, and $\mu$ sets how sparse the codes are.
With the codes fixed, the projection step reduces to maximizing $(\lambda-1)\,\mathrm{tr}(P S P^\top) + 2\,\mathrm{tr}(P B)$ over orthonormal $P$. This uses the orthonormality constraint to simplify the reconstruction term, and it takes $\lambda > 1$, a condition we impose so the step has a well-posed maximum. The two matrices are
$$ S = \sum_m X_m X_m^\top, \qquad B = \sum_m X_m A_m^\top D^\top . $$
A power-style iteration on the set of orthonormal matrices solves this. It needs only the product $S P^\top = \sum_m X_m (X_m^\top P^\top)$, which is $D \times d$ per client, and the $D \times d$ matrix $B$.
The dictionary step has a closed form, $D = (\sum_m P X_m A_m^\top)(\sum_m A_m A_m^\top + \epsilon I)^{-1}$. It needs only $d \times K$ and $K \times K$ sums. The coding step is a local lasso solve that requires no communication at all.
Two consequences follow. First, if every client participates in a round, the federated iterates equal the centralized ones up to the inner solver's tolerance, independent of how the data are partitioned. Second, communication per outer round is $O(T D d + dK + K^2)$ for $T$ inner projection iterations, with no dependence on the number of samples. When $D$ is small, a client can instead send $X_m X_m^\top$ once, and every later round costs only $O(dK + K^2)$.
Relation to Prior Work
The joint-learning literature motivates the proposal and supplies its objective. Three papers show the joint-versus-sequential gap. Sparse Embedding reports 77.3% on Caltech-101 against 73.6% for LC-KSVD. Supervised and Projected Sparse Coding for Image Classification jointly learns an orthogonal projection and group-sparse codes, reaching 91.9% on USPS against 45.5% for LDA followed by sparse classification. Latent Space Sparse Subspace Clustering alternates eigen-updates of $P$ with ADMM on self-representation codes and reports 2.31% against 2.41% error on Hopkins155. All three need the pooled matrix $X$. We keep their objectives and change only where the sums are computed.
Three federated works come close but each leaves out one ingredient. Distributed Dictionary Learning learns a dictionary over a peer-to-peer network with convex surrogates and gradient tracking. It has no projection, so its atoms must also fit ambient noise. SF-PCA computes exact federated PCA from encrypted local Gram summaries, with eigenvector correlation above 0.99 relative to centralized PCA. It is our closest methodological ancestor, since it exchanges summaries rather than models. But it maximizes variance, which is exactly the criterion Sparse Embedding shows loses sparse structure. Federated Deep Subspace Clustering averages a shared encoder and keeps each client's self-expressive layer private, reaching 83.8% on MNIST. Its subspace structure is never reconciled across clients, and its projection is a deep encoder trained by FedAvg rather than a transparent matrix.
Dictionary ideas in federated learning so far operate on network weights, not data. DictPFL uses a frozen SVD dictionary of weights to make homomorphic encryption affordable. WAFFLe shares rank-1 weight factors and keeps per-client selections private. UEFL grows a vector-quantization codebook inside a deep encoder's space. None of them learns an explicit data projection together with the dictionary.
Two papers constrain the design. SPEAR++ shows that per-client gradients of sparse-dictionary-structured layers can be inverted for batches up to 210 images. Our per-client messages $X_m(X_m^\top P^\top)$ are also linear in local data and would expose the span of a client's data to the server. We therefore treat secure aggregation, which reveals only the sum to the server, as mandatory, and we do not claim privacy beyond what it provides. FedMC shows that non-linear structure matters in federated feature modeling. We handle non-linearity through a shared random-feature map, the same device POF-MKL uses with fixed features. The kernel version of Sparse Embedding needs an $N \times N$ Gram matrix that no federation can form.
Research Program
We will build the protocol for three variants. The first is the unsupervised Sparse Embedding objective above. The second is a supervised variant with class-wise atom blocks, classified by smallest reconstruction residual. The third replaces $X_m$ with shared random features to obtain a non-linear version.
The analysis has three parts. We will prove exact equivalence to centralized block coordinate descent under full participation. We will characterize how error enters under client sampling: the sums become unbiased but noisy, so the method behaves like stochastic block descent. We will also bound the error introduced by an inexact inner projection solve.
Systems work consists of secure aggregation via additive masking over the sums, and optionally CKKS encryption reusing the SF-PCA pipeline. We will measure the runtime of each.
Baselines
The naive reference point is local-only learning. Each client runs centralized Sparse Embedding on its own data, with no collaboration. Collaboration must beat this to be worth anything, especially for clients that see few classes.
The oracle is centralized Sparse Embedding on pooled data. On Caltech-101 with 30 training samples per class, Sparse Embedding reports 77.3% accuracy. Our method should match this to within run-to-run noise on any partition when all clients participate. Any gap falsifies the exactness claim.
The sequential baseline is federated PCA in the SF-PCA style, run in cleartext with matched randomized subspace iteration, followed by federated dictionary learning on the projected features. It doubles as the ablation that isolates jointness: the same protocol with $P$ frozen after initialization. Its centralized analogue recovered 0 of the planted atoms against nearly 40 for the joint model in Sparse Embedding's synthetic test. Beating it means a statistically significant gap in atom recovery and accuracy across partitions.
The strongest competitor that a practitioner would actually try is FedAvg on the same objective. Clients run local alternating steps on $P$, $D$ and $A_m$. The server averages $P$ and $D$ and re-orthonormalizes $P$, with FedProx-style regularization as a tuned variant. We give it the same number of communication rounds and the same total bytes, and tune local epochs and learning rate on the same grid we use for our own inner iterations. No reported result was found on Lacuna for FedAvg applied to a joint projection-dictionary objective. Beating it means higher accuracy at equal bytes under label skew, and a gap that widens as skew increases.
For the clustering variant we compare against FDSC, which reports 83.8% accuracy on MNIST.
For dictionary-only denoising, setting $d = D$ makes our method a federated dictionary learner. We compare it against D²L, which reports 27.65 dB PSNR on the Boat image with 150 agents after 1000 exchanges. Beating it means reaching that PSNR in fewer communication rounds. We also report what the projection adds when artificial high-variance noise dimensions are appended to the patches.
Why not just…?
Why not just run federated PCA and then federated dictionary learning? This is the cheapest serious option, and SF-PCA already makes its first stage exact and private. The evidence against it is centralized: zero atoms recovered in Sparse Embedding's synthetic test, and 45.5% against 91.9% on USPS in SPSC. Federation could narrow the gap if skewed clients make the global covariance unrepresentative in ways that hurt both methods equally. That is why the sequential pipeline is our main ablation on every benchmark. If the gap shrinks to noise under federation, the joint design does not earn its extra rounds, and we will report that.
Why not just apply FedAvg to the joint objective, or to a deep network? WAFFLe reports FedAvg at 45.46% against its 66.35% on multimodal non-IID CIFAR-10, showing how weight averaging degrades under skew. For a projection with orthonormal rows the problem is sharper, because averaging rotated equivalents is ill-defined. Still, re-orthonormalized FedAvg with few local steps might be adequate under mild skew. Our skew sweep measures exactly where it breaks. Deep FedAvg models are a different model class, and we compare against them only through FDSC on clustering.
Why not just have each client send its covariance once and finish on the server? For small $D$ this is a legitimate shortcut, and we adopt it as a variant. It does not remove iteration, because $B$ and $\sum_m A_m A_m^\top$ depend on codes that change every round. For large $D$, such as the 23,724-dimensional genomic data handled by SF-PCA, a $D \times D$ upload is infeasible and the sketched products are needed. We will report the crossover point in $D$.
Proposed Experiments
The synthetic test replicates Sparse Embedding's planted-atom setup with distortion 1.2. The data are split across 10 to 100 clients, with each client generated from a disjoint subset of atoms. We count atoms recovered by each method, comparing against the centralized figure of nearly 40.
Classification uses Caltech-101 features, Extended YaleB, and USPS, partitioned by subject or class with Dirichlet label skew. Metrics are accuracy, worst-client accuracy, and bytes communicated.
Clustering uses Hopkins155 and MNIST. Denoising uses the Boat image split over 150 clients. Scaling uses a high-dimensional genomic matrix, measuring runtime and bytes per round with and without secure aggregation. The non-linear variant is tested on rotated MNIST, where LS3C's kernel version reports 54.63% error against 58.59% for SSC.
Three checks are decisive. First, federated and centralized iterates must coincide across IID and pathological splits while FedAvg degrades. Second, the joint-over-sequential gap must persist after federation. Third, at matched accuracy our method must use fewer bytes than FedAvg. If the first check fails, the method's central guarantee is wrong. If the second fails, the joint objective is not worth federating.
References
- Sparse Embedding: A Framework for Sparsity Promoting Dimensionality Reduction
- Supervised and Projected Sparse Coding for Image Classification
- Latent Space Sparse Subspace Clustering
- Distributed dictionary learning
- Scalable and Privacy-Preserving Federated Principal Component Analysis
- Federated Deep Subspace Clustering
- DictPFL: Efficient and Private Federated Learning on Encrypted Gradients
- WAFFLe: Weight Anonymized Factorization for Federated Learning
- Uncertainty-Based Extensible Codebook for Discrete Federated Learning in Heterogeneous Data Silos
- SPEAR++: Scaling Gradient Inversion via Sparsely-Used Dictionary Learning
- FedMC: Federated Manifold Calibration
- Personalized Online Federated Learning with Multiple Kernels