# Sparse and Low-rank Tensor Estimation via Cubic Sketchings

arXiv: https://arxiv.org/abs/1801.09326 · HTML: https://mlsanity.com/paper/1801.09326/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jan 2018.

## Built on by (most cited first, 11 of 11)

- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Guaranteed Nonconvex Factorization Approach for Tensor Train Recovery](https://mlsanity.com/paper/2401.02592/) (2024)
- [Tensor Principal Component Analysis in High Dimensional CP Models](https://mlsanity.com/paper/2108.04428/) (2021)
- [Covariate-assisted Sparse Tensor Completion](https://mlsanity.com/paper/2103.06428/) (2021)
- [A Scalable Factorization Approach for High-Order Structured Tensor Recovery](https://mlsanity.com/paper/2506.16032/) (2025)
- [Robust Low-rank Tensor Train Recovery](https://mlsanity.com/paper/2410.15224/) (2024)
- [Jointly Modeling and Clustering Tensors in High Dimensions](https://mlsanity.com/paper/2104.07773/) (2021)
- [Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements](https://mlsanity.com/paper/2502.05134/) (2025)
- [Dual-Channel Tensor Neural Networks: Finite-Sample Theory and Conformal Structure Selection](https://mlsanity.com/paper/2605.19122/) (2026)

## Abstract (arXiv)

In this paper, we propose a general framework for sparse and low-rank tensor estimation from cubic sketchings. A two-stage non-convex implementation is developed based on sparse tensor decomposition and thresholded gradient descent, which ensures exact recovery in the noiseless case and stable recovery in the noisy case with high probability. The non-asymptotic analysis sheds light on an interplay between optimization error and statistical error. The proposed procedure is shown to be rate-optimal under certain conditions. As a technical by-product, novel high-order concentration inequalities are derived for studying high-moment sub-Gaussian tensors. An interesting tensor formulation illustrates the potential application to high-order interaction pursuit in high-dimensional linear regression.