Effiziente Berechnung der Quadratwurzel-Inverse

15

Ein häufiges Problem in der Statistik ist die Berechnung der Quadratwurzel einer symmetrischen positiven definitiven Matrix. Was wäre der effizienteste Weg, dies zu berechnen?

Ich bin auf Literatur gestoßen (die ich noch nicht gelesen habe) und habe hier zufälligen R-Code gefunden , den ich hier der Einfachheit halber wiedergeben werde

# 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))
}

Ich bin nicht ganz sicher, ob ich die Zeile verstehe d = (d+abs(d))/2. Gibt es eine effizientere Methode zur Berechnung der Quadratwurzel-Inversen? Die R- eigenFunktion ruft LAPACK auf .

linear-algebra numerical-analysis matrix tchakravarty
quelle

Vorausgesetzt,

ist real,

ist gleich

. Dadurch werden negative Eigenwerte der Matrix effektiv beseitigt. Müssen Sie alle Einträge der Matrix

, oder genügt es , zu vermehren zu können ,

durch einen beliebigen Vektor

?

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 Vielen Dank für Ihren Kommentar. Wenn ich also eine PSD-Matrix habe, brauche ich diese Zeile nicht? Meine Anwendung erfordert , wie beispielsweise quadratische Formen Rechen

.

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

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

Tschakravarty

Ich bin nicht mit R vertraut, aber in Zeile 7 gehe ich davon aus, dass es eine logische Indizierung wie Matlab hat. Wenn ja, empfehle ich Ihnen, Zeile 5 als umzuschreiben d[d<0] = 0, was aussagekräftiger ist.

Federico Poloni

Ist dieser Code korrekt? Ich habe es an einem einfachen Beispiel in matlab ausgeführt und fand die Antwort falsch. Meine Matrix ist definitiv positiv, aber definitiv nicht symmetrisch. Bitte beachten Sie meine Antwort unten: Ich habe den Code an matlab übertragen.

Roni

10

$A^{-1/2}$

Die Aussage

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

$A$

$A$ $A$

$A$

Brian Borchers
quelle

6

A

$A$

A

$A$

A = B^{T} B

$A=B^TB$

B

$B$

B

$B$

R

$R$

A

$A$

5

Nach meiner Erfahrung funktioniert die Polar-Newton-Methode von Higham viel schneller (siehe Kapitel 6 der Funktionen von Matrizen von N. Higham). In dieser kurzen Notiz von mir gibt es Diagramme, die diese Methode mit Methoden erster Ordnung vergleichen. Es werden auch Zitate zu mehreren anderen Matrix-Quadratwurzel-Ansätzen vorgestellt, obwohl meistens die polare Newton-Iteration am besten zu funktionieren scheint (und es vermeidet, Eigenvektorberechnungen durchzuführen).

% 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
quelle

0

Optimieren Sie Ihren Code:

Option 1 - Optimieren Sie Ihren R-Code:
a. Du kannst apply()eine Funktion dazu dsowohl max(d,0)als auch d2[d==0]=0in einer Schleife ausführen.
b. Versuchen Sie es ei$valuesdirekt weiter.

Option 2 - Verwenden Sie C ++:
Schreiben Sie die gesamte Funktion in C ++ mit RcppArmadillo. Sie können es weiterhin von R aus anrufen.

Leistung
quelle

Effiziente Berechnung der Quadratwurzel-Inverse

Antworten: