Annealing Over the Outlier Mask for Robust Tensor Completion

Many multi-way datasets have two problems at once. Some entries are missing, and some of the recorded entries are badly wrong. Videos have occluding objects, face images have cast shadows, and hyperspectral cubes (images with hundreds of colour bands) have dead sensor stripes. Robust tensor completion tries to recover the clean array from such data. It assumes the clean signal is low-rank, meaning it is built from a few repeating patterns, and that the corruptions are sparse. The methods that recover the clean signal most accurately use non-convex objectives, and these get stuck in poor local solutions. The way they get stuck is specific: when corruption is concentrated along whole rows, columns, or frames, the solver absorbs the corruption into the "clean" estimate and never gives it back.

This note proposes moving the search. Instead of nudging the continuous factor matrices, we run simulated annealing over the discrete set of entries labelled as outliers. Simulated annealing is a search method that sometimes accepts a worse candidate, with a probability that shrinks as a "temperature" parameter is lowered. The search proposes structured changes to the label set, such as declaring a whole frame corrupt or rehabilitating a block. For each proposal, it re-fits the low-rank part on the remaining trusted entries with a fast, warm-started completion solver. It then accepts or rejects the proposal with the Metropolis rule, which always accepts improvements and accepts a worsening of size $\Delta E$ with probability $e^{-\Delta E/T}$. The claim is that being stuck in robust tensor completion is mostly a combinatorial problem of choosing which entries to trust. Annealing over that choice escapes traps that continuous descent, convex relaxation, and entry-by-entry reweighting cannot.

Core Claim

Recovering the low-rank part is well behaved once the outliers are known. Fast solvers such as Preconditioned Riemannian Gradient Descent (PRGD) handle this subproblem well. PRGD runs gradient descent on the set of fixed-rank Tucker tensors with a data-driven rescaling of the gradient, and it converges linearly from a spectral starting point. However, its authors state that it assumes Gaussian noise and has no way to isolate sparse outliers.

The hard part is the support of the outliers, and structured corruption makes it hard in a precise way. A corrupted slice is itself nearly low-rank. A sparse-plus-low-rank split therefore has no reason to label it sparse. This is exactly the incoherence violation that the exact-recovery guarantees of Robust Low-Rank Tensor Ring Completion and the convex model in Fully-connected tensor network decomposition for robust tensor completion problem assume away.

We define the energy of a candidate trusted set $\Gamma \subseteq \Omega$, where $\Omega$ is the set of observed entries, as

$$E(\Gamma) = \min_{\mathrm{rank}(\mathcal{X}) \le r} \frac{1}{|\Gamma|}\,\| \mathcal{P}_\Gamma(\mathcal{Y} - \mathcal{X}) \|_F^2 + \lambda\, c(\Omega \setminus \Gamma).$$

Here $\mathcal{Y}$ is the observed tensor and $\mathcal{P}_\Gamma$ keeps only entries in $\Gamma$. The quantity $r$ is the target multilinear rank. The term $c(\cdot)$ is a description-length cost of the rejected set, which charges less for one whole rejected fibre than for the same number of scattered entries. The weight $\lambda$ trades fit against the number of rejected entries.

We anneal $\Gamma$ using a mixture of move types: single entries, fibres, slices, and contiguous blocks. The novelty does not lie in "simulated annealing for tensors" in general. It lies in three choices made together:

  • The annealing state is the outlier mask, not the factors.
  • The moves are structure-aware.
  • Each energy evaluation is a short warm-started run of a fast completion solver.

Relation to Prior Work

The motivating evidence comes from work showing that non-convex tensor recovery gets trapped. Local and Global Convergence of General Burer-Monteiro Tensor Optimizations proves that rank-$r$ factorized landscapes have genuine spurious minima. Gradient descent there succeeds only from a warm start; the paper reports a 100% success rate for initialization radius $\alpha \le 2$. That analysis covers fully observed, uncorrupted tensors. Our setting adds both missing entries and outliers, which can only make the landscape worse.

