Probabilistic estimation of the rank 1 cross approximation accuracy
Provides theoretical guarantees for the maxvol algorithm's accuracy in low-rank approximation, benefiting practitioners in matrix approximation and maximum element search.
The paper analyzes the maxvol algorithm for rank-1 cross approximation, proving that with random matrices and proper initialization, it converges with high probability to an element close to the maximum, and under stricter error conditions, no initialization restrictions are needed.
In the construction of low-rank matrix approximation and maximum element search it is effective to use maxvol algorithm. Nevertheless, even in the case of rank 1 approximation the algorithm does not always converge to the maximum matrix element, and it is unclear how often close to the maximum element can be found. In this article it is shown that with a certain degree of randomness in the matrix and proper selection of the starting column, the algorithm with high probability in a few steps converges to an element, which module differs little from the maximum. It is also shown that with more severe restrictions on the error matrix no restrictions on the starting column need to be introduced.