Implikationen der Approximation der Determinante

Es ist bekannt, dass man die Determinante einer $n\times n$ Matrix im deterministischen -Raum genau berechnen kann . Welche Komplexitätsauswirkungen hätte die Approximation der Determinante einer reellen Matrix, von höchstens ( ) im randomisierten logarithmischen Raum, also eines Genauigkeit? $\log^2(n)$ $1$ $\left\|A\right\|\leq 1$ $1/\text{poly}$

Was wäre in dieser Hinsicht die "richtige" Näherung - multiplikativ oder additiv? (siehe eine der Antworten unten).

determinant cc.complexity-theory Lior Eldar
quelle

Sollen sich diese auf einem Real RAM befinden?

$\:$

Ich bin nicht sicher, ob ich die Frage richtig verstehe, aber wenn Sie sich auf die Genauigkeit der Arithmetik beziehen, würde ich annehmen, dass jede reelle Zahl in log (n) Bits gespeichert ist.

Lior Eldar

Mit dem Risiko, die Details der Frage nicht richtig verstanden zu haben: Um die Determinante innerhalb eines Faktors approximieren zu können, muss man entscheiden können, ob eine quadratische Matrix singulär ist oder nicht, was einige Konsequenzen haben sollte.

Zum einen wird randomisiert geprüft, ob ein allgemeiner Graph eine perfekte Übereinstimmung aufweist (über die Tutte-Matrix und Schwarz-Zippel). Ich glaube nicht, dass letzteres im randomisierten Logspace bekannt ist (zB listet der Complexity Zoo zweigliedrige perfekte Übereinstimmungen als schwer für NL auf).

Magnus Wahlström
quelle

Danke Magnus, obwohl ich tatsächlich über einen additiven Approximationsfehler nachgedacht habe. In diesem Fall müssen Sie nicht unterscheiden, ob eine Matrix singulär ist oder nicht. Die multilipulative Approximation kann ebenfalls von Interesse sein, daher bin ich mir im Moment nicht sicher, welche Definition die beste ist.

Lior Eldar

@LiorEldar, sicherlich auch mit additivem Approximationsfehler, wenn die Einträge in der Matrix ganze Zahlen sind und der additive Fehler unter 0,5 liegt, haben Sie einen narrensicheren Singularitätstest?

Peter Taylor

Hallo Peter Taylor, ich denke, dass Sie, um von einer Genauigkeit von 0,5 zu sprechen, zunächst irgendwie die größte Operator-Norm angeben müssen, die Sie unterstützen. So zum Beispiel , wenn die Eingabe

hat

, dann Determinante additive Fehler können sein

. Also selbst wenn Sie Ihre Eingabe Ihnen als abgeschnitten ganzen Zahlen angegeben, die jeweils

Bits, dann ist die maximale Norm , für die Sie erforderlich sind , um die Determinante zu nähern wäre

in Bezug auf ganze Zahlen, was bedeutet , dass

A

$A$

‖ A ‖ \leq 1

$\left\|A\right\|\leq 1$

1 / p o l y (n)

$1/poly(n)$

l o g (n)

$log(n)$

n^{n}

$n^n$

0.5

$0.5$ Approximationsfehler ist viel kleiner als

relativ zu

1 / p o l y (n)

$1/poly(n)$

‖ A ‖

$\left\|A\right\|$

Lior Eldar

Ich denke, das Problem mit additiven Fehlern in Bezug auf die Norm ist, dass sie nicht wirklich gut skaliert werden. Say I hatte einen Algorithmus, der eine gab

Approximationsfehler relativ zu

. Nun sei

die

Blockdiagonalmatrix, die unter Verwendung von

Kopien von

als Blöcke gebildet wird. Dann

1 / p o l y (n)

$1/poly(n)$

| | A | |

$||A||$

A^{'}

$A'$

n^{3} \times n^{3}

$n^3 \times n^3$

n^{2}

$n^2$

A

$A$

| | A | | = | | A^{'} | |

$||A||=||A'||$ , aber

, also a

additive Fehler für

Skalen auf einen

additive Fehler für

det (A^{'}) = det (A)^{n^{2}}

$\det(A')=\det(A)^{n^2}$

| | A^{'} | | / p o l y (n)

$||A'||/poly(n)$

d e t (A^{'})

$det(A')$

O (1)

$O(1)$

d e t (A)

$det (A)$

Kevin Costello

Implikationen der Approximation der Determinante

Antworten: