I want to calculate $y^T \cdot \operatorname{diag}(A^T B A) \cdot y$.

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

Is it possible to calculate the above expression in $O(Nm)$ complexity?

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?

I want to calculate y' * diag(A' * B * A) * y

• y is a N * 1 vector
• A is a m * N matrix where N >> m
• B is a m * m matrix, and B is a symmetric positive definite matrix, the Cholesky decomposition B = L * L' is precomputed if it is needed.

Is it possible to calculate the above expression in O(N*m) complexity?

I want to calculate $y^T \cdot \operatorname{diag}(A^T B A) \cdot y$.

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

Is it possible to calculate the above expression in $O(Nm)$ complexity?