Sensing tensors with Gaussian filters

Sparse recovery from linear Gaussian measurements has been the subject of much investigation since the breaktrough papers \cite{CRT:IEEEIT06} and \cite{donoho2006compressed} on Compressed Sensing. Application to sparse vectors and sparse matrices via least squares penalized with sparsity promoting norms is now well understood using tools such as Gaussian mean width, statistical dimension and the notion of descent cones \cite{tropp2014convex} \cite{Vershynin:ArXivEstimation14}. Extention of these ideas to low rank tensor recovery is starting to enjoy considerable interest due to its many potential applications to Independent Component Analysis, Hidden Markov Models and Gaussian Mixture Models \cite{AnandkumarEtAl:JMLR14}, hyperspectral image analysis \cite{zhang2008tensor}, to name a few. In this paper, we demonstrate that the recent approach of \cite{Vershynin:ArXivEstimation14} provides very useful error bounds in the tensor setting using the nuclear norm or the Romera-Paredes--Pontil \cite{RomeraParedesPontil:NIPS13} penalization.