8
$\begingroup$

given a symmetric matrix $Y \in \mathbb{R}^{n \times n}$, and an arbitrary matrix $X \in \mathbb{R}^{n \times n}$, and a vector $v \in \mathbb{R}^{n \times 1}$, is it possible to compute the following expression in $O(n^2)$ time?

$$diag(X^TYX) \cdot v$$

where $diag(X)$ returns a $n \times n$ matrix with its main diagonal elements equal to those of $X$ and off-diagonal elements equal to 0, and $X^T$ is the transpose of $X$.

$\endgroup$
  • 3
    $\begingroup$ Quick remark: $v$ is useless: the question is equivalent to "is it possible to compute $\operatorname{diag}(X^TYX)$ in $O(n^2)$?". I don't know the answer, but my guess is that it is no. $\endgroup$ – Federico Poloni Sep 20 '14 at 7:34
  • 2
    $\begingroup$ I think $v$ may play some role in reducing the cost because if we consider the computation of $(X^T Y X) v$, it is possible to be computed with $O(n^2)$ as follows: $X^T (Y (X v))$. But when $diag$ is used, I appreciate someone could give me a hand. $\endgroup$ – John Smith Sep 21 '14 at 1:46
  • 1
    $\begingroup$ For $D$ diagonal, the product $Dv$ can be computed in $O(n)$ time. I suppose it's possible that the vector product structure could be exploited, but I doubt it. If you could compute a matrix $Z$ in $O(n^{2})$ time such that $diag(X^{T}YX) = X^{T}YX - Z$, then sure, that vector product would be useful. $\endgroup$ – Geoff Oxberry Sep 21 '14 at 1:52
  • $\begingroup$ It seems hard to find such $Z$ in $O(n^2)$. $\endgroup$ – John Smith Sep 21 '14 at 1:59
  • 4
    $\begingroup$ I insist: $v$ is useless. If you have a procedure that computes $\operatorname{diag}(X^TYX)v$ in $O(n^2)$ time, then you can also compute $\operatorname{diag}(X^TYX)$ in $O(n^2)$ time: just choose $v$ as the vector of all ones. The opposite reduction is also clear. $\endgroup$ – Federico Poloni Sep 21 '14 at 7:05
2
$\begingroup$

Let me try to help, but please correct me if I am wrong because I am just pulling that from my hat :

I will just expand the computation to help to see what is happening.

Let us write $A = (X^TY)$

so you want to compute $\sum_k{a_{ik}x_{ki}\nu_i}$ for every $i$

and $a_{ik}=\sum_l{x_{li}y_{lk}}$

$\left(diag(X^TYX)⋅v\right)_i =\sum_k{\sum_l{x_{li}y_{lk}}x_{ki}\nu_i} $ wich is $O(n^3)$.

Now let us bring the hypothesis: Since $Y$ is symmetric, $y_{lk}=y_{kl}$. In the sum, there is only the product $x_{li}x_{ki}$ that is also symmetric with respect to $k$ and $l$.

So $\left(diag(X^TYX)⋅v\right)_i = 2\times\sum_k{\sum_{l>k}{x_{li}y_{lk}}x_{ki}\nu_i} + \sum_{k}{x_{ki}y_{kk}x_{ki}\nu_i}$

That is $n$ times $\frac{n(n+1)}{2}$ computations. So you can divide computation by almost $2$ but not $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.