Low Rank Tucker Approximation of Streamed Tensors using Structured Measurements


Recently several streaming algorithms for computing low-rank Tucker approximations of large tensors have been introduced by several researchers including Tropp, Udell, et al., De Lathauwer et al., and others. In this talk we will review the basic approach used by these works highlighting their similarities, and then present generalized theoretical guarantees proving their accuracy on full-rank and noisy data with high probability from a wide range of measurements. Some of our newly proposed structured measurements have the advantage of reducing the overall memory needed to sketch and recover large, potentially streamed, tensors and can also be chosen to economize sketching and recovery time. In particular, our recovery algorithms (after measurements have been collected) are sublinear-time in the overall tensor size. In addition, we improve upon prior works by providing stronger recovery error bounds which apply to a much more general class of measurements than previously analyzed. Our numerical experiments further highlight the value of these new measurement choices in various problem scenarios.