The authors of T-SVD Based Non-convex Tensor Completion and Robust Principal Component Analysis replace the convex nuclear norm with SCAD and MCP penalties to remove the convex norm's estimation bias. They note that their solver is initialization-sensitive and recommend starting from the convex solution. Fully-connected tensor network decomposition likewise reaches only critical points with its non-convex RNC-FCTN solver.

These papers do not try to escape poor solutions; they try to start near a good one. We take the opposite route. We keep the fast local solver for the continuous part and put the escape mechanism in the discrete part.

Two lines of annealing work supply the method and also constrain it. Neural Simulated Annealing keeps the Metropolis acceptance step and learns the proposal distribution. It was validated only on combinatorial problems such as the travelling salesperson problem, knapsack, and bin packing. This supports the view that annealing works best on discrete states with good moves, which is why we anneal a mask rather than continuous factors.

The graduated non-convexity papers, Adaptive Annealing for Robust Geometric Estimation and Adaptive Annealing for Robust Averaging, anneal the scale of a robust loss. They report that fixed decay schedules fail badly. On averaging with 50% outliers, fixed graduated non-convexity has mean error 13.99, against 1.37 for their adaptive version, GNCp, which tracks convexity of the cost. They also report that the convexity guide breaks down at extreme outlier ratios. Graduated non-convexity reweights each residual independently. It therefore cannot express the claim "this whole frame is corrupt", and that coupling is what our moves supply.

Bayesian Robust Tensor Ring Decomposition (BRTR) offers a probabilistic alternative with automatic rank pruning. Its variational updates are themselves a deterministic coordinate descent, and its slice pruning is greedy. We treat it as a strong competitor, not as something to build on.

Research Program

The system has three parts.

Inner solver. A robust-free low-rank completion solver, PRGD on the Tucker format, runs for a fixed small number $K$ of iterations. It is warm-started from the factors of the last accepted state. This gives an approximate $E(\Gamma)$ at a cost far below a cold solve. Because the energy is approximate, the chain is a noisy-energy Metropolis chain. We will measure how acceptance decisions change as $K$ grows. We will also report a final full solve on the best mask, so that reported accuracy does not depend on the approximation.

Proposal distribution. Proposals mix move types in proportion to their recent acceptance rates. The move types are: flip a single entry, flip a mode-$n$ fibre, flip a slice, grow or shrink a contiguous block, and swap one region in while another goes out. Moves are biased toward entries whose current residual is large (for rejecting) or small (for rehabilitating). The bias is computed with the usual Hastings correction, the factor that adjusts acceptance for asymmetric proposals, so that the target distribution is preserved.

Temperature. The temperature schedule is set from the empirical distribution of energy changes. The initial $T$ is chosen so that about half of uphill moves are accepted. Cooling is geometric, and the schedule is restarted if the acceptance rate collapses early.

A learned proposal in the style of Neural SA is a deliberate later extension. It is left out of the core study so that the effect of annealing can be measured cleanly.

Analysis. We will characterize when the mask landscape has the traps that motivate the method. The test case is a planted tensor with $s$ corrupted slices. For each $s$ and missing ratio, we count distinct local minima of $E$ under the greedy (zero-temperature) version of the same moves, using many random starts. We expect a transition. Below a threshold in $s$, entry-wise methods and greedy search both succeed. Above it, only methods that search over slice-level hypotheses with uphill moves recover the planted support.

Baselines

Naive reference. Plain PRGD on all observed entries, treating every observation as trusted. It shows how much damage the outliers do. Any method must beat it by a wide margin on corrupted data and should match it on clean data.

Convex robust completion. Robust Tensor Ring Completion (RTRC) from Robust Low-Rank Tensor Ring Completion and RC-FCTN from Fully-connected tensor network decomposition. RTRC minimizes nuclear norms of tensor-ring unfoldings plus an $\ell_1$ outlier term. These are the methods with exact-recovery guarantees, so they are the right test of whether structure-induced failures are real.

Strongest non-convex methods. RNC-FCTN and BRTR. Both are reported to outperform SNN, TNN, TTNN, and RTRC in MPSNR, MSSIM, RSE, and PSNR on video, hyperspectral, and YaleB data. However, no reported result was found on Lacuna for their numerical values on any dataset. We will therefore re-run them with author code on identical masks and corruption patterns.

