(Псевдо)-обратная матрица N на N с нулевым определителем

Я хотел бы взять обратную матрицу nxn для использования в моем GraphSlam.

Проблемы, с которыми я столкнулся:

  • .inverse() Собственная библиотека (3.1.2) не допускает нулевых значений, возвращает NaN
  • Библиотека LAPACK (3.4.2) не позволяет использовать нулевой определитель, но допускает нулевые значения (используется код примера из Вычисление обратной матрицы с помощью lapack в C)
  • Библиотека Seldon (5.1.2) по какой-то причине не компилировалась

Кто-нибудь успешно реализовал код инверсии матрицы n x n, который допускает отрицательные значения, нулевые значения и определитель нуля? Любые рекомендации по хорошей библиотеке (С++)?

Я пытаюсь рассчитать омегу для GraphSlam следующим образом: http://www.acastano.com/others/udacity/cs_373_autonomous_car.html

Простой пример:

[ 1 -1  0 0 ]
[ -1 2 -1 0 ]
[ 0 -1  1 0 ]
[ 0  0  0 0 ]

Реальный пример будет 170x170 и будет содержать 0, отрицательные значения, большие положительные значения. Данный простой пример используется для отладки кода.

Я могу рассчитать это в Matlab (псевдоинверсия Мура-Пенроуза), но по какой-то причине я не могу запрограммировать это на C++.

A = [1 -1 0 0; -1 2 -1 0; 0 -1 1 0; 0 0 0 0]
B = pinv(A)
B=
[0.56   -0.12  -0.44  0]
[-0.12  0.22   -0.11  0]
[-0.44  -0.11   0.56  0]
[0  0  0   0]

Для моего приложения я могу (временно) удалить измерение с нулями.
Поэтому я собираюсь удалить 4-й столбец и 4-ю строку.
Я также могу сделать это для моей матрицы 170x170, 4x4 был просто примером.

A:

[ 1 -1  0 ]
[ -1 2 -1 ]
[ 0 -1  1 ]

Таким образом, удаление 4-го столбца и 4-й строки не приведет к нулевому определителю. Но у меня все еще может быть нулевой определитель, если моя матрица такая же, как указано выше. Это когда сумма каждой строки или каждого столбца равна нулю. (Который у меня будет постоянно на GraphSlam)

Решение LAPACK (на основе Moore-Penrose Inverse) работало, если детерминант не был равен нулю (использовался код примера из Вычисление обратной матрицы с использованием lapack в C).
Но не удалось как "псевдоинверсия" с определителем, равным нулю.

РЕШЕНИЕ: (все кредиты Франку Райнингхаусу), использование SVD (разложение по единственному значению)
http://sourceware.org/ml/gsl-discuss/2008-q2/msg00013.html

Работает с:

  • Нулевые значения (даже полные 0 строк и полные 0 столбцов)
  • Отрицательные значения
  • Определитель нуля

A^-1:

[0.56   -0.12  -0.44]
[-0.12  0.22   -0.11]
[-0.44  -0.11   0.56]

c++ eigen matrix lapack slam-algorithm
person Community    schedule 17.12.2012    source источник
comment
Что не так с методом исключения Гаусса?   -  person Kerrek SB    schedule 17.12.2012
comment
Не могли бы вы привести один конкретный пример маленькой матрицы, которую ни один из них не сможет инвертировать? (Я предполагаю, что матрица неособая.)   -  person NPE    schedule 17.12.2012
comment
При исключении Гаусса все еще есть возможность иметь отрицательные и нулевые значения в вашем результате, нет?   -  person Toon    schedule 17.12.2012
comment
В вашем примере матрица имеет определитель, равный нулю. Это необратимая матрица. Я надеюсь, что вы не попробовать на этом!   -  person ritter    schedule 17.12.2012
comment
Можете ли вы сделать это название осмысленным? Матрицы с нулевым определителем не имеют обратных.   -  person djechlin    schedule 18.12.2012

Ответы (4)


arrow_upward
7
arrow_downward

Если все, что вам нужно, это решить задачу вида Ax=B (или, что то же самое, вычислить произведения вида A^-1 * b), то я рекомендую вам не вычислять обратную или псевдообратную задачу A, а решать непосредственно для Ax=b с использованием подходящего решателя рангов. Например, используя Eigen:

x = A.colPivHouseholderQr().solve(b);
x = A.jacobiSvd(ComputeThinU|ComputeThinV).solve(b);
person Community    schedule 17.12.2012

arrow_upward
4
arrow_downward

Ваша команда Matlab не вычисляет обратное в вашем случае, потому что матрица имеет нулевой детерминант. Команда pinv вычисляет псевдоинверсию Мура-Пенроуза. pinv(A) обладает некоторыми, но не всеми свойствами inv(A).

Значит, вы не делаете одно и то же в C++ и в Matlab!

Предыдущий

Как в моем комментарии. Теперь как ответ. Вы должны убедиться, что инвертируете обратимые матрицы. Это означает

det A != 0

В вашем примере матрица имеет определитель, равный нулю. Это необратимая матрица. Я надеюсь, что вы не попробовать на этом!

Например, данная матрица имеет нулевой определитель, если есть полная строка или столбец с нулевыми элементами.

person ritter    schedule 17.12.2012
comment
Виноват. Для моего приложения (GraphSlam) сумма всех значений в каждой строке будет равна нулю. Но в своем коде они все еще могут инвертировать эту омега-матрицу. - person Toon; 17.12.2012
comment
Если только сумма каждой строки равна нулю, это ничего не говорит о ее определителе. По крайней мере, я не вижу его быстро ;-) - person ritter; 17.12.2012
comment
Вы пытаетесь решить линейное уравнение X=AY. Вы, конечно, можете запросить обратную А для общего решения проблемы, которая требует det A!=0. Однако линейное уравнение по-прежнему разрешимо с нулевым определителем A. Тогда пространство решений имеет размерность больше 0. Таким образом, все подвекторное пространство является возможным решением. Я бы рекомендовал сначала проверить определитель, а затем решить, как решить линейное уравнение: инверсия, исключение Гаусса и т. д. - person ritter; 17.12.2012
comment
Хорошо, теперь проблема более ясна, я начну копаться в псевдоинверсии Мура-Пенроуза в С++. Я не был уверен, в чем проблема. Теперь я знаю, что не могу использовать обычную инверсию, но должен делать псевдоинверсию. И Matlab использует псевдоинверсию Мура-Пенроуза и может получить результаты спуска. - person Toon; 17.12.2012
comment
Точно, это не псевдоинверсия, которую вы пытаетесь вычислить в своей программе на C++. - person ritter; 17.12.2012

arrow_upward
2
arrow_downward

Вы уверены, что это из-за нулевых/отрицательных значений, а не потому, что ваша матрица необратима?

Матрица имеет обратную только в том случае, если ее определитель отличен от нуля (ссылка на mathworld), а пример матрицы, который вы опубликовано в вопросе имеет нулевой определитель и поэтому не имеет обратного.

Это должно объяснить, почему эти библиотеки не позволяют вам взять обратную матрицу, но я не могу сказать, справедливо ли то же самое рассуждение для вашей полноразмерной матрицы 170x170.

person je4d    schedule 17.12.2012

arrow_upward
0
arrow_downward

Если ваши матрицы являются своего рода ковариационными или весовыми матрицами, вы можете использовать «обобщенную инверсию холецкого» вместо SVD. Результаты будут более приемлемыми для практического использования

person Community    schedule 20.02.2014