Implications de l'approximation du déterminant

On sait que l'on peut calculer exactement le déterminant d'une matrice dans l' espace determinstic . Quelles seraient les implications de complexité d'approximer le déterminant d'une matrice réelle, de norme au plus ( ) dans l'espace logarithmique randomisé, jusqu'à un précision? $n\times n$ $\log^2(n)$ $1$ $\left\|A\right\|\leq 1$ $1/\text{poly}$

À cet égard, quelle serait l'approximation "correcte" à demander - multiplicative ou additive? (voir une des réponses ci-dessous).

determinant cc.complexity-theory Lior Eldar
la source

Sont-ils censés être sur une vraie RAM?

$\:$

Je ne suis pas sûr d'avoir bien compris la question, mais si vous vous référez à la précision de l'arithmétique, je suppose que chaque nombre réel est stocké dans des bits de log (n).

Lior Eldar

Avec le risque de ne pas avoir bien compris les détails de la question: être en mesure d'approximer le déterminant dans n'importe quel facteur nécessite de pouvoir décider si une matrice carrée est singulière ou non, ce qui devrait avoir des conséquences.

D'une part, il donne un test aléatoire pour savoir si un graphique général a une correspondance parfaite (via la matrice de Tutte et Schwarz-Zippel). Je ne pense pas que ce dernier soit connu dans l'espace de journalisation aléatoire (par exemple, le Complexity Zoo répertorie la correspondance parfaite bipartite comme difficile pour NL).

Magnus Wahlström
la source

Merci Magnus, même si je pensais en fait à une erreur d'approximation additive, auquel cas vous ne serez pas obligé de dire si une matrice est singulière ou non. Une approximation multilatérale peut également être intéressante, donc pour le moment, je ne sais pas quelle est la meilleure définition.

Lior Eldar

@LiorEldar, sûrement même avec une erreur d'approximation additive, si les entrées dans la matrice sont des entiers et que la limite d'erreur additive est inférieure à 0,5, vous avez un test de singularité à toute épreuve?

Peter Taylor

Salut Peter Taylor, je pense que pour parler de, disons, une précision de 0,5, vous devez d'abord définir la plus grande norme d'opérateur que vous supportez. Ainsi, par exemple, si votre entrée

, alors votre erreur additive déterminante peut être

. Donc, même si votre entrée vous est donnée sous forme d'entiers tronqués, chacun de

bits, alors la norme maximale pour laquelle vous devez approximer le déterminant serait

en termes d'entiers, ce qui signifie que

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$ l'erreur d'approximation est beaucoup plus petite que

rapport à

1 / p o l y (n)

$1/poly(n)$

‖ A ‖

$\left\|A\right\|$

Lior Eldar

Je pense que le problème avec l'erreur additive par rapport à la norme est qu'elle ne se modifie pas vraiment bien. Supposons que j'avais un algorithme qui a donné une erreur d'approximation de

rapport à

. Soit maintenant

la matrice diagonale de blocs

formée en utilisant

copies de

comme blocs. Alors

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'||$ , mais

, donc a

erreur additive pour

échelles à uneerreur additive

pour

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

Implications de l'approximation du déterminant

Réponses: