ИСТИНА

It will be shown that there exists a cross CUR approximation with relative error of the order 1+r/n+o(r/n), which improves on the best currently known bound of 1+40r/n+o(r/n) by Boutsidis and Woodruff. Notably, the generator U in such an approximation is the pseudoinverse of the rank r projection of the submatrix at the intersection of the selected rows and columns, similar to how maximum projective volume approximations are formed. This allows to view any cross approximation algorithm of a similar form as an approximate projection onto subspace of rank r matrices, and as a faster alternative to randomized approximate SVD. In particular, projections with such cross approximations outperform modern matrix completion algorithms, when the fraction of known elements is high enough.