I want to calculate $$y^T \mbox{diag}(A^T B A) \,y$$ where


* $y$ is a $n \times 1$ vector.
* $A$ is a $m \times n$ matrix where $n \gg m$.
* $B$ is a $m \times m$ symmetric positive definite matrix; the Cholesky decomposition $B = LL^T$ is precomputed if it is needed.


Is it possible to calculate the above expression at a cost of $O(m n)$ flops? 



How to calculate $y^T \mbox{diag}(A^T B A) \,y$ efficiently?
$$\mathrm y^\top \mbox{diag}(\mathrm A^\top \mathrm B \,\mathrm A) \,\mathrm y = \sum\_{k=1}^n \mathrm e\_k^\top\mathrm A^\top \mathrm B \,\mathrm A \,\mathrm e\_k \, y\_k^2 = \sum\_{k=1}^n \mathrm a\_k^\top \mathrm B \, \mathrm a\_k \, y\_k^2$$


where $\mathrm a\_k \in \mathbb R^m$ is the $k$-th column of $\rm A$. Since each $\mathrm a\_k^\top \mathrm B \, \mathrm a\_k$ costs $\mathcal O (m^2)$ operations, the total computational cost is $\mathcal O (m^2 n)$ operations.


However, if $\rm B$ is a **diagonal** matrix, then each $\mathrm a\_k^\top \mathrm B \, \mathrm a\_k$ only costs $\mathcal O (m)$ operations, and the total computational cost is $\mathcal O (m n)$ operations.


