Вычисление инверсии очень большой матрицы

Question

Я пытаюсь вычислить инверсию очень большой матрицы (11300x21500) в C++. До сих пор я пробовал библиотеки Eigen и Armadillo, но оба были неудачными на этапе инициализации, заявив, что памяти недостаточно. Может ли быть какой-то способ преодолеть эту ситуацию?

Заранее спасибо

P.S
я должен исправить размер матрицы для 21500x21500. Как предположил UmNyobe, это не квадратная матрица. Это на самом деле матрица наблюдения, X, и я пытаюсь вычислить (X^TX) ^-1

У меня есть память 8 Гб (в 64-битной системе), но я не думаю, что я использую все это пространство памяти. Диспетчер задач показывает, что использование памяти во время ошибки составляет 1 ГБ. Возможно, в Windows7 есть ОС, которая закрывает приложение, когда его использование памяти превышает 1 ГБ.

Кстати, моя первоначальная цель - запустить регрессию над этой матрицей наблюдения.

Еще одна вещь: большинство столбцов в каждой строке матрицы наблюдения X равны нулю. Может ли быть способ воспользоваться этим, чтобы ограничить использование памяти в операции инвертирования?

Answer 1

Вы не можете инвертировать не квадратную матрицу.

http://en.wikipedia.org/wiki/Invertible_matrix

Answer 2

Предположив матрицу является квадратом, что вы, вероятно, ищете алгоритм инверсии матрицы на месте.

Вы должны зарегистрироваться this.

Answer 3

Предполагая (11300 x 11300) Матрицу целое (32 бита), то есть

4*(11300^2)/(1024^3) = 0.4757 GB 

Если вы используете двойной точности, то в два раза это число.

Если библиотека использует алгоритм Штрассена, который требует дополнительной памяти той же величины, то вы удваиваете предыдущий номер.

Таким образом, инвертирование матрицы на основе этого размера с помощью Strassen или gaussian будет стоить вам 1,9 ГБ.

Answer 4

Я хотел бы предложить другое решение, которое работает только в том случае, если вы не заинтересованы в обратном к самой матрице, а в произведении инверсии с вектором. Например, предположим, что вы хотели бы найти продукт ваших обратных времен вектором v, то есть w := (X^T X)^{-1} v. В этом случае, вы на самом деле ищет решение проблемы

Find w such that (X^T X) w = v 

Использование итерационных алгоритмов, можно найти w данную X и v в уравнении выше без переворачиванияX. Одна из возможностей, которая приходит мне на ум, заключается в использовании Method of Conjugate Gradients.Этот алгоритм может быть реализован примерно в 10 строках и требует только вычислить продукт (X^T X) y с заданным вектором y. В нашем случае это можно сделать в два этапа, то есть вычислить z := X y и на втором этапе X^T z, что позволит сэкономить место, поскольку вам не нужно хранить продукт X^T X.

Answer 5

Хотя вы компилируете свою программу на 64-разрядной машине, вы также должны убедиться, что используете правильные 64-разрядные библиотеки. В противном случае программа может быть скомпилирована в 32-разрядной версии, и вы по-прежнему будете иметь одинаковые проблемы с памятью.

Что касается вычисления обратного, то обратная функция OpenCV может помочь. Не забудьте использовать обратный DECOMP_SVD, поскольку я нашел его более эффективным с близкими сингулярными матрицами.