Issue
Let's say I have a matrix X
with n, m == X.shape
in PyTorch.
What is the time complexity of calculating the pseudo-inverse with torch.pinverse
?
In other words, what is the time complexity of
X_p = torch.pinverse(X)
?
Here is the documentation
Solution
The PyTorch documentation states that pinverse is calculated using SVD (singular value decomposition). The complexity of SVD is O(n m^2)
, where m
is the larger dimension of the matrix and n
the smaller. Thus this is the complexity.
For more info, check out these pages on wikipedia:
- 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
Answered By - Maya Farber Brodsky
0 comments:
Post a Comment
Note: Only a member of this blog may post a comment.