Los autovalores de a $AB$ $BA$ donde $A$ $B$ son arbitrarias matrices

Question

Esta pregunta es una generalización de los Autovalores de a $AB$ $BA$ donde $A$ $B$ son matrices rectangulares en las que sí que es una generalización de los Autovalores de a $AB$ $BA$ donde $A$ $B$ son matrices cuadradas.

Deje $A$ $m \times n$ matriz y B y $n \times k$ matriz. Obviamente, la matriz producto $AB$ es posible, mientras que el producto $BA$ no lo es. Suponga $n<k<m$, de tal manera que $AB$ es una matriz grande.

¿Hay algo que podamos hacer para bien de la matriz $A$ o $B$, de tal manera que el producto $BA$ se convierte en posible y tal que los autovalores de a $BA$ decir algo acerca de los valores propios de la original $AB$?

Estoy pensando en procedimientos tales como:

• Truncar $A$ ($k \times n$)
• Anexar algunos de los valores de a $B$ ($n \times m$)
• La interpolación de los valores en $B$
• Tomar muestras aleatorias
• etc.

Motivación 1 (teórico): La matriz de $AB$ es grande y claramente degenerados. Por lo tanto, no debe ser menor de la matriz que recoge la misma información como $AB$ (es decir, tiene los mismos autovalores). Si $k=m$, $BA$ sería una más pequeños de la matriz, como se discutió en la Autovalores de a $AB$ $BA$ donde $A$ $B$ son matrices rectangulares.

Motivación 2 (práctica): La eigendecomposition de una gran matriz es computacionalmente costoso, y puede requerir hardware especial. Si el problema se puede simplificar, por ejemplo, por la descomposición de los más pequeños de $BA$, entonces el análisis se puede realizar de manera más eficiente.

Alternativamente, hay algo que podemos decir acerca de los valores propios de a $AB$ sin realizar el producto, es decir, basado en el análisis de $A$ $B$ por separado.

Answer 1

EDITAR:

1) Sí. Hay algo que se puede hacer. Deje $A$ $m$ $n$ matriz y deje $B$ $n$ $k$ matriz con $n < k < m$. A continuación, $AB$ está definido, pero $BA$ no lo es. Aumentar el $B$ $m-k$ columnas de ceros, de modo que $C = [B \: 0]$$n$$m$. Este es un trivial de extensión del operador $B$ a un mayor subespacio. A continuación, $AC$ $CA$ definidos. La matriz $AC$ $m$ $m$ (grande), mientras que la matriz de $CA$$n$$n$, pero tienen los mismos autovalores distintos de cero.

2) No. En general, hay poco que se puede aprender a partir de los análisis por separado de $A$$B$. Un ejemplo extremo es el caso de nonsingular $A$$B = A^{-1}$. El trabajo involucrado en la producción desde el principio la eigendecomposition de $A$ $B$ es todo para nada, como $AB = I$. Otro ejemplo es el caso donde $A$ $B$ son de bloque diagonal de las matrices con $$A = \begin{bmatrix} A_{11} & 0 \\ 0 & 0 \end{bmatrix}, \quad B = \begin{bmatrix} 0 & 0 \\ 0 & B_{22} \end{bmatrix},$$ de modo que $AB=0$.

---

Original respuesta:

Esta no puede ser la respuesta que usted está buscando, pero a sabiendas de la descomposición SVD de la matriz es con frecuencia útil y muy bien podría resolver su problema subyacente.

En primer lugar, permítanme justificar un ligero cambio en la notación. Por convención, los vectores son vectores columna, a menos que explícitamente identificados como vectores fila y este convenio lleva a matrices rectangulares.

Aquí estamos interesados en un producto de $AB^T$ donde $A \in \mathbb{R}^{m \times n}$ $B \in \mathbb{R}^{k \times n}$ son de alto matrices, es decir,$n \ll m$$n \ll k$. En particular, $m$ $k$ son tan grandes que no tenemos ni el espacio para almacenar el producto de forma explícita ni el tiempo para el cálculo de la SVD del producto, incluso si hay suficiente almacenamiento, podría estar disponible.

A continuación siguen el estándar truco para esta situación.

Podemos calcular el tamaño de la economía QR factorizations de $A$$B$, es decir, $$A = QR, \quad B = VS,$ $ donde$Q \in \mathbb{R}^{m \times n}$$R \in \mathbb{R}^{n \times n}$, e $V \in \mathbb{R}^{k \times n}$$S \in \mathbb{R}^{n \times n}$. Esto es esencialmente de Gram-Schmidt orthogonalization de $A$$B$. Los costos son de $O(mn^2)$ $O(kn^2)$ de las operaciones aritméticas. A continuación, $$AB^T = QRS^T V^T.$$

El pequeño de la matriz $RS^T \in \mathbb{R}^{n \times n}$ requiere $O(n^3)$ operaciones para formar y otro $O(n^3)$ operaciones para obtener su enfermedad vesicular porcina, es decir, $$ RS^T = \bar{Q} \Sigma \bar{V}^T. $$ Volviendo al producto $AB^T$, vemos que de hecho hemos calculado su enfermedad vesicular porcina, como $$ AB^T = Q R S^T V^T = Q \bar{Q} \Sigma \bar{V}^T V^T = (Q \bar{Q}) \Sigma (V \bar{V})^T.$$

Answer 2

La siguiente sugerencia se basa en https://arxiv.org/abs/0909.4061v2 y sus referencias.

La gran matriz $A$ puede ser proyectado a un subespacio de dimensiones iguales a las de $B$, sin perder mucha/alguna de su acción.

Pasos:

• Generar un random $n \times k$ matriz $\Omega$ a partir de una distribución Gaussiana con $\mu = 0$ $\sigma = 1$
• Formulario de la $m \times k$ matriz $Y = AΩ$
• La construcción de un $m \times k$ matriz $Q$ cuyas columnas forman una ortonormales base para el rango de $Y$, por ejemplo, el uso de los QR de la factorización de la $Y = QR$
• Formulario de la $n \times k$ matriz $\tilde{A} = Q^{∗}A$

Ahora, el producto $B\tilde{A}$ es posible. Los autovalores para este producto están muy cerca de los valores propios del producto $AB$.

La diferencia entre el real $A$ y su aproximación a $\tilde{A}$ está dado por $||A-QQ^{∗}A||$.

No tengo pruebas de ello, y no estoy seguro de que esto funcionará en todos los casos, pero algunas pruebas rápidas parecen sugerir que funciona.