Probabilistic estimation of the rank 1 cross approximation accuracy

DOI10.1007/978-3-030-41032-2_22MaRDI QIDQ6288509arXivFDO

Authors D. A. Zheltkov, Alexander Osinsky

Publication date 30 June 2017

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-41032-2_22

Mathematics Subject Classification ID

Numerical analysis (65-XX)

arXiv classification

math.NA

Abstract: 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.

This page was built for publication: Probabilistic estimation of the rank 1 cross approximation accuracy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6288509)