Analysis of the alternating minimization method for low-rank canonical polyadic decomposition in the Chebyshev norm

Calcolo. 2026. Vol. 63. No. 2. Article 23.

Stanislav Morozov

The approximation of tensors in a low-para metric format is a crucial component in many mathematical modelling and data analysis tasks. Among the widely used low-parametric representations, the canonical polyadic (CP) decomposition is known to be very efficient. Nowadays, most algorithms for CP approximation aim to construct the approximation in the Frobenius norm; however, some applications require entrywise approximation. In this paper, we propose the alternating minimization method for constructing low-rank approximations of tensors in the CP format in the Chebyshev norm. Through an extensive evaluation, we demonstrate the effectiveness of the algorithm. We also analyze the proposed algorithm for rank-1 approximations and introduce the notion of d-way alternance. We show that the presence of a d-way alternance is a necessary condition for optimal approximation and that all limit points of the alternating minimization method satisfy this condition. Based on this analysis, we derive a modification of the algorithm that empirically shows promising results for constructing of the optimal rank-1 approximations.

Keywords: Alternating minimization, low-rank approximation, Chebyshev norm, Canonical polyadic decomposition