On the accuracy of cross and column low-rank MaxVol approximations in average

The article considers the problem of low-rank column and cross ($CGR$, $CUR$) approximation of matrices in the Frobenius norm up to a fixed factor $1+\varepsilon$. It is proved that, for random matrices, in average, an estimate of the form $1+\varepsilon\le\frac{m+1}{m-r+1}\frac{n+1}{n-r+1}$, holds, where $m$ and $n$ are the number of rows and columns of the cross approximation. Thus, matrices for which the maximum volume principle cannot guarantee high accuracy are quite rare. A connection of the estimates obtained with the methods for finding the submatrix of the maximum volume and the maximum projective volume is also considered. Numerical experiments show the closeness of theoretical estimates and practical results of fast cross approximation.