0
$\begingroup$

Assume that matrix $A$ is defined as follows:

$A = X \cdot X^T$

Where $X$ is a Real matrix with more columns than rows, and $A$ has a matrix inverse.

One can find the inverse of $A$ defined as $A^{-1}$ using Gaussian Elimination, or LU Decomposition (find articles here and here on pivoting), but this has a complexity of $O(n^3)$.

Knowing that this matrix is symmetric and (I think?) positive definite, is there a faster way to compute the exact inverse?


The background on the problem:

For reference, I am trying to use this to quickly solve the following equation for $Z$:

$Z = Y X^T(X X^T)^{-1}X$

Where $X$ and $Y$ are known, and both are Real.

I am solving this in Python code, and I have not been able to find a package to calculate the inverse quickly as I am using exact rationals with the quicktions package. sympy.Matrix.inv is slower than just writing out code to do Gaussian Elimination.

I've seen this article Don't invert that matrix, but I don't know a way to solve this system without inverting a matrix.

$\endgroup$
  • $\begingroup$ Cholesky factorisation? $\endgroup$ – copper.hat Jun 7 '17 at 16:16
  • $\begingroup$ Is that the correct equation? It looks like it simplifies to $Z=Y$. $\endgroup$ – Joppy Jun 7 '17 at 16:48
  • $\begingroup$ Yes, it is the correct equation. It does not simplify to $Z=Y$ $\endgroup$ – Paul Terwilliger Jun 7 '17 at 17:03
  • $\begingroup$ math.stackexchange.com/questions/182662/… $\endgroup$ – Keith McClary Jun 7 '17 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.