# Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 30 references that are in the map.
- First posted on arXiv 7 Feb 2025.

## Builds on (most cited first, 12 of 12)

- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Optimization and Generalization of Shallow Neural Networks with Quadratic Activation Functions](https://mlsanity.com/paper/2006.15459/) (2020)
- [Iterative Random Forests to detect predictive and stable high-order interactions](https://mlsanity.com/paper/1706.08457/) (2017)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [On the Impact of Overparameterization on the Training of a Shallow Neural Network in High Dimensions](https://mlsanity.com/paper/2311.03794/) (2023)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Sparse and Low-rank Tensor Estimation via Cubic Sketchings](https://mlsanity.com/paper/1801.09326/) (2018)
- [Tensor Regression Using Low-rank and Sparse Tucker Decompositions](https://mlsanity.com/paper/1911.03725/) (2019)
- [Iterative Hard Thresholding for Low CP-rank Tensor Models](https://mlsanity.com/paper/1908.08479/) (2019)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Neural Networks and Polynomial Regression. Demystifying the Overparametrization Phenomena](https://mlsanity.com/paper/2003.10523/) (2020)

## Abstract (arXiv)

In this paper, we investigate the sample complexity of recovering tensors with low symmetric rank from symmetric rank-one measurements. This setting is particularly motivated by the study of higher-order interactions and the analysis of two-layer neural networks with polynomial activations (polynomial networks). Using a covering numbers argument, we analyze the performance of the symmetric rank minimization program and establish near-optimal sample complexity bounds when the underlying distribution is log-concave. Our measurement model involves random symmetric rank-one tensors, which lead to involved probability calculations. To address these challenges, we employ the Carbery-Wright inequality, a powerful tool for studying anti-concentration properties of random polynomials, and leverage orthogonal polynomials. Additionally, we provide a sample complexity lower bound based on Fano's inequality, and discuss broader implications of our results for two-layer polynomial networks.