I need to minimize a function which has the following terms in it (there are other non-linear terms as well but this is the bottleneck). I'm trying to do as much work upfront to speed up the optimization.
$$\mathrm{min} \space\space\space\space\space \mathbf{x^T}(M_1^TM_1+M_2^TM_2+...+M_r^TM_r)\mathbf{x}+\mathrm{other \space terms...}$$
Here, all matrices $M_i$ are positive, real matrices of dimension $m\times n$ achieving full rank (in the smaller dimension).
If $m\geq n$, I can collapse this expression to $\frac{1}{2}\mathbf{x^T}Q\mathbf{x}$ where $Q$ is an $n \times n$ positive definite matrix and I can proceed very efficiently; the calculation would have $\mathcal{O}(n^2)$ operations.
However, if $n\gg m$ it doesn't make sense to do this. Naïvely, I could evaluate $\sum_{i=1}^{r}||M_i\mathbf{x}||^2$ and achieve $\mathcal{O}(mnr)$ which is faster assuming $mr<n$. I'm sure we can do better.
Can I factorize $(M_1^TM_1+M_2^TM_2+...+M_r^TM_r)$ into $\tilde{M}^T\tilde{M}$ where $\tilde{M}$ is $m\times n$ such that I can evaluate $||\tilde{M}\mathbf{x}||^2$ and achieve $\mathcal{O}(mn)$ in my optimization?
Sadly this doesn't seem possible. In block matrix notation, we can define an $mr \times n$ matrix:
$$ C= \left[ \begin{array}{c|c} M_1 \\ M_2 \\ \vdots \\ M_r \\ \end{array} \right] $$
Then the problem is equivalent to $\textrm{min}\space\mathbf{x^T}C^TC\mathbf{x}$. Clearly, if $n>mr$ then the computation $C\mathbf{x}$ cannot be more performant than $\mathcal{O}(mnr)$.