Hay un procedimiento iterativo que empuja a los valores singulares de una matriz hacia la unidad?

Question

Considere la posibilidad de una matriz cuadrada $A = U \Sigma V^T$. Quiero encontrar a $B = UV^T$ - sin embargo, parece un despilfarro calcular el conjunto de la SVD, sólo para volver a multiplicar las dos matrices ortogonales.

¿Existe algún estable procedimiento que puede utilizar para "empujar" a las entradas en la diagonal de la matriz $\Sigma$ a?

Answer 1

Set$A_0=A$$A_n = (1/2)(A_{n-1}+(A_{n-1}^T)^{-1})$. Puedo reclamar $A_n \to UV$, y lo hace rápidamente.

Definir $f(x) = \frac{x+x^{-1}}{2}$. Supongamos $A=UDV$ donde la diagonal entradas de $D$ $\sigma_1$, $\sigma_2$, ..., $\sigma_k>0$. Luego de la inducción muestra que $A_n = U D_n V$ donde $D$ es diagonal con entradas de $f^{(n)}(\sigma_j)$. (Aquí se $f^{(n)}$ significa recorrer $f$ $n$ a veces). Para cualquier $\sigma>0$, $f^{(n)}(\sigma) \to 1$, y lo hace con bastante rapidez: $|f^{(n)}(\sigma)-1|$ encoge como $1/\exp(c \cdot 2^n)$.

Descargo de responsabilidad: yo no he probado este método.

Answer 2

David , 1. Tenga en cuenta que $x\rightarrow (x+1/x)/2$ es la iteración de Newton para el cálculo de una aproximación de $\sqrt{1}$. Si $\sigma =1000\approx 2^{10}$, uno necesita más que $10$ iteraciones.

2. ¿Cuál es el interés ? Cada matricial iteración tiene la complejidad de la $\sim n^3$; comparar con el coste del cálculo de la SVD (en $O(n^3)$) y la multiplicación $UV^T$ ($\sim n^3$).

3. El OP se supone (si me entienden correctamente su pregunta) que los valores propios son desconocidos. ¿Cómo se escribe su iteración ? De todos modos, el cálculo de los valores propios es también en $O(n^3)$.

4. La pareja $U,V$ no es única, pero creo que el $UV^T$ es único.