Cálculo eficiente de la matriz de raíz cuadrada inversa

15

Un problema común en estadística es calcular la inversa de la raíz cuadrada de una matriz simétrica positiva definida. ¿Cuál sería la forma más eficiente de calcular esto?

Encontré algo de literatura (que aún no he leído) y algún código R incidental aquí , que reproduciré aquí por conveniencia

# function to compute the inverse square root of a matrix
fnMatSqrtInverse = function(mA) {
  ei = eigen(mA)
  d = ei$values
      d = (d+abs(d))/2
      d2 = 1/sqrt(d)
      d2[d == 0] = 0
      return(ei$vectors %*% diag(d2) %*% t(ei$vectors))
}

No estoy completamente seguro de entender la línea d = (d+abs(d))/2. ¿Existe una forma más eficiente de calcular la matriz inversa de raíz cuadrada? La eigenfunción R llama LAPACK .

linear-algebra numerical-analysis matrix tchakravarty
fuente

Siempre que sea real, es igual a . Esto efectivamente elimina cualquier valor propio negativo que pueda tener la matriz. ¿Necesita todas las entradas de la matriz

, o es suficiente para poder multiplicar

por un vector arbitrario

?

d

$d$

(d + | d |) / 2

$(d+|d|)/2$

max (d, 0)

$\max(d,0)$

A^{- 1 / 2}

$A^{-1/2}$

A^{- 1 / 2}

$A^{-1/2}$

x

$x$

Daniel Shapero

@DanielShapero Gracias por tu comentario. Entonces, si tengo una matriz PSD, ¿no necesito esa línea? Mi aplicación requiere calcular formas cuadráticas como

A^{- 1 / 2} B A^{- 1 / 2}

$A^{-1/2}BA^{-1/2}$ .

tchakravarty

No estoy familiarizado con R, pero dada la línea 7, supongo que tiene una indexación lógica como Matlab. Si es así, le sugiero que reescriba la línea 5 como d[d<0] = 0, que es más expresiva.

Federico Poloni

¿Es correcto este código? Lo ejecuté en un ejemplo simple en matlab y encontré que la respuesta era incorrecta. Mi matriz es positiva definida pero definitivamente no simétrica. Vea mi respuesta a continuación: he transferido el código a matlab.

roni

10

El código que ha publicado utiliza la descomposición del valor propio de la matriz simétrica para calcular . $A^{-1/2}$

La declaración

d = (d + abs (d)) / 2

efectivamente toma cualquier entrada negativa en d y la establece en 0, mientras deja solo las entradas no negativas. Es decir, cualquier valor propio negativo de se trata como si fuera 0. En teoría, todos los valores propios de A no deberían ser negativos, pero en la práctica es común ver pequeños valores propios negativos cuando calcula los valores propios de un supuesto supuestamente positivo. matriz de covarianza que es casi singular. $A$

Si realmente necesita la inversa de la raíz cuadrada de la matriz simétrica de , y es razonablemente pequeña (no más grande que decir 1,000 por 1,000), entonces esto es tan bueno como cualquier método que pueda usar. $A$ $A$

En muchos casos, puede utilizar un factor de Cholesky de la inversa de la matriz de covarianza (o prácticamente el mismo, el factor de Cholesky de la matriz de covarianza en sí). Calcular el factor de Cholesky suele ser un orden de magnitud más rápido que calcular la descomposición del valor propio para matrices densas y mucho más eficientes (tanto en tiempo de cómputo como en almacenamiento requerido) para matrices grandes y dispersas. Por lo tanto, usar la factorización de Cholesky se vuelve muy deseable cuando es grande y escaso. $A$

Brian Borchers
fuente

66

La respuesta de Brian da buenos consejos: use el factor Cholesky en su lugar (si puede). Hay otra optimización que puede hacer además de eso: no calcule su matriz PSD . A menudo obtienes de un cálculo como , con rectangular. En este caso, es suficiente calcular una descomposición QR de para obtener el factor de Cholesky de , con mucha mayor precisión.

A

$A$

A

$A$

A = B^{T} B

$A=B^TB$

B

$B$

B

$B$

R

$R$

A

$A$

Federico Poloni

5

En mi experiencia, el método de Newton polar de Higham funciona mucho más rápido (ver Capítulo 6 de Funciones de matrices de N. Higham). En esta breve nota mía hay tramas que comparan este método con los métodos de primer orden. Además, se presentan citas de varios otros enfoques de matriz-raíz cuadrada, aunque la iteración de Newton polar parece funcionar mejor (y evita hacer cálculos de vectores propios).

% compute the matrix square root; modify to compute inverse root.
function X = PolarIter(M,maxit,scal)
  fprintf('Running Polar Newton Iteration\n');
  skip = floor(maxit/10);
  I = eye(size(M));
  n=size(M,1);
  if scal
    tm = trace(M);
    M  = M / tm;
  else
    tm = 1;
  end
  nm = norm(M,'fro');

  % to compute inv(sqrt(M)) make change here
  R=chol(M+5*eps*I);

  % computes the polar decomposition of R
  U=R; k=0;
  while (k < maxit)
    k=k+1;
    % err(k) = norm((R'*U)^2-M,'fro')/nm;
    %if (mod(k,skip)==0)
    %  fprintf('%d: %E\n', k, out.err(k));
    %end

    iU=U\I;
    mu=sqrt(sqrt(norm(iU,1)/norm(U,1)*norm(iU,inf)/norm(U,inf)));
    U=0.5*(mu*U+iU'/mu);

   if (err(k) < 1e-12), break; end
  end
  X=sqrt(tm)*R'*U;
  X = 0.5*(X+X');
end

suvrit
fuente

0

Optimiza tu código:

Opción 1: optimice su código R:
a. Puede apply()una función para dque a la vez max(d,0)y d2[d==0]=0en un solo bucle.
si. Intente operar ei$valuesdirectamente.

Opción 2: usar C ++:
reescribe toda la función en C ++ con RcppArmadillo. Aún podrá llamarlo desde R.

poder
fuente

Cálculo eficiente de la matriz de raíz cuadrada inversa

Respuestas: