Gibt es eine verbesserte Methode zur Berechnung des folgenden Ausdrucks?

gegeben eine symmetrische Matrix und eine beliebige Matrix und einen Vektor , ist es möglich, den folgenden Ausdruck in -Zeit zu berechnen ? $Y \in \mathbb{R}^{n \times n}$ $X \in \mathbb{R}^{n \times n}$ $v \in \mathbb{R}^{n \times 1}$ $O(n^2)$

d i a g (X^{T} Y X) \cdot v

$diag(X^TYX) \cdot v$

wobei eine Matrix zurückgibt, deren Hauptdiagonalelemente gleich denen von und nicht diagonalen Elementen gleich 0 sind und die Transponierte von . $diag(X)$ $n \times n$ $X$ $X^T$ $X$

optimization algorithms performance matrix complexity John Smith
quelle

Kurze Bemerkung: ist nutzlos: Die Frage ist äquivalent zu " es möglich, in zu berechnen ?". Ich weiß die Antwort nicht, aber ich vermute, dass es nein ist .

v

$v$

diag (X^{T} Y X)

$\operatorname{diag}(X^TYX)$

O (n^{2})

$O(n^2)$

Federico Poloni

Ich denke, kann eine Rolle bei der Reduzierung der Kosten spielen, denn wenn wir die Berechnung von , ist es möglich, mit wie folgt berechnet zu werden: . Aber wenn verwendet wird, schätze ich, dass mir jemand könnte.

v

$v$

(X^{T} Y X) v

$(X^T Y X) v$

O (n^{2})

$O(n^2)$

X^{T} (Y (X v))

$X^T (Y (X v))$

d i a g

$diag$

John Smith

Für die Diagonale kann das Produkt in berechnet werden. Ich nehme an, es ist möglich, dass die Vektorproduktstruktur ausgenutzt wird, aber ich bezweifle es. Wenn Sie eine Matrix in Zeit so berechnen könnten, dass , dann wäre dieses Vektorprodukt sicher nützlich.

D

$D$

D v

$Dv$

O (n)

$O(n)$

Z

$Z$

O (n^{2})

$O(n^{2})$

d i a g (X^{T} Y X) = X^{T} Y X - Z

$diag(X^{T}YX) = X^{T}YX - Z$

Geoff Oxberry

Es scheint schwierig zu sein, ein solches in .

Z

$Z$

O (n^{2})

$O(n^2)$

John Smith

Ich bestehe darauf: ist nutzlos. Wenn man ein Verfahren , das berechnet in Zeit, dann kann man auch compute in Zeit : wähle einfach als den Vektor aller. Die entgegengesetzte Reduktion ist ebenfalls klar.

v

$v$

diag (X^{T} Y X) v

$\operatorname{diag}(X^TYX)v$

O (n^{2})

$O(n^2)$

diag (X^{T} Y X)

$\operatorname{diag}(X^TYX)$

O (n^{2})

$O(n^2)$

v

$v$

Federico Poloni

Lassen Sie mich versuchen zu helfen, aber bitte korrigieren Sie mich, wenn ich falsch liege, weil ich das nur aus meinem Hut ziehe:

Ich werde nur die Berechnung erweitern, um zu sehen, was passiert.

Schreiben wir $A = (X^TY)$

Sie möchten also für jedes berechnen $\sum_k{a_{ik}x_{ki}\nu_i}$ $i$

und $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}$ , was . $O(n^3)$

Lassen Sie uns nun die Hypothese bringen: Da symmetrisch ist, ist . In der Summe gibt es nur das Produkt , das auch in Bezug auf und symmetrisch ist . $Y$ $y_{lk}=y_{kl}$ $x_{li}x_{ki}$ $k$ $l$

Also $\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}$

Das sind mal Berechnungen. Sie können die Berechnung also durch fast teilen, aber nicht durch . $n$ $\frac{n(n+1)}{2}$ $2$ $n$

Jean Mercat
quelle

Gibt es eine verbesserte Methode zur Berechnung des folgenden Ausdrucks?

Antworten: