8

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

John Smith
  • 241
  • 1
  • 2
  • 3
    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. – Federico Poloni Sep 20 '14 at 07:34
  • 2
    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. – John Smith Sep 21 '14 at 01:46
  • 1
    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. – Geoff Oxberry Sep 21 '14 at 01:52
  • It seems hard to find such $Z$ in $O(n^2)$. – John Smith Sep 21 '14 at 01:59
  • 4
    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. – Federico Poloni Sep 21 '14 at 07:05

1 Answers1

2

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

Jean Mercat
  • 31
  • 2