Python, одновременное псевдообращение множества сингулярных симметричных матриц 3x3

У меня есть 3D-изображение с размерами строк x cols x deps. Для каждого вокселя изображения я вычислил реальную симметричную матрицу 3x3. Они хранятся в массиве D, который, следовательно, имеет форму (rows, cols, deps, 6).

D хранит 6 уникальных элементов симметричной матрицы 3x3 для каждого воксела моего изображения. Мне нужно найти псевдо-инверсию Мура-Пенроуза для всех матриц row * cols * deps одновременно / в векторизованном коде (цикл через каждый воксель изображения и инвертирование слишком медленное в Python).

Некоторые из этих симметричных матриц 3x3 неособые, и я могу найти их инверсии в векторизованном коде, используя аналитическую формулу для истинной инверсии невырожденной симметричной матрицы 3x3, и я это сделал.

Однако для тех матриц, которые ЯВЛЯЮТСЯ сингулярными (а они обязательно будут), мне нужен псевдообратный алгоритм Мура-Пенроуза. Я мог бы вывести аналитическую формулу для MP реальной, сингулярной, симметричной матрицы 3x3, но это действительно неприятная / длинная формула и, следовательно, будет включать ОЧЕНЬ большое количество (поэлементных) матричных арифметических операций и немного запутать ищу код.

Следовательно, я хотел бы знать, есть ли способ одновременно численно найти псевдообратную МП для всех этих матриц сразу. Есть ли способ сделать это?

С благодарностью, GF


person NLi10Me    schedule 01.05.2014    source источник


Ответы (2)


NumPy 1.8 включает элементы линейной алгебры, которые делают именно то, что вам нужно. В то время как np.linalg.pinv не gufunc-ed, np.linalg.svd есть, и за кулисами вызывается именно эта функция. Таким образом, вы можете определить свою собственную gupinv функцию на основе исходного кода исходной функции следующим образом:

def gu_pinv(a, rcond=1e-15):
    a = np.asarray(a)
    swap = np.arange(a.ndim)
    swap[[-2, -1]] = swap[[-1, -2]]
    u, s, v = np.linalg.svd(a)
    cutoff = np.maximum.reduce(s, axis=-1, keepdims=True) * rcond
    mask = s > cutoff
    s[mask] = 1. / s[mask]
    s[~mask] = 0

    return np.einsum('...uv,...vw->...uw',
                     np.transpose(v, swap) * s[..., None, :],
                     np.transpose(u, swap))

И теперь вы можете делать такие вещи, как:

a = np.random.rand(50, 40, 30, 6)
b = np.empty(a.shape[:-1] + (3, 3), dtype=a.dtype)
# Expand the unique items into a full symmetrical matrix
b[..., 0, :] = a[..., :3]
b[..., 1:, 0] = a[..., 1:3]
b[..., 1, 1:] = a[..., 3:5]
b[..., 2, 1:] = a[..., 4:]
# make matrix at [1, 2, 3] singular
b[1, 2, 3, 2] = b[1, 2, 3, 0] + b[1, 2, 3, 1]

# Find all the pseudo-inverses
pi = gu_pinv(b)

И, конечно, результаты верны как для сингулярных, так и для неособых матриц:

>>> np.allclose(pi[0, 0, 0], np.linalg.pinv(b[0, 0, 0]))
True
>>> np.allclose(pi[1, 2, 3], np.linalg.pinv(b[1, 2, 3]))
True

И для этого примера с вычисленными псевдообратными 50 * 40 * 30 = 60,000:

In [2]: %timeit pi = gu_pinv(b)
1 loops, best of 3: 422 ms per loop

Что на самом деле не так уж и плохо, хотя это заметно (в 4 раза) медленнее, чем простой вызов np.linalg.inv, но это, конечно, не позволяет должным образом обрабатывать отдельные массивы:

