  Recovery of sparse vectors and low-rank matrices from a small number of
linear measurements is well-known to be possible under various model
assumptions on the measurements. The key requirement on the measurement
matrices is typically the restricted isometry property, that is, approximate
orthonormality when acting on the subspace to be recovered. Among the most
widely used random matrix measurement models are (a) independent sub-gaussian
models and (b) randomized Fourier-based models, allowing for the efficient
computation of the measurements.
  For the now ubiquitous tensor data, direct application of the known recovery
algorithms to the vectorized or matricized tensor is awkward and memory-heavy
because of the huge measurement matrices to be constructed and stored. In this
paper, we propose modewise measurement schemes based on sub-gaussian and
randomized Fourier measurements. These modewise operators act on the pairs or
other small subsets of the tensor modes separately. They require significantly
less memory than the measurements working on the vectorized tensor, provably
satisfy the tensor restricted isometry property and experimentally can recover
the tensor data from fewer measurements and do not require impractical storage.
