Generic Linear Convergence for Algorithms of Nonlinear Least Squares over Smooth Varieties

In applications, a substantial number of problems can be formulated as nonlinear least squares problems over smooth varieties. Unlike the classical least squares problem over a Euclidean space, the nonlinear least squares problem over a variety can be challenging to solve and analyze even if the variety itself is simple. Geometrically, this problem is equivalent to projecting a point in the ambient Euclidean space onto the image of the given variety under a nonlinear map. It is the singularities of the image that make both the computation and the analysis difficult. In this paper, we prove that, under some mild assumptions, these troublesome singularities can always be avoided. This enables us to establish that linear convergence rate can be generic for iterative sequences generated by algorithms satisfying some standard assumptions. We apply our general results to the low-rank partially orthogonal tensor approximation problem. As a consequence, we obtain the linear convergence rate for a classical alternating polar decomposition–alternating least squares method applied to a generic tensor without any further assumptions. Funding: This work is partially supported by the Natural Science Foundation of Hunan Province of China Grant 2025JJ20006, the National Key Research Project of China Grant 2023YFA1009401, the National Natural Science Foundation of China Grants 12571554 and 12571334, and the Innovation Research Foundation of National University of Defense Technology.