Methods for nonnegative matrix factorization based on low-rank cross approximations

Available methods for nonnegative matrix factorization make use of all elements of the original $m\times n$ matrix, and their complexity is at least $O(mn),$ which makes them extremely resource-intensive in the case of large amounts of data. Accordingly, the following natural question arises: given the nonnegative rank of a matrix, can a nonnegative matrix factorization be constructed using some of its rows and columns? Methods for solving this problem are proposed for certain classes of matrices, namely, for nonnegative separable matrices (for which there exists a cone spanned by several columns of the original matrix that contains all its columns), for nonnegative separable matrices with perturbations, and for nonnegative matrices of rank 2. In practice, the number of operations and the amount of storage used by the proposed algorithms depend linearly on $m+n$ .