-4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ What is $\mbox{diag} (\cdot)$? $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 4, 2018 at 15:06
  • $\begingroup$ @RodrigodeAzevedo diag(.) is the diagonal of the matrix. $\endgroup$
    – Alaya
    Commented Apr 4, 2018 at 15:30
  • $\begingroup$ Is $\mbox{diag} (A)$ a diagonal matrix whose diagonal entries are $a_{11}, a_{22}, \dots, a_{nn}$? $\endgroup$
    – Rodrigo de Azevedo
    Commented Apr 4, 2018 at 15:32
  • $\begingroup$ @RodrigodeAzevedo yes $\endgroup$
    – Alaya
    Commented Apr 4, 2018 at 15:40

1 Answer 1

Reset to default
1
$\begingroup$

$$\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.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .