Recovering orthogonal tensors under arbitrarily strong, but locally correlated, noise

preprint2021arXivOpen access

Abstract

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 nn-dimensional tensors of rank nn with up to 40%40\% missing entries.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.