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

Junren Chen; Lijun Ding; Dong Xia; Ming Yuan

Source-linked AI summary

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

Junren Chen, Lijun Ding, Dong Xia, Ming Yuan

arXiv:2510.16965v3Oct 19, 2025math.STcs.ITstat.ME

TL;DR

The paper studies low Tucker rank tensor estimation from nonlinear observations, where efficient and statistically optimal procedures were previously unavailable across the considered models. It introduces T-RAIC to align empirical gradient maps with ideal descent steps and uses this condition to analyze RGD, obtaining exact or near-optimal local recovery and end-to-end guarantees except for phase retrieval initialization.

Problem
The paper addresses the lack of computationally efficient and statistically optimal procedures for nonlinear low Tucker rank tensor regression.
Method
The framework establishes T-RAIC for model-specific gradient maps and uses it to obtain local linear convergence of RGD, optionally with normalization when the Frobenius norm is known.
Results
Across five nonlinear models, T-RAIC yields exact local recovery for phase retrieval and ReLU regression and near-optimal errors for the remaining models; spectral initialization gives O(d3/2) end-to-end guarantees except for phase retrieval.
Takeaways & Limitations
The framework provides a common RGD-based analysis for nonlinear low Tucker rank tensor estimation, including nonsmooth, discontinuous, and unknown link functions.
Takeaways & Limitations
The O(d3/2) initialization complexity is statistically suboptimal, and provable initialization for low-rank tensor phase retrieval remains open.

Abstract

