On Recoverability of Randomly Compressed Tensors with Low CP Rank
This provides theoretical guarantees for recovering tensors in applications such as hyperspectral image and video compression, where prior assumptions were restrictive, making it an incremental advance in tensor recovery theory.
The paper tackles the problem of recovering compressed tensors under the canonical polyadic decomposition model, showing that tensors compressed by subgaussian linear mappings are recoverable with a number of measurements on the same order as model parameters, without requiring strong assumptions like sparsity or continuous distributions in the latent factors.
Our interest lies in the recoverability properties of compressed tensors under the \textit{canonical polyadic decomposition} (CPD) model. The considered problem is well-motivated in many applications, e.g., hyperspectral image and video compression. Prior work studied this problem under somewhat special assumptions---e.g., the latent factors of the tensor are sparse or drawn from absolutely continuous distributions. We offer an alternative result: We show that if the tensor is compressed by a subgaussian linear mapping, then the tensor is recoverable if the number of measurements is on the same order of magnitude as that of the model parameters---without strong assumptions on the latent factors. Our proof is based on deriving a \textit{restricted isometry property} (R.I.P.) under the CPD model via set covering techniques, and thus exhibits a flavor of classic compressive sensing. The new recoverability result enriches the understanding to the compressed CP tensor recovery problem; it offers theoretical guarantees for recovering tensors whose elements are not necessarily continuous or sparse.