Какова временная сложность псевдообратного в pytorch (то есть torch.pinverse)?

Question

Допустим, у меня есть матрица X с n, m == X.shape в PyTorch . Какова временная сложность вычисления псевдообратного с torch.pinverse?

Другими словами, какова временная сложность

X_p = torch.pinverse(X)

?

Здесь документация

Answer 1

Документация PyTorch гласит, что пинверс рассчитывается с использованием SVD (разложение по сингулярному значению). Сложность SVD составляет O(n m^2), где m - больше размер матрицы, а n - меньше. Таким образом, это сложность.

Для получения дополнительной информации, проверьте эти страницы в Википедии:

• https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse#Singular_value_decomposition_(SVD)
• https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra