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

We consider the estimation of a d1× d2× d3 tensor X^star of Tucker rank (r1,r2,r3) from the nonlinear observations yi=fi(langle Ai,X^starrangle)i=1n. 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 |X^star|rm F is known a priori. Under O(r1r2r3+sum1≤ i≤ 3ridi) 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(d3/2) measurements under d1=d2=d3=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.