¿Una forma rápida de invertir ADA 'cuando D es una matriz diagonal que cambia cada iteración?

Question

Así que tengo una estadística algoritmo de aprendizaje en la que D es una matriz diagonal que cambia cada iteración mientras permanece la misma. Estoy buscando una forma rápida de invertir ADA' en cada iteración, lo que termina siendo un .9 millones por .9 millones tamaño de la matriz.

A es de orden m por n con m < n.

Mis pensamientos han sido atraídos a hacer un económico SVD de a para obtener A=SVU' (V y termina siendo un cuadrado de la diagonal de la matriz) en el que yo sólo necesita preocuparse de invertir el interior de U'DU plazo y U'*U=yo, me siento como debe de ser algo posible pero no puedo averiguar.

Alguna idea?

algunas notas adicionales: es bastante escasa, el preprocesamiento de las cosas, como el SVD de a puede tomar el tiempo necesario...etc

Código de MATLAB que he probado para mostrar que el enfoque sugerido no funciona (seguro de cómo dar formato a esta):

rows=90; cols=120; G=rand(rows,cols); [X,Y,Z]=svd(G,'econ'); A=Z'; %the above was just to generate A s.t. A'A=I, as in second paragraph above d=rand(1,cols); D=diag(d); M=A*D*A'; Minv=M^(-1) %something to compare with %[U,E,V]=svd(A); %also tried this, it didn't work either [U,E,V]=svd(A,'econ'); Einv=E'; Einv(1:rows,1:rows)=diag(1./diag(E)); %calculate inverse of E Ap=V*Einv*U'; Minv2=Ap'*D^(-1)*Ap; max(max((Minv-Minv2).^2)) %did it work? (no)

Answer 1

Cómo acerca de: $$(ADA')^{-1} = {A^+}' D^{-1} A^+$$ donde $A^+$ es el de Moore-Penrose pseudoinverse?

Tenga en cuenta que si $A=U\Sigma V'$ más económica es el SVD, a continuación, $A^+=V\Sigma^{-1}U'$.

Btw, estoy asumiendo que tu matrices son reales, que $A$ es de rango $m$, e $D$ de la fila $n$.

---

Editar: Resulta que esto no funciona. No tengo una solución de trabajo (sin embargo), sólo las siguientes observaciones.

Deje $\boxed{\quad A\phantom'\quad}=\boxed{U\phantom'}\,\boxed{\Sigma\phantom'}\,\boxed{\quad V'\quad}$ ser el económico, SVD.

Entonces podemos escribir la totalidad de enfermedad vesicular porcina como $\boxed{\quad A\phantom'\quad}=\boxed{U\phantom'}\,\boxed{\Sigma\phantom'\quad 0\phantom'}\begin{array}{|cc|}\hline V'\\ \hline \quad\! N'\!\!\quad\\\hline\end{array}$.

Por otra parte, las columnas de a$U$ formulario de la columna de espacio de $A$. Y las columnas de a$N$ forma el espacio nulo de a$A$.

Por consiguiente, podemos escribir: $$(ADA')^{-1} = (U\Sigma V'DV\Sigma' U')^{-1}=U\Sigma^{-1}(V'DV)^{-1}\Sigma^{-1}U'$$ o: $$(ADA')^{-1} = \left(U(\Sigma\mid0)\binom{V}{N}D(V\mediados N)\binom{\Sigma'}{0} U'\right)^{-1} = U\left((\Sigma\mid0)\binom{V}{N}D(V\mediados N)\binom{\Sigma}{0}\right)^{-1}U'$$ En la segunda forma, podemos decir que: $$\left(\binom{V'}{N'}D(V\mid N)\right)^{-1} = \binom{V'}{N'}D^{-1}(V\mid N) $$ Sin embargo, por desgracia, no podemos dejar de mencionar la $N$ submatrices y tenemos: $$(V'DV)^{-1}\ne V'D^{-1}V $$ Esta es la razón por la que mi sugerencia original no funciona.