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

Improve this question
$\endgroup$
5
  • 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, 2014 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, 2014 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, 2014 at 1:52
  • $\begingroup$ It seems hard to find such $Z$ in $O(n^2)$. $\endgroup$
    – John Smith
    Sep 21, 2014 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, 2014 at 7:05

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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