Методы неотрицательной матричной факторизации на основе крестовых малоранговых приближений

Известные на данный момент методы для решения задачи неотрицательной матричной факторизации предполагают использование всех элементов исходной матрицы размера $m \times n$ и сложность их не меньше $O(mn)$, что при больших объемах данных делает их слишком ресурсоемкими. Поэтому естественным образом возникает вопрос: можно ли построить неотрицательную факторизацию матрицы, зная ее неотрицательный ранг, используя лишь несколько ее строк и столбцов? В данной работе предлагаются методы решения этой задачи для определенных классов матриц: неотрицательных сепарабельных матриц — тех, для которых существует конус, натянутый на несколько столбцов исходной матрицы и содержащий все ее столбцы; неотрицательных сепарабельных матриц с возмущениями; неотрицательных матриц ранга $2$. На практике предложенные алгоритмы используют число операций и объем памяти, линейно зависящие от $m + n$. Библ. 24. Фиг. 7. Табл. 2.