# Beyond the Signs: Nonparametric Tensor Completion via Sign Series

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 50 references that are in the map.
- First posted on arXiv 31 Jan 2021.

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

- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [A Consistent Histogram Estimator for Exchangeable Graph Models](https://mlsanity.com/paper/1402.1888/) (2014)
- [Nonconvex Low-Rank Tensor Completion from Noisy Data](https://mlsanity.com/paper/1911.04436/) (2019)
- [Generalized Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/1808.07452/) (2018)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Estimating network edge probabilities by neighborhood smoothing](https://mlsanity.com/paper/1509.08588/) (2015)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [Spectral algorithms for tensor completion](https://mlsanity.com/paper/1612.07866/) (2016)
- [Multiway clustering via tensor block models](https://mlsanity.com/paper/1906.03807/) (2019)
- [Learning from Binary Multiway Data: Probabilistic Tensor Decomposition and its Statistical Optimality](https://mlsanity.com/paper/1811.05076/) (2018)
- [Provable Convex Co-clustering of Tensors](https://mlsanity.com/paper/1803.06518/) (2018)
- [Learning tensors from partial binary measurements](https://mlsanity.com/paper/1804.00108/) (2018)
- [Algebraic Variety Models for High-Rank Matrix Completion](https://mlsanity.com/paper/1703.09631/) (2017)
- [Near-optimal sample complexity for convex tensor completion](https://mlsanity.com/paper/1711.04965/) (2017)
- [Matrix Completion Under Monotonic Single Index Models](https://mlsanity.com/paper/1512.08787/) (2015)
- [Tensor denoising and completion based on ordinal observations](https://mlsanity.com/paper/2002.06524/) (2020)
- [On Learning High Dimensional Structured Single Index Models](https://mlsanity.com/paper/1603.03980/) (2016)
- [Bayesian Network--Response Regression](https://mlsanity.com/paper/1606.00921/) (2016)
- [Supervised tensor decomposition with features on multiple modes](https://mlsanity.com/paper/1910.09499/) (2019)
- [Online high rank matrix completion](https://mlsanity.com/paper/2002.08934/) (2020)

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

- [Efficient Nonparametric Tensor Decomposition for Binary and Count Data](https://mlsanity.com/paper/2401.07711/) (2024)
- [Sufficient dimension reduction for feature matrices](https://mlsanity.com/paper/2303.04286/) (2023)
- [Statistical and computational rates in high rank tensor estimation](https://mlsanity.com/paper/2304.04043/) (2023)
- [Color Image Recovery Using Generalized Matrix Completion over Higher-Order Finite Dimensional Algebra](https://mlsanity.com/paper/2308.02621/) (2023)

## Abstract (arXiv)

We consider the problem of tensor estimation from noisy observations with possibly missing entries. A nonparametric approach to tensor completion is developed based on a new model which we coin as sign representable tensors. The model represents the signal tensor of interest using a series of structured sign tensors. Unlike earlier methods, the sign series representation effectively addresses both low- and high-rank signals, while encompassing many existing tensor models -- including CP models, Tucker models, single index models, several hypergraphon models -- as special cases. We show that the sign tensor series is theoretically characterized, and computationally estimable, via classification tasks with carefully-specified weights. Excess risk bounds, estimation error rates, and sample complexities are established. We demonstrate the outperformance of our approach over previous methods on two datasets, one on human brain connectivity networks and the other on topic data mining.