Cómo determinar si una matriz es cerca de ser negativo (semi-)definitiva?

Question

Preguntas:
1. Es allí una manera simple, interpretables manera determinar la distancia/la cercanía de una matriz a de ser no positivo (semi-)definitiva?

2. O: ¿cómo puedo sistemáticamente crear matrices que son apenas positivo (semi-)definitiva?

Antecedentes: he estado estudiando el comportamiento de los distintos estimadores utilizados en el modelado de ecuaciones estructurales (como ML y le gusta). Mi enfoque ahora está en su convergencia comportamiento cuando estos estimadores se basan en varianza-covarianza (VCV) matrices que están cerca de ser inválida VCV s (= no positivo (semi-)definitiva). Hasta ahora, he creado más crudamente por ensayo y error.

Answer 1

Como la Wikipedia dice: "Un Hermitian $n \times n$ matriz $A$ se define como positivo-definida (PD) si el escalar $b^T A b$ es positivo para todos los no-cero vector columna $b$ de % de $n$ números reales". Además, $A$ puede ser equivalentemente ser definido como DP en términos de sus autovalores $\lambda$ (todas positivas) y en términos de la descomposición de Cholesky $A = LL^T$ (existente).

1. La forma más rápida para comprobar, por tanto, si una matriz dada $A$ es la EP es comprobar si $A$ tiene una descomposición de Cholesky. Si la descomposición de Cholesky, se produce un error, $A$ no es un EP de la matriz. Dado que el $A$ es PD esperamos que todos los elementos de la diagonal de $L$ a ser real y estrictamente positivo. Cuanto más cerca están de $0$ más cerca de la matriz $A$ es no ser la enfermedad de parkinson. (Esto se relaciona estrechamente con un cuarto de las características de la EP matrices que es positivo líder principal de los menores de edad.) Más rigurosamente también se puede comprobar que los valores propios de la misma y ver si son todos positivos. Cuanto más cerca están de $0$ más cerca de $A$ es no ser la enfermedad de parkinson. Esto también permite una interpretación directa de "¿por qué $A$ no es EP". Como un autovalor se acerca más y más a $0$ esto significa que la columna espacio atravesado por $A$ está disminuyendo, y en algún momento uno de sus dimensiones se derrumba sobre otra, es decir. tenemos al menos una columna que es la combinación lineal de las otras columnas en la matriz de $A$.

2. Dada una matriz $A$ PD es la manera más rápida para obtener una matriz de "cerca" es que no es la PD será el conjunto de los elementos de la diagonal de $L$ a 0 (o algo muy pequeño). Esa es una manera, pero es un poco contundente. Que efectivamente va a invalidar uno o más de $A$'s líder principal de los menores de edad. Una segunda forma que es más cuidadosamente examinado sería el uso de la descomposición en valores singulares $A = USV^T$ y configura uno de los elementos de la diagonal celebración de los valores propios en $S$ a $0$. Esto garantizará que la reconstrucción de la matriz $A^{s_n=0}$ será el más cercano de la matriz de a $A$ en el plazo de la norma de Frobenius (dado que usted elija para "invalidar" la más pequeña de singular valor $s$). Este método se relacionan directamente con la caracterización de $A$ como EP basado en sus valores propios; en el caso de una matriz de covarianza $A$ los valores singulares de $A$ equiparar sus valores propios, por lo que cuando se establezca que uno de los valores singulares de a $0$ que efectivamente uno de los autovalores a $0$. Anexo: también podemos utilizar este autovalor metodología basada directamente a crear cerca de PD matrices sin iniciar la DP matriz $A$ (que en realidad es el caso general). Dado cualquier $n \times p$ matriz $B$ calculamos la descomposición de valor singular $B = USV^T$, configurar una o más de las diagonales, los valores de $S$ a (cerca) $0$ valores y calcular $B^{s_n = 0} = V S V^T$; $B^{s_n = 0}$ será PSD.

En R, que sería algo así como:

n = 1000;
p = 10;
set.seed(1);
B = matrix(rnorm(n * p), ncol=p);
svdB = svd(B);
B0 = svdB$v %*% diag(c(svdB$d[1:p-1], .Machine$double.eps)) %*% t(svdB$v) 

Observe que la aritmética de punto flotante cuestiones se saque de banda por lo que incluso si se establece uno de los elemento de la diagonal $L$ o $S$ a $0.0000000001$ o algo muy pequeño, usted todavía puede terminar con la no EP matriz. Este se refieren a la magnitud de los otros elementos en $L$ o $S$ (y probablemente en el álgebra lineal numérica utilizada (OpenBLAS, MKL, etc).

Answer 2

Para una real simétrica matriz $M=P\,\text{diag}(\lambda_1,\dots,\lambda_n)\, P^T$, la más cercana (en la norma de Frobenius) PSD de la matriz se obtiene mediante umbralización los autovalores a las 0:$$\text{Proj}_{\mathcal{S}_n^+}(M)=P\,\text{diag}\big(\max(\lambda_1,0),\dots,\max(\lambda_n,0)\big)\, P^T.$$ Ver, por ejemplo, aquí. Por lo tanto, se pueden interpretar en la medida de $M$'s distancia de PSD es simplemente la distancia de su espectro de lo positivo orthant.

Así, para crear casi PSD matrices, tomar cualquier ortonormales matriz $P$ y, a continuación, establezca $M=PDP^T$ para $D=\text{diag}(\lambda_1,\dots,\lambda_n)$ e las $\lambda_i$ están cerca de la orilla de dicho orthant. Por ejemplo, en R:

n = 10
P = qr.Q(qr(matrix(rnorm(n * n), nrow=n)))
D = diag(rnorm(n, sd=.1)^2)
M = P %*% D %*% t(P)