The strongest number available in the file is completion-only and has no outliers: T2NN reaches 27.51 dB PSNR on Akiyo with 95% of entries missing (A Hybrid Norm for Guaranteed Tensor Recovery). This sets an upper reference for what our method should approach on Akiyo when outliers are added and then correctly removed.

Fairness. Each method gets the same observed entries, the same corruption realizations over 20 seeds, and the same rank-search grid. Each also gets the same hyperparameter-tuning budget, done on a held-out tensor. Wall-clock budgets are matched, with the annealing chain capped at the slowest baseline's runtime.

What counts as beating them. A statistically significant RSE reduction over the best of RNC-FCTN and BRTR on structured-corruption settings. In addition, no worse than a 0.5 dB PSNR loss on purely random-entry corruption, where we do not expect an advantage.

Ablations. The key ablation is the same move set at zero temperature: greedy mask search, accepting only improvements. It isolates the uphill acceptance step. A second ablation restricts moves to single entries, isolating structure-awareness.

Why not just…?

Why not just restart the non-convex solver many times from random initializations? This is the most serious threat, because multi-start is cheap and parallel. Our expectation is that restarts randomize the factors but not the outlier decision. A corrupted slice that fits a low-rank pattern will be absorbed from almost any starting factors. The Burer-Monteiro analysis says the basin around the true solution is small, but it says nothing about whether random starts find it under structured corruption. We will run compute-matched multi-start RNC-FCTN and multi-start PRGD with $\ell_1$ trimming. If they match annealing on the slice-corruption phase diagram, we will report that the mask view adds nothing.

Why not just warm-start from a convex solution, as Ma et al. recommend? That works when the convex solution is close, which needs incoherence. Under slice-concentrated corruption, the convex split puts the slice into the low-rank part, so the warm start sits inside the trap. Running convex-then-SCAD/MCP as a baseline on the same structured settings tests this directly.

Why not just use graduated non-convexity or group-sparse outlier penalties? Graduated non-convexity anneals per-entry weights. With a fixed schedule it is fragile, with mean error 13.99 against 1.37 for the adaptive version in Adaptive Annealing for Robust Averaging. Its adaptive Hessian tracking scales poorly to tensor-sized parameter vectors, and its authors note it fails at extreme outlier ratios. Group penalties such as $\ell_{2,1}$ fix one group shape in advance. We will include fixed-schedule graduated non-convexity with a Geman-McClure loss on the same inner solver, and $\ell_{2,1}$ variants with fibre groups and with slice groups. If a correctly specified group penalty matches annealing, the remaining value of our method is robustness to not knowing the corruption shape. We will test that with mixed corruption shapes.

Proposed Experiments

Synthetic tensors. Planted Tucker and tensor-ring ground truths, with missing ratios from 50% to 90%. Corruption comes in four shapes: random entries, fibres, slices, and blocks. Each shape is tested at increasing corrupted fractions. We report RSE, F1 of the recovered outlier support, and exact-recovery success rate (RSE $< 10^{-4}$).

Real data with naturally structured corruption.

  • Extended YaleB, where shadows are the outliers.
  • The surveillance videos used by BRTR and RTRC, where moving foreground objects are blocks and some frames are dropped.
  • Indian Pines and Salinas A with injected stripe and band corruption.
  • Akiyo with corrupted frame blocks.

We report PSNR and SSIM (structural similarity), and foreground F1 where ground-truth masks exist.

Decisive checks. First, the success-rate phase diagram over the number of corrupted slices against missing ratio. The proposal is supported if annealing pushes the failure boundary well beyond that of RNC-FCTN, BRTR, and compute-matched multi-start. Second, the zero-temperature ablation. If greedy mask search with the same structured moves matches full annealing, the credit belongs to the moves, not the annealing, and we will say so. Third, a runtime curve of accuracy against wall-clock time, to show that warm-started inner solves keep the method competitive with ADMM-based convex solvers.