Fast and stable recovery of Approximately low multilinear rank tensors from multi-way compressive measurements

We introduce a reconstruction formula that allows one to recover an N-order tensor X ϵ R^I1×...×In from a reduced set of multi-way compressive measurements by exploiting its low multilinear rank structure. It is proved that, in the matrix case (N = 2), the proposed reconstruction is stable in the sense that the approximation error is proportional to the one provided by the best low-rank approximation, i.e ||X - X||₂ ≤ K||X - X₀||₂, where K is a constant and X₀ is the corresponding truncated SVD of X. We also present simulation results indicating that the same stable behavior is observed with higher order tensors (N > 2). In addition, it is shown that, an interesting property of multi-way measurements allows us to build the reconstruction based on compressive linear measurements of fibers taken only in two selected modes, independently of the tensor order N. Simulation results using real-world 2D and 3D signals are presented illustrating our results and comparing the reconstructions against the best low multilinear rank approximations and the reconstructions obtained by using the Kronecker-CS approach.