In [8]: %timeit np.linalg.inv(b)
10 loops, best of 3: 98.8 ms per loop
person Jaime    schedule 01.05.2014
comment
Очень круто, это потрясающая особенность нового релиза! Записная книжка ipython со списком новых обобщенных функций ufunc находится здесь - person gg349; 02.05.2014
comment
Забавно, что этот блокнот взят из выступления, которое я дал группе пользователей Python в Сан-Диего! Никогда бы не подумал, что кто-нибудь, кроме присутствующих на этом выступлении, когда-нибудь найдет его. Интернет - маленькое место ... - person Jaime; 02.05.2014
comment
Спасибо за ответ, Джейми, это похоже на какой-то мощный код ... но я еще не совсем его понимаю. Я относительно новичок в Python. Gufunc - это реализация графического процессора? Я уверен, что смогу это найти, но подумал, что спрошу, если кто-то еще не знает. Конечно, взять псевдообратное значение 60000 произвольных вещественных / симметричных матриц 3x3 за 422 мс - это довольно круто. - person NLi10Me; 03.05.2014
comment
Это не имеет ничего общего с графическим процессором. Вы можете прочитать документацию по универсальным функциям, также известным как ufuncs, здесь. Затем вы можете прочитать об обобщенных универсальных функциях, также известных как gufuncs, здесь. По сути, ufuncs берут операцию, определенную на скалярах, например сложение, и запускают ее поэлементно для всех элементов своих входных массивов. Gufuncs делают нечто подобное с операциями, определенными для массивов, так что один вызов выполняет одну и ту же операцию для многих составных массивов. - person Jaime; 03.05.2014

РЕДАКТИРОВАТЬ: см. Ответ @Jaime. Только обсуждение в комментариях к этому ответу сейчас полезно и только для конкретной проблемы.

Вы можете сделать эту матрицу по матрице, используя scipy, который предоставляет pinv (link) для вычисления псевдообратного преобразования Мура-Пенроуза. Пример ниже:

from scipy.linalg import det,eig,pinv
from numpy.random import randint
#generate a random singular matrix M first
while True:
    M = randint(0,10,9).reshape(3,3)
    if det(M)==0:
        break
M = M.astype(float)
#this is the method you need
MPpseudoinverse = pinv(M)

Однако при этом не используется тот факт, что матрица является симметричной. Вы также можете попробовать версию pinv, предоставленную numpy, которая предположительно быстрее и отличается. См. это сообщение.

person gg349    schedule 01.05.2014
comment
Я знаю scipy.linalg.pinv, мой вопрос в том, как ИЗБЕЖАТЬ делать это матрица за матрицей. Цикл по всем строкам cols deps-матриц слишком медленный для моего приложения. - person NLi10Me; 01.05.2014
comment
Извините, у меня создалось впечатление, что это не так, поскольку только некоторые из них являются единичными. Вы профилировали свой код? Вы УВЕРЕНЫ, что это ваш звонок pinv к вашей проблеме? Сколько матриц обычно бывает сингулярным? Подозреваю, что мало (?). В этом случае попытка векторизации pinv является преждевременной оптимизацией. - person gg349; 01.05.2014
comment
Я думаю ты прав. Это небольшая часть единственных матриц. Я попытаюсь изолировать их, перебрать ТОЛЬКО их и использовать pinv. Может быть, этого будет достаточно быстро. Изначально у меня было много вычислений внутри цикла по всем вокселям (а не только вызов pinv), поэтому я не думаю, что именно pinv замедлял работу. Большинство этих операций уже векторизованы, и это единственный источник проблем. - person NLi10Me; 01.05.2014
comment
Хорошо, держи нас в курсе. Вы также можете попробовать использовать версию numpy, которая может быть быстрее или медленнее, см. Ссылку выше - person gg349; 02.05.2014
comment
Я действительно использовал numpy-версию. Это действительно происходит достаточно быстро, так как процент сингулярных матриц очень мал. Большое спасибо за Вашу помощь. Однако исходный вопрос все еще остается в силе: есть ли в Python способ одновременно инвертировать набор небольших матриц? - person NLi10Me; 02.05.2014
comment
Я полагаю, что другое решение вне Python - это параллельная обработка, но я ищу решение в Python. - person NLi10Me; 02.05.2014