This article is cited in 4 papers

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

E. E. Tyrtyshnikov^a, E. M. Shcherbakova<sup>b

a</sup> Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, 119333 Russia
^b Faculty of Computational Mathematics and Cybernetics, Moscow State University, Moscow, 119991 Russia

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

Key words: nonnegative matrix factorization, separable matrices, fast algorithms, cross approximation methods.

UDC: 519.61

Received: 13.03.2019
Revised: 13.03.2019
Accepted: 10.04.2019

DOI: 10.1134/S0044466919080179

 English version: Computational Mathematics and Mathematical Physics, 2019, 59:8, 1251–1266

Bibliographic databases:

• 
• 
•