Many datasets arrive as multi-way arrays, or tensors: wireless channels indexed by antenna, subcarrier and time; hyperspectral images indexed by row, column and wavelength; knowledge bases indexed by subject, relation and object. Splitting such a tensor into a few low-rank factors (tensor decomposition) recovers its structure. The standard algorithms are fragile, though. Under noise or outliers they can stall for hundreds of iterations or converge to wrong factors, and the robust variants that come with guarantees are slow. Neural networks trained to speed this up are locked to the size they were trained on. We propose a learned decomposition solver that is trained on small tensors and runs unchanged on tensors with mode lengths one to two orders of magnitude larger, under heavy-tailed and structured corruption. It works directly on the factors and the observed entries, so it never builds the full tensor in memory.
The idea fits in two sentences. Write one step of a robust alternating solver as message passing: each row of a factor matrix (one antenna, one pixel row, one entity) collects averaged messages from the tensor entries it touches, and a small network decides how much to trust each entry and how to precondition the row's update. Because every learned piece acts on a single entry or a single row and uses averages rather than sums, the same weights apply at any tensor size. Larger tensors also give each row more entries to average over, which should make the learned solver more accurate at scale.
Core Claim
We claim that a learned update rule which is local, permutation-equivariant and mean-aggregated generalizes zero-shot across tensor sizes. When the true signal is low-rank, it beats both hand-designed robust reweighting and fixed-size learned initializers, measured by accuracy and by wall-clock time to a target accuracy. The claim also resolves a tension noted in the literature. Online and Differentially-Private Tensor Decomposition shows that tensor power iteration tolerates isotropic noise up to $O(1/\sqrt{d})$ because high-dimensional averaging cancels noise. Methods that generalize across sizes in combinatorial optimization, such as BQ-NCO, which reduces a large routing instance step by step to small subproblems resembling its training data, get size invariance by shrinking the problem the model sees. That would seem to give up the averaging benefit. Our design keeps the decision local while the evidence behind each decision grows with scale, so locality and noise averaging work together.
Concretely, consider an order-3 tensor $\mathcal{T}$ observed on index set $\Omega$, with CP factors $A, B, C$ of rank $R$. CP (canonical polyadic) decomposition writes the tensor as a sum of $R$ rank-one outer products. Let $a_i$ be row $i$ of $A$, $\Omega_i$ the observed entries with first index $i$, and $r_{ijk} = \mathcal{T}_{ijk} - \langle a_i, b_j, c_k\rangle$ the residual. The learned row update is
$$a_i \leftarrow a_i + P_\theta(s_i)\,\frac{1}{|\Omega_i|}\sum_{(i,j,k)\in\Omega_i} w_\theta(r_{ijk}, z_{ijk})\, r_{ijk}\,(b_j \ast c_k).$$
Here $\ast$ is the elementwise product. The function $w_\theta$ is a learned trust weight that sees the residual and features $z_{ijk}$, namely residual statistics of the entry's other slices. $P_\theta$ is a learned $R\times R$ preconditioner computed from row summary statistics $s_i$. Both share weights across the $R$ rank components, so they also commute with relabeling the components.
With $w \equiv 1$ and $P$ set to the inverse Gram matrix, this reduces to an alternating least squares (ALS) step. With $w$ fixed to a Huber or $\ell_1$ weight, it is iteratively reweighted least squares. The quantitative expectation follows from averaging independent noise. If the weighted residual noise has bounded variance $\sigma^2$, the noise in the aggregated update scales like $\sigma/\sqrt{|\Omega_i|}$. As mode lengths grow, $|\Omega_i|$ grows and per-row error should fall, provided the learned weights stay calibrated outside the training sizes.
Research Program
The method borrows mechanisms from three groups of prior work. From the cross-scale literature it takes the design rules that buy size invariance. Learning Combinatorial Optimization Algorithms over Graphs conditions decisions on local neighborhood embeddings. The half-convolution GNN for combinatorial auctions passes messages on a bipartite graph between items and bids. Local–global feature fusion transformers show that absolute coordinate inputs break transfer across scales. Our bipartite graph links factor rows to observed entries, uses no absolute index coordinates, and relies only on averaged aggregation.
From IREM, which generalizes from 10-node to 30-node graphs by running more energy-descent steps at test time, we take the policy of letting the iteration count grow with instance size. We also take the warning that its experiments stop at small sizes. Our update is a learned step on an explicit residual objective rather than a free energy, which keeps memory per step at $O(|\Omega| R)$.
From the robust-decomposition literature we take the target behaviour and the strongest hand-designed competitor. Robust Low-rank Tensor Train Recovery proves linear convergence of $\ell_1$ subgradient methods with 40–50% corrupted measurements. It also documents the trade-off we target: the projected variant must store the full tensor, and the factorized variant slows sharply when the tensor is ill-conditioned. The learned preconditioner $P_\theta$ is aimed at that second failure. DL-CPALS motivates the work and is the closest prior method. It unrolls two ALS iterations to train a network that predicts a starting point, and it escapes ALS "swamps" (long plateaus with little progress), but only for $32\times8$ antenna arrays.
We differ from DL-CPALS in three ways. We learn the update rather than the starting point. Our learned functions never see the tensor dimensions. We train against heavy-tailed and block corruptions rather than near-Gaussian noise. Sketching work such as Fast and Guaranteed Tensor Decomposition via Sketching constrains the scalability design. For dense large tensors we subsample $\Omega$ uniformly at each step instead of using count sketches, because mean aggregation makes subsampling an unbiased estimate of the full update. Whether this matches sketch-level speed is an empirical question we will report.
Structured corruptions need special care. Robust tensor CUR decompositions and Anandkumar et al. note that tensors can isolate slice and fiber corruptions that defeat matrix robust PCA, but a weight computed from one entry cannot see that its slice is corrupted. The features $z_{ijk}$ therefore include the median and spread of residuals along each of the entry's fibers. This lets the network down-weight a whole stripe or occluded block. Training uses random CP tensors with mode lengths between 16 and 64, ranks between 2 and 10, condition numbers between 1 and 100, and noise drawn from a mixture of Gaussian, Student-t, Poisson, sparse gross outliers and slice/block corruptions. Losses are computed on held-out clean entries and unrolled over 10–20 steps with truncated backpropagation.
Extending to tensor trains (chains of small three-way cores, so that storage grows linearly in tensor order) is a second-stage goal. Each core slice becomes a row token. We will report it only if the CP version works, since rank growth across TT cores adds a separate failure mode.
Baselines
The naive reference point is ALS started from a truncated SVD of each unfolding, plus random-start ALS. Both run on the same observed entries with the same rank and stop at the same tolerance. DL-CPALS reports that SVD-ALS needs 158 iterations, and random-start ALS fails within 500, to reach an average normalized squared error (ANSE) of 0.002 on mmWave MIMO channels. Any learned method has to beat these clearly in time-to-target to justify itself.
The strongest hand-designed competitor is the identical unrolled structure with $w_\theta$ replaced by Huber or $\ell_1$ reweighting and $P_\theta$ replaced by the exact inverse Gram matrix. This is robust ALS by iteratively reweighted least squares. Its Huber threshold and damping are tuned by grid search on the same small training tensors the learned model sees, with a comparable number of tuning evaluations. This is also the ablation that isolates our key ingredient, the learned weighting and preconditioning. We run separate ablations that drop only $P_\theta$, and that drop only the fiber features $z$, to attribute gains.
For guarantees under gross outliers we compare to FRSubGM from Robust Low-rank Tensor Train Recovery. It uses spectral initialization and the same entries; for no-materialization comparisons we restrict it to its factorized form. For learned fixed-size competitors, DL-CPALS is retrained separately at each target size. It thus gets more training than our model, which is trained once at small sizes. An oracle version of our own model, trained directly at each target size, gives an upper bound that measures the cost of zero-shot transfer.
On real data we add domain methods. On HYDICE Urban hyperspectral restoration, the reference is LRTDTV, at a mean peak signal-to-noise ratio (MPSNR) of 38.63 dB versus 36.35 dB for matrix-based LRTV. We also include DeepTensor, which fits an untrained network per instance and reports up to 6 dB over SVD/PCA on hyperspectral denoising. On the JHU COVID-19 count tensor the reference is ENTED, with relative RMSE 0.406 (Nonparametric tensor ring decomposition). All methods get the same per-instance wall-clock budget on the same hardware.
Beating a baseline means two things at the largest test sizes, which are never seen in training. Our method must reach lower factor or held-out reconstruction error at matched wall-clock time, or reach the same error at least 2× faster. And the gap must not shrink as size grows.
Why not just…?
Why not just use robust ALS with a well-tuned Huber weight? This is the most serious threat. If the noise model is simple, a tuned Huber weight may already be near-optimal, and it transfers across sizes trivially. Our bet is that learning helps in two specific regimes: mixed and structured corruption, where entry-wise Huber weights cannot see a bad slice, and ill-conditioned factors, where Gram-inverse steps swamp. The matched ablation settles this directly. If learning gains nothing over tuned reweighting on isotropic and sparse-outlier noise, we will say so and restrict the claim to the block-corruption and ill-conditioned regimes.
Why not just initialize ALS from an SVD, or with a DL-CPALS-style network retrained at each size? DL-CPALS shows that a better start cuts iterations from 158 to 36, yet a start alone does not prevent later swamps when noise changes how strongly the factors overlap. Retraining at every size also needs training data at every size, which is exactly what is missing in the target settings. Our MIMO experiment trains at $32\times8$ and tests on larger arrays, comparing against per-size retrained DL-CPALS. Losing to it would show that size invariance costs more accuracy than it saves.
Why not just fit each tensor from scratch with DeepTensor or a coarse-to-fine tensor train like PuTT? PuTT upsamples a fitted tensor train from coarse to fine grids. Both methods can be very accurate, and on HYDICE they may win on peak quality. They need thousands of gradient steps per instance, and PuTT's upsampling assumes regular dyadic grids, which do not exist for antenna or entity modes. We therefore report the full accuracy–time curve rather than a single number, and concede the high-budget end if that is where they lead.
Why not just unfold the tensor and run matrix robust PCA? LRTDTV's 38.63 versus 36.35 dB comparison already shows that unfolding loses spatial–spectral structure, and unfolding does not reduce memory. We include unfold-then-RPCA only as a sanity baseline on the block-corruption experiments.
Proposed Experiments
The first decisive check is a scaling curve on synthetic CP tensors. We train at mode length at most 64 and test at 128, 512, 2048 and 4096 under each noise family, plotting factor match score and time-to-target against size for our method, tuned Huber-IRLS, FRSubGM and the size-specific oracle. The hypothesis fails if the gap to the oracle widens with size. The concentration prediction gets its own test: per-row error should fall roughly like $1/\sqrt{|\Omega_i|}$ when sampling density is held fixed, and we test whether the learned weights keep that slope or drift miscalibrated outside the training range.
The second check is mmWave MIMO-OFDM channel estimation simulated as in DL-CPALS. We train at $32\times8$ antennas and test at $64\times16$ and $128\times32$, reporting iterations and wall-clock time to ANSE 0.002 against SVD-ALS, random-start ALS and retrained DL-CPALS.
The third check is HYDICE Urban restoration under its native stripe, Gaussian and impulse mixture. We train only on small random crops and run on the full image, reporting MPSNR against LRTDTV's 38.63 dB together with runtime. The fourth check is the JHU order-4 count tensor, which tests whether a single learned weight function transfers to count noise, against ENTED's relative RMSE of 0.406.
Across all four, the ablations removing $P_\theta$, $z$ and learned $w$ show which ingredient carries the result. A null result on the Huber ablation would be reported as the main finding.
References
- Online and Differentially-Private Tensor Decomposition
- BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
- Learning Combinatorial Optimization Algorithms over Graphs
- A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions
- Learning to solving vehicle routing problems via local–global feature fusion transformer
- Learning Iterative Reasoning through Energy Minimization
- Robust Low-Rank Tensor Train Recovery
- Deep-Learning-Aided Alternating Least Squares for Tensor CP Decomposition and Its Application to Massive MIMO Channel Estimation
- Fast and Guaranteed Tensor Decomposition via Sketching
- Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruptions
- Tensor vs. Matrix Methods: Robust Tensor Decomposition under Block Sparse Perturbations
- Hyperspectral Image Restoration Via Total Variation Regularized Low-Rank Tensor Decomposition
- DeepTensor: Low-Rank Tensor Decomposition With Deep Network Priors
- Nonparametric tensor ring decomposition with scalable amortized inference
- Coarse-To-Fine Tensor Trains for Compact Visual Representations