This question is related to this question with a slightly more general setting. A good speedup on this could improve performances of a decision process in multi-objective optimization that I designed.
Suppose that $m\leq n$. Let $M\in\mathbb R^{n\times n}$ and $N\in\mathbb R^{m\times m}$ be some symmetric positive semi-definite matrices, let also $A\in\mathbb R^{m\times n}$.
Suppose further that both $M$ and $N$ factorize respectively as $UU^T$ and $VV^T$ with $U\in\mathbb R^{n\times n}$ and $V\in\mathbb R^{m\times m}$. The goal is to find an efficient algorithm to factorize the PSD $AMA^T+N$ into $WW^T$ without necessarilly having to compute $AMA^T+N$ itself.
The naive cost is to compute $AMA^T+N$ in $O(mn^2+nm^2)$ operations and then perform a Cholesky factorization to get $WW^T$ which is done in $O(m^3)$. Since $m\leq n$ the total cost is $O(mn^2)$. I am wondering if there is any hope for a better runtime by taking advantage of the factorizations of $M$ and $N$.
The first idea that comes to mind is then to do $(AU)(AU)^T+VV^T$ and therefore it feels like we can decompose the problem in two :
- find some matrix $W_1\in\mathbb R^{m\times m}$ such that $W_1W_1^T=(AU)(AU)^T$ without having to compute all of $AUU^TA^T$.
- from $W_1W_1^T+VV^T$ find $WW^T$.
Any idea is welcome.