Accelerated alternating minimization algorithm for low-rank approximations in the Chebyshev norm
This work addresses the need for efficient low-rank approximations in the Chebyshev norm, which is important for applications where element-wise accuracy is critical, but the contribution is incremental as it builds on existing alternating minimization techniques.
The authors propose an accelerated alternating minimization algorithm for low-rank matrix approximation in the Chebyshev norm, demonstrating effectiveness on large-scale problems. They introduce the concept of a 2-way alternance of rank r and prove it is a necessary condition for optimality, with all limit points of their method satisfying this condition.
Nowadays, low-rank approximations of matrices are an important component of many methods in science and engineering. Traditionally, low-rank approximations are considered in unitary 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 the 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 $r$. We show that the presence of a $2$-way alternance of rank $r$ is the necessary condition of the optimal low-rank approximation in the Chebyshev norm and that all limit points of the alternating minimization method satisfy this condition.