  We consider the problem of recovering an orthogonally decomposable tensor
with a subset of elements distorted by noise with arbitrarily large magnitude.
We focus on the particular case where each mode in the decomposition is
corrupted by noise vectors with components that are correlated locally, i.e.,
with nearby components. We show that this deterministic tensor completion
problem has the unusual property that it can be solved in polynomial time if
the rank of the tensor is sufficiently large. This is the polar opposite of the
low-rank assumptions of typical low-rank tensor and matrix completion settings.
We show that our problem can be solved through a system of coupled
Sylvester-like equations and show how to accelerate their solution by an
alternating solver. This enables recovery even with a substantial number of
missing entries, for instance for $n$-dimensional tensors of rank $n$ with up
to $40\%$ missing entries.
