Multi-Way Compressed Sensing for Sparse Low-Rank Tensors

For linear models, compressed sensing theory and methods enable recovery of sparse signals of interest from few measurements-in the order of the number of nonzero entries as opposed to the length of the signal of interest. Results of similar flavor have more recently emerged for bilinear models, but no results are available for multilinear models of tensor data. In this contribution, we consider compressed sensing for sparse and low-rank tensors. More specifically, we consider low-rank tensors synthesized as sums of outer products of sparse loading vectors, and a special class of linear dimensionality-reducing transformations that reduce each mode individually. We prove interesting "oracle" properties showing that it is possible to identify the uncompressed sparse loadings directly from the compressed tensor data. The proofs naturally suggest a two-step recovery process: fitting a low-rank model in compressed domain, followed by per-mode l(0)/l(1) decompression. This two-step process is also appealing from a computational complexity and memory capacity point of view, especially for big tensor datasets.