¿Hay algún método mejorado para calcular la siguiente expresión?

dada una matriz simétrica , y una matriz arbitraria , y un vector , ¿es posible calcular la siguiente expresión en el tiempo ? $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$

donde devuelve un matriz con sus principales elementos diagonales iguales a los de y los elementos fuera de la diagonal igual a 0, y es la transpuesta de . $diag(X)$ $n \times n$ $X$ $X^T$ $X$

optimization algorithms performance matrix complexity John Smith
fuente

Comentario rápido:

es inútil: la pregunta es equivalente a "¿es posible calcular

?". No sé la respuesta, pero supongo que no .

v

$v$

diag (X^{T} Y X)

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

O (n^{2})

$O(n^2)$

Federico Poloni

Creo que

puede desempeñar algún papel en la reducción del costo porque si consideramos el cálculo de

, es posible calcularlo con

siguiente manera:

. Pero cuando se usa

, aprecio que alguien pueda echarme una mano.

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

Para

diagonal, el producto

se puede calcular en tiempo

. Supongo que es posible que la estructura del producto vectorial pueda explotarse, pero lo dudo. Si pudiera calcular una matriz

en el tiempo

modo que

, entonces seguro, ese producto vectorial sería útil.

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

Parece difícil encontrar tal

Z

$Z$

O (n^{2})

$O(n^2)$

John Smith

Insisto:

es inútil. Si tiene un procedimiento que calcula

en el tiempo

, entonces también puede calcular

en el tiempo

: simplemente elija

como el vector de todos unos La reducción opuesta también es clara.

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

Permítame intentar ayudar, pero corríjame si me equivoco porque solo estoy sacando eso de mi sombrero:

Simplemente expandiré el cálculo para ayudar a ver lo que está sucediendo.

Escribamos $A = (X^TY)$

entonces quieres calcular para cada $\sum_k{a_{ik}x_{ki}\nu_i}$ $i$

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

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

Ahora traigamos la hipótesis: como es simétrica, . En la suma, solo existe el producto que también es simétrico con respecto a y . $Y$ $y_{lk}=y_{kl}$ $x_{li}x_{ki}$ $k$ $l$

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

Eso es veces $n$ cálculos. Por lo tanto, puede dividir el cálculo entre casipero no. $\frac{n(n+1)}{2}$ $2$ $n$

Jean Mercat
fuente

¿Hay algún método mejorado para calcular la siguiente expresión?

Respuestas: