Perturbation of Higher-Order Singular Values

The higher-order singular values for a tensor of order $d$ are defined as the singular values of the $d$ different matricizations associated with the multilinear rank. When $d \ge 3$, the singular values are generally different for different matricizations but not completely independent. Characterizing the set of feasible singular values turns out to be difficult. In this work, we contribute to this question by investigating which first-order perturbations of the singular values for a given tensor are possible. We prove that, except for trivial restrictions, any perturbation of the singular values can be achieved for almost every tensor with identical mode sizes. This settles a conjecture from [W. Hackbusch and A. Uschmajew, Numer. Math., 135 (2017), pp. 875--894] for the case of identical mode sizes. Our theoretical results are used to develop and analyze a variant of the Newton method for constructing a tensor with specified higher-order singular values or, more generally, with specified Gramians for the matricizations. We establish local quadratic convergence and demonstrate the robust convergence behavior with numerical experiments.