View PDF HTML (experimental)

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(\langle A_i,X^\star\rangle)\}_{i=1}^n$. We develop a unified approach that first constructs a gradient map from the data and then establishes the {\it 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(r_1r_2r_3+\sum_{1\le i\le 3}r_id_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(\sqrt{d_1d_2d_3})$ measurements, which 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.

Submission history

From: Junren Chen [view email]
[v1] Sun, 19 Oct 2025 19:10:08 UTC (783 KB)
[v2] Sat, 29 Aug 2026 20:56:34 UTC (419 KB)