Effective Tensor Sketching via Sparsification

DOI10.1109/TIT.2021.3049174MaRDI QIDQ4963971zbMATH OpenOpenAlexFDO

Authors Dong Xia, Ming Yuan

Publication date 24 February 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.11298

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Multilinear algebra, tensor calculus (15A69) Numerical linear algebra (65F99)

Abstract: In this paper, we investigate effective sketching schemes via sparsification for high dimensional multilinear arrays or tensors. More specifically, we propose a novel tensor sparsification algorithm that retains a subset of the entries of a tensor in a judicious way, and prove that it can attain a given level of approximation accuracy in terms of tensor spectral norm with a much smaller sample complexity when compared with existing approaches. In particular, we show that for a $k$th order $dimescdotsimesd$ cubic tensor of {it stable rank} $r_s$, the sample size requirement for achieving a relative error $varepsilon$ is, up to a logarithmic factor, of the order $r_s^{1/2}{d}^{k/2}/varepsilon$ when $varepsilon$ is relatively large, and $r_{s}d/varepsilo{n}^2$ and essentially optimal when $varepsilon$ is sufficiently small. It is especially noteworthy that the sample size requirement for achieving a high accuracy is of an order independent of $k$. To further demonstrate the utility of our techniques, we also study how higher order singular value decomposition (HOSVD) of large tensors can be efficiently approximated via sparsification.

Cited in

(4)

• Statistical inference for structured high-dimensional models. Abstracts from the workshop held March 11--17, 2018
• scientific article; zbMATH DE number 7049775 (Why is no real title available?)
• Covariate-Assisted Sparse Tensor Completion
• Davis-Kahan theorem under a moderate gap condition

This page was built for publication: Effective Tensor Sketching via Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4963971)