# On Recoverability of Randomly Compressed Tensors with Low CP Rank

arXiv: https://arxiv.org/abs/2001.02370 · HTML: https://mlsanity.com/paper/2001.02370/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2020.

## Built on by (most cited first, 2 of 2)

- [Implicit Regularization in Tensor Factorization](https://mlsanity.com/paper/2102.09972/) (2021)
- [Downlink MIMO Channel Estimation from Bits: Recoverability and Algorithm](https://mlsanity.com/paper/2411.16043/) (2024)

## Abstract (arXiv)

Our interest lies in the recoverability properties of compressed tensors under the textitcanonical 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 textitrestricted 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.