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

8

dada una matriz simétrica , y una matriz arbitraria X R n × n , y un vector v R n × 1 , ¿es posible calcular la siguiente expresión en el tiempo O ( n 2 ) ?YRn×nXRn×nvRn×1O(n2)

diag(XTYX)v

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

John Smith
fuente
3
Comentario rápido: es inútil: la pregunta es equivalente a "¿es posible calcular diag ( X T Y X ) en O ( n 2 ) ?". No sé la respuesta, pero supongo que no . vdiag(XTYX)O(n2)
Federico Poloni
2
Creo que puede desempeñar algún papel en la reducción del costo porque si consideramos el cálculo de ( X T Y X ) v , es posible calcularlo con O ( n 2 ) de la siguiente manera: X T ( Y ( X v ) ) . Pero cuando se usa d i a g , aprecio que alguien pueda echarme una mano. v(XTYX)vO(n2)XT(Y(Xv))diag
John Smith
1
Para diagonal, el producto D v se puede calcular en tiempo O ( n ) . Supongo que es posible que la estructura del producto vectorial pueda explotarse, pero lo dudo. Si pudiera calcular una matriz Z en el tiempo O ( n 2 ) de modo que d i a g ( X T Y X ) = X T Y X - Z , entonces seguro, ese producto vectorial sería útil. DDvO(n)ZO(n2)diag(XTYX)=XTYXZ
Geoff Oxberry
Parece difícil encontrar tal en O ( n 2 ) . ZO(n2)
John Smith
44
Insisto: es inútil. Si tiene un procedimiento que calcula diag ( X T Y X ) v en el tiempo O ( n 2 ) , entonces también puede calcular diag ( X T Y X ) en el tiempo O ( n 2 ) : simplemente elija v como el vector de todos unos La reducción opuesta también es clara. vdiag(XTYX)vO(n2)diag(XTYX)O(n2)v
Federico Poloni

Respuestas:

2

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=(XTY)

entonces quieres calcular para cada ikaikxkiνii

y aik=lxliylk

que esO(n3).(diag(XTYX)v)i=klxliylkxkiνiO(n3)

Ahora traigamos la hipótesis: como es simétrica, y l k = y k l . En la suma, solo existe el producto x l i x k i que también es simétrico con respecto a k y l .Yylk=yklxlixkikl

Entonces (diag(XTYX)v)i=2×kl>kxliylkxkiνi+kxkiykkxkiνi

Eso es veces n ( n + 1 )n cálculos. Por lo tanto, puede dividir el cálculo entre casi2pero non.n(n+1)22n

Jean Mercat
fuente