# Fast computation of square root inverse of matrix, matrix being determined from Ax=b form

I have an equation of the form $J^Te=f$, where $e$ and $f$ are known vectors and $J$ is an unknown matrix.

How can I efficiently compute $J^T(JJ^T)^{-1/2}e$ ?

My motivation to address this problem is that, as a part of a bigger problem I need to compute matrix $J$ then compute $J^T(JJ^T)^{-1/2}e$. However, computation of matrix $J$ is expensive and $J$ results to be a large matrix, thereby the determination of product-transpose-squareroot-inverse of it is taking a lot of time. Hence, I'm planning to bypass the expensive computation of $J$ with the help some known vectors $e$ and $f$ and the relation $J^Te=f$.

• Welcome to Scicomp.SE! Do you have any indication whether the quantity you are looking for can actually be computed given only $e$ and $f$? (The one equation $J^T e=f$ is not nearly enough to uniquely determine $J$.) – Christian Clason Mar 5 '16 at 17:02
• @ChristianClason I understand that J may not be unique. If there is a possibility, I want to look for a computation procedure which returns same $J^T(JJ^T)^{-1/2}e$ value irrespective of $J$ – user3619023 Mar 5 '16 at 17:50
• The point is that there might not be a unique value irrespective of $J$. (In fact, I'd rather expect so.) Maybe you could edit the question to add a bit more detail where this problem is coming from? – Christian Clason Mar 5 '16 at 18:13
• @ChristianClason I hope the edit helps – user3619023 Mar 5 '16 at 21:29
• As an example, (unless I'm mistaken) if neither $e$ or $f$ contained any zeros, then you could define $J$ to be a diagonal matrix, then $J(JJ)^{-1/2}e=e$ – Steve Mar 5 '16 at 23:17

The problem is wildly underdetermined. Of the infinitely many equations for $J$ of the equation $J^T e=f$ is the (rank-one) matrix $$J^T = \frac{f e^T}{\|e\|^2}.$$ For this, you have that $$JJ^T = \frac{e f^Tf e^T}{\|e\|^4} = \|f\|^2 \frac{e e^T}{\|e\|^4}.$$
Interestingly, this matrix satisfies $$(JJ^T)(JJ^T) = \|f\|^4 \frac{e e^T}{\|e\|^4} \frac{e e^T}{\|e\|^4} = \|f\|^4 \frac{e e^T e e^T}{\|e\|^8} = \|f\|^4 \frac{e e^T}{\|e\|^6} = \frac{\|f\|^2}{\|e\|^2} JJ^T.$$ This means that $$(JJ^T)^{1/2} = \frac{\|e\|}{\|f\|} JJ^T.$$ This allows you to compute the quantity you are interested in.
EDIT: To see how the last line follows, take the square of the left and right hand sides (i.e., multiply each side with itself) to obtain $$JJ^T = \frac{\|e\|^2}{\|f\|^2} (JJ^T) (JJ^T).$$ This is, up to division by the factor on both sides, the same as before.
So, how to proceed then: We know that $A := JJ^T = c ee^T$ where $c=\|f\|^2/\|e\|^4$. In other words, if you multiply $A$ by $e$, you get a multiple of $c\|e\|^2 e$ from it. Conversely, this means that applying $A^{-1}$ to this direction $e$, you get one over this multiple, i.e., $A^{-1}e=\frac{1}{c\|e\|^2}e$. (This inverse does not strictly exist -- I'm just taking the pseudo-inverse $A^\dagger$ when I write $A^{-1}$). This brings us back to the equation $$(JJ^T)^{-1/2} = \frac{\|f\|}{\|e\|} A^{-1}$$ and consequently $$(JJ^T)^{-1/2}e = \frac{\|f\|}{\|e\|} A^{-1}e = \frac{\|f\|}{c\|e\|^2} e = \frac{\|f\|\|e\|^4}{\|f\|^2\|e\|^2} e = \frac{\|e\|^2}{\|f\|} e.$$ With this, you get $$J^T(JJ^T)^{-1/2}e = \frac{1}{\|f\|} fe^Te = \frac{\|e\|^2}{\|f\|} f.$$
All of this said, this is just one choice for $J$. Other choices may yield different results.