Multi-way compressed sensing for sparse low-rank tensors

Nicholas D. Sidiropoulos, Anastasios Kyrillidis

Research output: Contribution to journalArticlepeer-review

115 Scopus citations


For linear models, compressed sensing theory and methods enable recovery of sparse signals of interest from few measurementsin 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 \ell-{0}/\ell 1 decompression. This two-step process is also appealing from a computational complexity and memory capacity point of view, especially for big tensor datasets.

Original languageEnglish (US)
Article number6290342
Pages (from-to)757-760
Number of pages4
JournalIEEE Signal Processing Letters
Issue number11
StatePublished - 2012


  • compressed sensing
  • multi-way analysis
  • tensor decomposition


Dive into the research topics of 'Multi-way compressed sensing for sparse low-rank tensors'. Together they form a unique fingerprint.

Cite this