Low-Rank Tensor Estimation from Nonlinear Observations: A Unified Framework

Abstract

We consider the estimation of a $d_1\times d_2\times d_3$ tensor $X^{\star }$ of Tucker rank $(r_1,r_2,r_3)$ from the nonlinear observations $\{y_i=f_i(⟨A_i,X^{\star }⟩){\}}_{i=1}^n$. We develop a unified approach that first constructs a gradient map from the data and then establishes the tensor restricted approximate invertibility condition (T-RAIC), a condition that quantifies how well the gradient map aligns with the ideal descent step under a low-rank tensor dual norm. We show that T-RAIC yields local linear convergence guarantees for a Riemannian gradient descent (RGD) algorithm, which may incorporate a normalization step if $\Vert X^{\star }{\Vert }_{\mathrm{F}}$ is known a priori. Under $O(r_1{r}_2{r}_3+{\sum }_{1\le i\le 3}{r}_i{d}_i)$ Gaussian measurements, we establish T-RAICs for single-index models, logistic regression, phase retrieval, ReLU regression, and one-bit compressed sensing. The RAICs imply that RGD locally converges to $X^{\star }$ exactly in phase retrieval and ReLU regression, and up to near-optimal estimation errors in the remaining models. We further show that, in all these models except for phase retrieval, a simple spectral initialization yields the desired initialization from $O(d^{3/2})$ measurements under $d_1=d_2=d_3=d$ (ignoring dependence on the Tucker rank and condition number of $X^{\star }$). This is also the best known sample complexity for polynomial-time and end-to-end algorithms in tensor linear regression and tensor completion. Numerical simulations are provided to corroborate our theoretical findings.

Compared with v1 (Oct 2025), the current v3 focuses exclusively on the tensor estimation results, with substantially clearer exposition, several improvements and refinements, and a new model of tensor ReLU regression. Compared with v2 (Aug 2026), v3 corrects several typos and notation issues