Accelerated Alternating Minimization Algorithm for Low‐Rank Approximations in the Chebyshev Norm

ABSTRACT Nowadays, low‐rank approximations of matrices are an important component of many methods in science and engineering. Traditionally, low‐rank approximations are considered in unitarily invariant norms; however, recently element‐wise approximations have also received significant attention in the literature. In this paper, we propose an accelerated alternating minimization algorithm for solving the problem of low‐rank approximation of matrices in the Chebyshev norm. Through numerical evaluation, we demonstrate the effectiveness of the proposed procedure for large‐scale problems. We also theoretically investigate the alternating minimization method and introduce the notion of a 2‐way alternance of rank . We show that the presence of a 2‐way alternance of rank is a necessary condition for the optimal low‐rank approximation in the Chebyshev norm and that all limit points of the alternating minimization method satisfy this condition.