from arXiv · show

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 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(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.

1 Introduction

The paper develops a unified framework for low Tucker rank tensor estimation from nonlinear observations, addressing the lack of computationally efficient and statistically optimal procedures across several models. Its T-RAIC-based RGD framework supports local recovery, while spectral initialization enables end-to-end guarantees for all considered models except phase retrieval.

Our Contributions: T-RAIC requires a model-specific empirical gradient map to approximate the ideal descent step under a low-rank tensor dual norm, without requiring the link function to be continuous, smooth, or convex.The framework therefore accommodates unknown, nonsmooth, discontinuous, and nonconvex observation links.
Our Contributions: Under Gaussian covariates and O(r1r2r3 + r1d1 + r2d2 + r3d3) observations, the paper establishes T-RAICs for five nonlinear tensor models.The models are single-index regression, logistic regression, phase retrieval, ReLU regression, and one-bit tensor sensing.
Our Contributions: The resulting RGD guarantees give exact local recovery in phase retrieval and ReLU regression, and near-optimal errors in single-index models, logistic regression, and one-bit compressed sensing.These are local guarantees based on the T-RAIC and warm initialization.
Spectral initialization: A first-moment spectral procedure using yiAi followed by T-HOSVD provides accurate initialization with O(d1d2d3)^1/2 observations for the considered nonlinear models except phase retrieval.In the balanced setting, this becomes O(d3/2) measurements, and combining initialization with local convergence gives end-to-end guarantees for four models.
Spectral initialization: The O(d3/2) initialization cost is statistically suboptimal but matches the best-known polynomial-time guarantees for tensor linear regression and tensor completion.The paper also notes that exact recovery is unavailable from one-bit observations or general unknown-link single-index models, unlike ReLU observations.

2 Preliminaries

The preliminaries define Tucker-rank tensors, their matricizations and decompositions, and the tangent-space machinery used by Riemannian optimization. They then introduce T-RAIC as the central condition relating a gradient map to the ideal descent direction under a low-rank tensor dual norm.

2.1 Tensor and Tucker Rank: Tucker rank is specified by the ranks of the three tensor matricizations, and the low-rank tensor set consists of tensors whose mode-wise ranks do not exceed (r1,r2,r3).A Tucker-rank tensor admits a core tensor and orthonormal factor matrices, with degrees of freedom Tdf = r1r2r3 + Σj rjdj.
2.1 Tensor and Tucker Rank: T-HOSVD approximately computes the best Tucker-rank approximation, while exact projection onto the low-rank tensor set is generally NP-hard.The approximation satisfies a factor-three Frobenius error bound relative to the exact projection.
2.2 Riemannian Optimization: The tangent space at a fixed Tucker-rank tensor is a linear subspace associated with the smooth fixed-rank manifold, and Riemannian gradients are obtained by projecting ordinary gradients onto it.This projection has a closed-form expression and can be followed by T-HOSVD retraction to return to the manifold.
2.3 Tensor Restricted Approximate Invertibility Condition: T-RAIC requires H(U) to uniformly approximate U − X⋆ over a constraint set under the low Tucker rank tensor dual norm.This condition is the tensor-specific form of a more general restricted approximate invertibility condition.

3 Riemannian Gradient Descent

The paper develops Riemannian and normalized Riemannian gradient descent methods for low-Tucker-rank tensor estimation under T-RAIC conditions. The resulting theorems provide local convergence guarantees, with normalization enabling a weaker constraint-set requirement when the target Frobenius norm is known.

Riemannian Gradient Descent: RGD uses a gradient map projected onto the tangent space, while T-HOSVD enforces the low Tucker rank structure because best low-rank approximation is computationally infeasible.The algorithm takes a gradient map, step size, initialization, and Tucker rank as inputs.
Local convergence: Under T-RAIC conditions, Algorithm 2 has a general local convergence guarantee for iterates near X^star.The stated conditions require a sufficiently large constraint set and an error function based on the Frobenius distance to X^star.
Local convergence: The convergence theorem applies when the approximation parameter satisfies µ2 <= c min{Rloc, Λmin}, for universal constants C > c > 0.The target is assumed to have Tucker rank (r1, r2, r3) and positive Λmin.
Normalized RGD: When ||X^star||F is known, normalized RGD rescales iterates to the target norm and converges under an RAIC on a weaker constraint set.The normalized method keeps iterates on βS_F, where β = ||X^star||F.
Normalized RGD: The normalized convergence theorem assumes Tucker rank (r1, r2, r3), positive Λmin, known Frobenius norm β, and the same local smallness condition on µ2.The theorem states the condition µ2 <= c min{Rloc, Λmin} for universal constants C > c > 0.

4 Applications to Concrete Models

The framework establishes T-RAICs for several nonlinear low-rank tensor models under Gaussian measurements, yielding local RGD guarantees and near-optimal error rates or exact recovery depending on the model.

T-RAIC results: T-RAICs are established for single-index models, logistic regression, phase retrieval, ReLU regression, and one-bit sensing using Gaussian covariates.The measurement requirement is of order the tensor's degrees of freedom, written as Tdf in the supplied theorems.
Tensor single-index models: Single-index models attain squared Frobenius error O(σ̂^2Tdf/n), matching the minimax lower bound for tensor linear regression.The comparison follows by specializing the random link functions to additive Gaussian-noise linear observations.
Tensor logistic regression: The logistic-regression analysis assumes known unit Frobenius norm, while extending the techniques to unknown norm remains future work.Known norms different from one are covered by a direct extension, but the supplied passage excludes unknown norms.
Model-specific guarantees: RGD converges exactly in phase retrieval and ReLU regression, while single-index models, logistic regression, and one-bit sensing achieve near-optimal estimation errors.These conclusions follow from the model-specific T-RAICs and local convergence theorems.
One-bit tensor sensing: One-bit sensing reaches an error rate matching the lower bound up to logarithmic factors, despite signs identifying the tensor only up to global scale or direction constraints.The cited lower bound is Ω(Tdf/n) for uniform recovery, and the theorem's rate matches it up to logarithmic factors.
Technical contributions: The phase-retrieval and ReLU T-RAIC proofs use hyperplane tessellation to obtain uniform guarantees over all signals, enabling uniform local convergence.This is stronger than the fixed-signal guarantees associated with the cited prior techniques.

5 Spectral Initialization

The paper proposes a first-moment HOSVD spectral initializer for nonlinear low-rank tensor observations and establishes high-probability accuracy guarantees under model assumptions. The initializer supports end-to-end procedures, but does not currently provide provable accuracy for tensor phase retrieval.

Assumptions: The initialization analysis assumes a fixed tensor X⋆ with Tucker rank and Frobenius norm satisfying Assumption 5.1.The observation functions may be random, independent copies of a possibly random function, and independent of the Gaussian covariates.
Method: Algorithm 4 is a simple first-moment HOSVD procedure designed for nonlinear observations.Its proof adapts Gaussian orthogonal decomposition ideas but requires new concentration control because nonlinear responses are non-Gaussian.
Theoretical guarantees: Theorem 5.3 establishes high-probability accuracy for the HOSVD initializer under a sample-size condition and assumptions on the nonlinear observation model.The result gives an initialization error bound for the algorithm's output.
Theoretical guarantees: Theorem 5.3 yields Corollary 5.4, providing a more convenient sufficient condition for the initializer's accuracy.
Limitation: In phase retrieval, the initializer cannot guarantee accurate initialization because the first condition in (5.2) fails.A provable tensor phase-retrieval initializer is left for future work, with the matrix case already unresolved in the relevant regime.

6 End-to-End Algorithms for Concrete Models

The paper combines spectral initialization with local Riemannian-gradient convergence to obtain end-to-end guarantees for several nonlinear tensor models. These guarantees are nonuniform and require O(d^{3/2}) observations in the balanced fixed-rank, bounded-condition-number setting, while tensor phase retrieval is excluded from the initialization results.

Scope and limitations: The end-to-end results are nonuniform because the initialization applies only to a fixed unknown X⋆ and requires at least order D observations.The local convergence guarantees can hold under fewer observations, creating a gap between initialization and local optimization requirements.
Tensor single-index models: For tensor single-index models, Algorithm 4 produces an initializer that satisfies the warm-start requirement of Theorem 4.7 under the stated sample-size condition.The proof combines the initialization event with the local convergence event.
Tensor logistic regression: For tensor logistic regression, normalized Algorithm 4 output satisfies the initialization condition needed for the local convergence theorem under the stated assumptions.The setting treats the Frobenius norm as known, while unknown norm remains outside the current techniques.
Tensor ReLU regression: For ReLU regression, initializing with 2Z0 yields local convergence to X⋆ under the stated sample-size and conditioning requirements.The factor two compensates for the model-specific coefficient µ = 1/2 in the spectral initializer analysis.
One-bit tensor sensing: For one-bit tensor sensing, normalized spectral initialization satisfies the warm-start condition required for the local convergence guarantee.The proof identifies a sample-size term sufficient for the minimum-eigenvalue condition.
Overall guarantees: Theorems 6.2–6.5 provide end-to-end guarantees for tensor single-index models, logistic regression, ReLU regression, and one-bit tensor sensing.The procedures combine Algorithm 4 with the corresponding local convergence theorem, using normalization or rescaling when required.
Sample complexity: In the balanced setting with fixed Tucker rank and bounded condition number, the end-to-end procedures use sample size of order d^{3/2}.This rate is statistically suboptimal but matches the best-known polynomial-time guarantees cited for tensor linear regression and tensor completion.

7 Numerical Simulations

Numerical experiments support the theoretical behavior of the end-to-end algorithms across nonlinear tensor models and compare tensor phase retrieval with matrix and vector alternatives on hyperspectral data. The results show improved error with more observations, model-specific advantages, and strong gains from exploiting Tucker structure.

End-to-end recovery under nonlinear observations: In the truncated single-index model, estimation error decreases with sample size, while increasing tensor dimension or Tucker rank increases error.The experiments use (d,r) = (20,2), (28,2), and (28,4) across sample sizes from 1200 to 8800.
End-to-end recovery under nonlinear observations: In ReLU regression, the model-specific algorithm reaches numerical precision with enough observations, while the generic single-index method has substantially larger statistical error.This matches the theorem's exact convergence guarantee for the specialized ReLU solver.
End-to-end recovery under nonlinear observations: In one-bit sensing, the model-specific algorithm has markedly faster error decay than the generic single-index gradient, consistent with O(n^-1) versus O(n^-1/2) rates.Larger dimension or Tucker rank also produces larger estimation errors, consistent with the stated theoretical dependence.
Tensor phase retrieval with a hyperspectral image dataset: The hyperspectral experiment uses a 30×30×30 tensor from bands 6–35 and 6750 Gaussian phaseless measurements, with adjacent bands providing the initialization.Because provably accurate tensor phase-retrieval initialization remains unavailable, the initialization is data-driven.
Tensor phase retrieval with a hyperspectral image dataset: On Indian Pines, tensor phase retrieval achieves Frobenius error 0.021 and PSNR 35.91, outperforming matrix error 0.119 and PSNR 20.84 and vector error 0.258 and PSNR 14.12.All methods start from the same data-driven initialization and run for 50 iterations.
Tensor phase retrieval with a hyperspectral image dataset: The tensor method's advantage is consistent with jointly exploiting low-rank structure across all three tensor modes.

8 Concluding Remarks

The paper unifies low Tucker rank tensor estimation from nonlinear observations through T-RAIC and derives local convergence and efficient initialization results. It also identifies initialization for phase retrieval, multi-response regression, and robustness as open directions.

T-RAIC quantifies how closely a model-specific empirical gradient map approximates the ideal descent step under the tensor dual norm, yielding local linear convergence for RGD and its normalized counterpart.
The framework establishes T-RAICs for single-index models, logistic regression, phase retrieval, ReLU regression, and one-bit tensor sensing under Gaussian covariates.
The resulting RGD guarantees give exact local recovery for phase retrieval and ReLU regression, while the remaining models achieve near-optimal statistical errors.
Except for phase retrieval, simple spectral initialization followed by RGD yields computationally efficient end-to-end algorithms.
Open problems include provable initialization for low-rank tensor phase retrieval, multi-response regression, and robust variants for sparse, heavy-tailed, or corrupted settings.

A.2 Proof of Theorem 3.2 (Convergence of Algorithm 3)

The convergence proof for the normalized algorithm maintains a local error bound, feasibility, and Tucker rank throughout the iterations. It relies on normalization control, a sufficiently small error parameter, and Weyl’s inequality.

Normalization is controlled using a standard Euclidean error bound when ||X⋆||F=β>0, enabling the normalized update to inherit the convergence argument.
For sufficiently small μ2 relative to the local radius and minimum singular-value parameter, the error sequence decreases monotonically.
The induction preserves the Frobenius error bound, the local constraint set, and Tucker rank (r1,r2,r3) at every iteration.The proof establishes these three properties jointly for all t ≥ 0.
Weyl’s inequality ensures that iterates remain in the prescribed Tucker-rank neighborhood, completing the induction and convergence proof.
The broader RAIC framework compares a gradient map with the ideal descent step under a dual norm over a constraint set, with complexity controlled by Gaussian width and covering numbers.

B.2 Single-Index Models (Proof of Theorem 4.6)

The single-index proof derives a tensor RAIC by specializing a general Gaussian-design RAIC after vectorizing tensors. Its sample requirement is governed by the Gaussian widths of the model cone and low-rank dual-norm set.

The single-index RAIC holds with high probability when n ≥ C[ω2(K)+ω2(C(1))], combining the complexities of the symmetric set and cone.
The argument controls deviations uniformly over normalized cone differences and the symmetric set using empirical-process bounds.
Rotational invariance and sub-Gaussian control bound the relevant random processes, producing the desired RAIC with exponentially high probability.
The proof reduces tensor estimation to a vector problem through vectorization and applies Gaussian-width bounds to obtain the T-RAIC.
A Stein-identity calculation makes the residual term vanish, completing the single-index RAIC proof.

B.4 Phase Retrieval (Proof of Theorem 4.13)

The phase-retrieval proof establishes a uniform RAIC for the phase-retrieval gradient map over a cone and symmetric set under Gaussian design. It controls sign-sensitive discrepancies and transfers the resulting bound to tensors by vectorization.

The phase-retrieval RAIC holds uniformly over nonzero cone elements under a Gaussian-design sample condition involving the complexities of the cone and symmetric set.
The proof restricts to nonzero target and iterate pairs and controls their phase-retrieval discrepancy through a global binary embedding bound.
The relevant dual-norm term is identified with the corresponding fluctuation term from the single-index argument, allowing previously established bounds to be reused.
After establishing the vector RAIC, vectorization and Gaussian-width estimates yield the tensor phase-retrieval T-RAIC.

B.5 ReLU Regression (Proof of Theorem 4.15)

The ReLU-regression proof establishes a general cone-based RAIC and applies it to the low-rank tensor tangent cone. The argument combines product-process concentration, covering arguments, and spectral initialization bounds.

RAIC for ReLU Regression: Theorem B.10 establishes a ReLU-regression RAIC uniformly over cone elements under Assumption B.5 and a sample-size condition.The result uses the map h_x(u) and provides universal constants controlling the approximation error.
RAIC for ReLU Regression: The proof bounds the main error terms uniformly, including Ξ7 ≤ 1/80∥u − x∥2 with high probability.The bound holds when n is sufficiently large relative to the Gaussian widths of K and C(1).
Proof of Theorem B.10: A covering argument controls the centered sign-product process by combining a net approximation with concentration for product processes.The proof uses a minimal net of C ∩ S^{d−1}, product-process concentration, and bounds on the approximation remainder.
Proof of Theorem 4.15: Theorem 4.15 follows by identifying tensor space with Euclidean space, applying Theorem B.10, and using Proposition B.4 for the low-rank tangent cone.The tensor cone is instantiated through T^d_{2r} ∩ B_F.
Spectral initialization: The spectral-initialization proof exploits Gaussian rotational invariance and mode-wise covariance concentration to estimate the leading singular subspaces.The leading r_j eigenvectors of the empirical matrices provide the mode factors, with probability controlled when n ≥ C d_j.

C.2 Proof of Corollary 5.4

The proof of Corollary 5.4 converts general concentration and tangent-space results into bounds involving tensor condition parameters. It verifies the required sample-size condition and derives the stated error guarantees.

Sample-size verification: The first sample-size requirement in (5.5) implies n ≥ C T_d^f, while the remaining terms control the contributions in (5.4).The proof uses relations (C.13)–(C.14) and then bounds each term on the right-hand side of (5.4).
Error bounds: The residual contribution ρν^2d/(µΛ^2n) is bounded by cµΛ using the final term in (5.5) and Λ ≤ ρκ^2.Choosing the universal constant sufficiently large yields the first result in (5.6).
Error bounds: Normalization inequalities and the relations µX⋆ and Λ ≤ ρ yield the second result in (5.6).The proof applies the standard normalization inequality for nonzero tensors.
Condition-number form: The condition-number formulation in (5.7) implies (5.5), completing the corollary.Mode-wise spectral-norm bounds establish the needed relation between the condition-number parameters and the earlier sample-size condition.