Cómo encontrar la más cercana positiva definida la matriz de la no-simétrica matriz

Question

Tengo una matriz de Un dado y quiero encontrar una matriz B que es la más cercana a Una en la norma de frobenius y es positiv definitiva. B no tiene que ser simétrico.

He encontrado un montón de soluciones si la entrada de la matriz a es simétrica. Son para un no-simétrica la matriz a? Es posible reescribir el problema como una minimización de un problema convexo?

Answer 1

Una real, la plaza matriz $B$ es positiva definida iff $v^TBv> 0$ todos los $v\neq 0$. Pero $$v^TBv = \tfrac{1}{2}(v^TBv+v^TB^Tv) = \tfrac{1}{2}v^T(B+B^T)v.$$ Se deduce entonces que el $B$ es positiva definida iff $B+B^T$ es positiva definida. Por lo tanto, el modelo se convierte en $$\begin{array}{ll} \text{minimize} & \|A-B\|_F \\ \text{subject to} & B+B^T \succ 0 \end{array}$$ Esto sigue siendo un problema de optimización convexa. Por ejemplo, en CVX el modelo es

n = size(A,1);
cvx_begin sdp
    variable B(n,n)
    minimize(norm(A-B,'Fro'))
    subject to
        B+B' >= 0
cvx_end

(Descargo de responsabilidad: yo soy el autor de la CVX. Usted no necesita utilizar para resolver este problema, sin embargo. Cualquier SDP solver puede manejar este problema.)

Tenga en cuenta que la CVX modelo se relaja la condición de exigir $B$ a ser positivo semidefinite. Que será necesario con cualquier solucionador numérico que se puedan emplear aquí. Por supuesto, un interior método de punto llevaría a una secuencia de estrictamente positiva definida soluciones que convergen a un nivel óptimo, pero este óptimo, puede ser positivo semidefinite.

Answer 2

Creo que esta es una forma directa para calcular la más cercana psd de la matriz sin el uso de optimización numérica.

1. Encontrar el más cercano simétrica psd de la matriz ( $S$ ) $A$ como sigue (véase la prueba del Teorema 2.1 en Higham 1988 papel):

   (i) Calcular la parte simétrica de $A$: $C=(A+A^T)/2$

   (ii) Calcular la descomposición espectral $C=UDU^T$ donde $D$ es la diagonal

   (iii) Reemplazar las anotaciones negativas en $D$ cero para obtener la matriz diagonal $D_+$

   (iv) Calcular $S=UD_+U^T$

2. Añadir un anti-simétrica matriz $Q$ $S$que lo hace de manera más cercana a $A$:

   (i) de la Pila de hasta un genérico anti-simétrica matriz $Q$ en un vector $\text{vec}(Q)$ y reordenar a la forma $Px$ donde $P$ es una conocida base de la matriz y $x$ es un vector que contiene la parte superior triangular de los elementos de $Q$

   (ii) Calcular $Q$ $\text{vec}(Q)=P(P^TP)^{-1}P'\text{vec}(A-S)$

   (iii) El deseado más cercano psd de la matriz es $B=S+Q$.