Factorizacion de Cholesky de matrices singulares

A.M. Urbano, R. Canto, B. Ricarte

Institut de Matematica Multidisciplinar, Universitat Politecnica de Valencia,E-46022 Valencia

amurbano@mat.upv.es,rcanto@mat.upv.es,bearibe@mat.upv.es,

Resumen

Es conocido que toda matriz simetrica definida positiva admite una unica fac-torizacion de Cholesky, mientras que si la matriz es semidefinida positiva dichafactorizacion no es, por regla general, unica. En este trabajo vamos a demostrarque existe una unica factorizacion de Cholesky de rango completo en formaescalonada para las matrices simetricas semidefinidas positivas. Los resultadosobtenidos pueden extenderse a matrices rectangulares A sin rango completo paraobtener la factorizacion de Cholesky de rango completo de la matriz simetricasemidefinida positiva ATA. Ademas presentamos dos algoritmos que permitenobtener la factorizacion de Cholesky de ATA sin necesidad de hacer el productode ambas matrices.Seccion en el CEDYA 2011: ALAMA

1. Introduccion

Dada una matriz A ∈ Rn×n con rank(A) = r < n, una factorizacion de laforma A = FU , donde F ∈ Rn×r, U ∈ Rr×n y rank(F ) = rank(U) = r recibeel nombre de factorizacion de rango completo de A. Dicha factorizacion no esunica, pero sı que lo es la factorizacion de rango completo en la que la matrizU esta en forma escalona reducida superior unitaria.

Cuando la matriz A es simetrica definida positiva es conocido que existe unaunica factorizacion de Cholesky A = LLT , donde L es triangular inferior condiagonal positiva, pero si A es simetrica semidefinida positiva esta factorizacionno es unica en general. Uno de los objetivos del trabajo es demostrar que existeuna unica factorizacion de Cholesky de rango completo (factorizacion CRC) dela matriz A, de la forma A = LLT , donde L ∈ Rn×r es escalonada inferior y conla entrada principal de cada columna positiva. Dicha factorizacion la obtenemosaplicando a la matriz A el algoritmo de quasi-Gauss sin intercambio de filas [2].

Este resultado puede aplicarse para obtener la factorizacion CRC de la ma-triz semidefinida positiva ATA, donde A es una matriz rectangular sin rangocompleto. Ademas, presentamos dos algoritmos que permiten obtener dicha fac-torizacion sin realizar el producto de matrices ATA.

2. Factorizacion CRC de matrices simetricassemidefinidas positivas

Dada una matriz A ∈ Rn×n simetrica semidefinida positiva y con rank(A) =r < n, en la siguiente proposicion se obtiene la factorizacion CRC de A sinrealizar intercambio de filas aplicando el algoritmo de quasi-Gauss [2]. Para ellosupondremos, sin perdida de generalidad, que A no tiene filas ni, por la simetrıa,columnas nulas. En caso contrario, si las filas de ındices i1, i2, . . . , is fuesennulas premultiplicando y postmultiplicando A por las matrices I{i1,i2,...,is} y(I{i1,i2,...,is}

)T, respectivamente, obtenidas a partir de la matriz identidad de

orden n sin las filas de ındices i1, i2, . . . , is, obtenemos una matriz A sin filas nicolumnas nulas,

A = I{i1,i2,...,is}A(I{i1,i2,...,is}

)T

A partir de la factorizacion CRC de A obtenemos la correspondiente factoriza-cion de la matriz A, es decir

A = LALTA =⇒ A =

((I{i1,i2,...,is}

)T

LA

)(LTAI

{i1,i2,...,is})= LLT

Proposicion 1. Consideremos la matriz A ∈ Rn×n simetrica semidefinida po-sitiva con rank(A) = r y sin filas ni columnas nulas. Existe la factorizacionCRC de A, A = LLT , donde L ∈ Rn×r es escalonada inferior y con la entradaprincipal de cada columna positiva.

Demostracion: Como A es semidefinida positiva y no tiene filas ni columnasnulas, todos los elementos de la diagonal principal son positivos. Supongamosque podemos aplicar el algoritmo de Gauss sin intercambio de filas hasta laiteracion (k − 1)-esima y que el pivote k-esimo es nulo, es decir

Rk−1 = E(k−1)E(k−2) · · ·E(1)A

=

l11 l12 . . . l1k−1 l1k l1k+1 . . . l1nl22 . . . l2k−1 l2k l2k+1 . . . l2n

. . ....

......

...lk−1k−1 lk−1k lk−1k+1 . . . lk−1n

0 lkk+1 . . . lknlkk+1 lk+1k+1 . . . lk+1n

......

...lkn lk+1n . . . lnn

con lii > 0 para i = 1, 2, . . . , k − 1. A partir de la relacion existente entre losmenores de A y de Rk−1 (ver [1]) tenemos que para j = k + 1, k + 2, . . . , n, severifica:

det (A[1, 2, . . . , k, j]) = det (Rk−1[1, 2, . . . , k, j]) = −l2kj

k−1∏i=1

lii ≤ 0,

por lo que lkj = 0 para j = k + 1, k + 2, . . . , n. Es decir la fila k-esima de lamatriz Rk−1 es nula, por lo que podemos quitarla aplicando el algoritmo dequasi-Gauss.

Como consecuencia, siempre que un pivote sea nulo tambien seran nulostodos los elementos de su fila. Al quitar dicha fila mediante el algoritmo de quasi-Gauss obtenemos una nueva matriz Rk−1 a la que podemos seguir aplicandoel algoritmo de Gauss hasta llegar a la matriz en forma escalonada superiory con rango completo de la que obtendremos el factor escalonado superior deCholesky LT . Notar que la entrada principal en cada columna es el pivote queutilizamos en cada iteracion, por lo que es siempre positivo. �

3. Factorizacion CRC de matrices rectangulares

Sea A ∈ Rn×m con rank(A) = r < mın{n,m}, entonces ATA ∈ Rm×m

es simetrica semidefinida positiva. Aplicando la Proposicion 1 obtenemos sufactorizacion CRC, ATA = LLT , sin realizar intercambio de filas.

El problema principal para obtener la factorizacion de Cholesky, general ode rango completo, de ATA consiste en realizar el producto de las matricespuesto que el numero de condicion de ATA es el cuadrado del numero de condi-cion de la matriz A. Por ello, vamos a presentar dos algoritmos que permitenobtener la factorizacion de Cholesky de rango completo sin necesidad de calcularpreviamente el producto correspondiente.

3.1. Matriz con rango completo por columnas

Supongamos en primer lugar que la matriz A ∈ Rn×m tiene rango com-pleto por columnas, esto es, rank(A) = m. Como consecuencia ATA ∈ Rm×m

es simetrica definida positiva y, por tanto, admite una unica factorizacion deCholesky de la forma

ATA = LLT , L ∈ Rm×m triangular inferior invertible.

La obtencion de la matriz L sin hacer el producto ATA pude hacerse teniendoen cuenta el siguiente resultado.

Proposicion 2. Sea A ∈ Rn×m una matriz con rango completo por columnasy L = (lij) su factor triangular inferior de Cholesky. Se verifica

lij =< Aj , Ai > −

∑j−1k=1 ljklik

ljjpara

i = 1, 2, . . . ,mj = 1, 2, . . . , i− 1

l2ii = ∥Ai∥2 −i−1∑t=1

l2it

donde Ai representa la columna i-esima de la matriz A, i = 1, 2, . . . ,m.

Demostracion: Como L es el factor triangular inferior de Cholesky se verificaque ATA = LLT . Supongamos que ei representa el i-esimo vector canonico.Para i = 1, 2, . . . ,m tenemos

eTi ATAei = eTi LL

T ei =⇒ ∥Aei∥2 = ∥LT ei∥2 =⇒ ∥Ai∥2 =

i∑t=1

l2it (1)

De manera analoga para i = 1, 2, . . . ,m y j = 1, 2, . . . , i− 1, obtenemos

∥A(ej + ei)∥2 = ∥LT (ej + ei)∥2 =⇒ ∥Aj +Ai∥2 = ∥LTj + LT

i ∥2

Por tanto

∥Aj +Ai∥2 = (lj1 + li1)2 + (lj2 + li2)

2 + · · ·+ (ljj + lij)2 + l2ij+1 + · · ·+ l2ii

=

j∑t=1

l2jt + 2

j∑k=1

ljklik +

i∑t=1

l2it = ∥Aj∥2 + 2

j∑k=1

ljklik + ∥Ai∥2

De donde, para j = 1, 2, . . . , i− 1, obtenemos

lij =∥Aj +Ai∥2 − ∥Aj∥2 − 2

∑j−1k=1 ljklik − ∥Ai∥2

2ljj=

< Aj , Ai > −∑j−1

k=1 ljklikljj

Finalmente, y a partir de la ecuacion (1) tenemos

l2ii = ∥Ai∥2 −i−1∑t=1

l2it �

Sea A ∈ Rn×m con rango completo por columnas. A partir de la Proposicion 2obtenemos los dos algoritmos siguientes que calculan el factor triangular inferiorde Cholesky L ∈ Rm×m tal que ATA = LLT .

ALGORITMO 1 (Calculo de la matriz L por filas)

l11 = ∥A1∥

For i = 2, 3, . . . ,m

For j = 1, 2, . . . , i− 1

lij =< Ai, Aj > −

∑j−1k=1 ljklik

ljj

end

l2ii = ∥Ai∥2 −∑i−1

t=1 l2it

end

Donde el sumatorio para j = 1 es nulo, es decir∑0

k=1 ljklik = 0.

ALGORITMO 2 (Calculo de la matriz L por columnas)

l11 = ∥A1∥

For i = 1, 2, 3, . . . ,m− 1

For j = i+ 1, i+ 2, . . . ,m

lji =< Aj , Ai > −

∑i−1t=1 ljtlit

lii

end

l2i+1i+1 = ∥Ai+1∥2 −∑i

k=1 l2i+1k

end

Tambien en este caso el sumatorio es nulo para i = 1. La ventaja del Algoritmo2 respecto del Algoritmo 1 es que el calculo de los elementos lji puede hacersemediante computacion en paralelo.

Ejemplo 1. Calcular el factor triangular inferior de Cholesky de la matriz ATAsin hacer el producto, siendo A la matriz

A =

0 2 12 1 10 −1 12 −2 10 0 1

.

Aplicando el algoritmo por filas tenemos

l11 = ∥A1∥ =√8 = 2

√2

l21 =< A1, A2 >

l11=

−2√8= −

√2

2

l22 =√

∥A2∥2 − l221 =

√19

2

l31 =< A1, A3 >

l11=

4√8=

√2

l32 =< A2, A3 > −l21l31

l22=

√2

19

l33 =√

∥A3∥2 − l231 − l232 =

√55

19

Por tanto el factor triangular inferior de Cholesky de ATA es

L =

2√2 0 0

−√2/2

√19/2 0√

2√

2/19√

55/19

.

3.2. Matriz sin rango completo

Supongamos ahora que la matriz A ∈ Rn×m no tiene rango completo porcolumnas, esto es, rank(A) = r < mın{n,m}. Se calcula en primer lugar la fac-torizacion de rango completo de A de la forma A = FU , donde F ∈ Rn×r, U ∈Rr×m en forma escalonada reducida superior unitaria y rango(F ) = rango(U) =r. Como la matriz F tiene rango completo por columnas, FTF es simetricadefinida positiva. Aplicando la Proposicion 2, su factor inferior de Cholesky LF

puede calcularse sin necesidad de realizar el producto FTF . A partir de aquı esinmediato comprobar que el factor escalonado inferior de Cholesky de la matrizATA se obtiene de la forma

L = UTLF

Ejemplo 2. Calcular el factor escalonado inferior de Cholesky de ATA sinhacer el producto, siendo A la matriz

A =

0 2 2 12 1 2 10 −1 −1 12 −2 −1 10 0 0 1

.

La factorizacion de rango completo A = FU , donde U esta en forma escalonadareducida superior unitaria es,

A =

0 2 12 1 10 −1 12 −2 10 0 1

︸ ︷︷ ︸

F

1 0 1/2 00 1 1 00 0 0 1

.

︸ ︷︷ ︸U

Notar que la matriz F es la matriz del ejemplo 1, por tanto el factor escalonadoinferior de Cholesky de ATA es

L = UTLF =

2√2 0 0

−√2/2

√19/2 0√

2/2√19/2 0√

2√2/19

√55/19

.

El metodo anterior presenta el inconveniente de tener que hacer en primerlugar la factorizacion de rango completo de la matriz A para obtener las colum-nas linealmente independientes. Podemos evitarnos este paso teniendo en cuentael siguiente comentario:

Comentario: Supongamos que r1 es la primera columna de la matrizA ∈ Rn×m

linealmente dependiente de las r1 − 1 columnas anteriores. En este caso, la

columna r1 de la matriz ATA sera tambien linealmente dependiente de las r1−1columnas anteriores y como consecuencia la fila r1 sera dependiente de las r1−1filas anteriores. Por tanto, si aplicamos el algoritmo de Gauss a la matriz ATA,la fila r1 que se obtiene es nula.

Ası pues, al aplicar alguno de los algoritmos anteriores a la matriz A inicialobtendremos que lr1r1 = 0, lo que implica que ljr1 = 0 para j = r1 + 1, . . . ,m.Como consecuencia dicha columna no formara parte de la matriz escalonadainferior L que estamos calculando. El proceso continua con el calculo de loselementos de las filas o columnas siguientes teniendo en cuenta que ljr1 = 0para j = r1 + 1, . . . ,m.

Ejemplo 3. Consideremos la matriz A del ejemplo anterior

A =

0 2 2 12 1 2 10 −1 −1 12 −2 −1 10 0 0 1

.

Aplicando el algoritmo por filas:

l11 = ∥A1∥ =√8 = 2

√2

l21 =< A1, A2 >

l11=

−2√8= −

√2

2

l22 =√

∥A2∥2 − l221 =

√19

2

l31 =< A1, A3 >

l11=

2√8=

√2

2

l32 =< A2, A3 > −l21l31

l22=

√19

2

l33 =√

∥A3∥2 − l231 − l232 = 0.

Notar que l33 = 0 implica que la tercera columna de la matriz ATA es com-binacion lineal de las dos primeras. Como consecuencia dicha columna puedeser quitada al calcular el factor triangular inferior de Cholesky para que la fac-torizacion sea de rango completo. Ahora seguimos calculando los elementos que

faltan, teniendo en cuenta que lj3 = 0, con j > 3,

l41 =< A1, A4 >

l11=

4√8=

√2

l42 =< A2, A4 > −l21l41

l22=

√2

19l43 = 0

l44 =√∥A4∥2 − l241 − l242 − l243 =

√55

19

luego

L =

2√2 0 0

−√2/2

√19/2 0√

2/2√

19/2 0√2

√2/19

√55/19

.

Agradecimientos

Trabajo financiado por el proyecto de la DGI MTM2010-18228 y el Progra-ma de Apoyo a la Investigacion y Desarrollo (PAID-06-10) de la UniversitatPolitecnica de Valencia.

Bibliografıa

[1] T. Ando, Totally positive matrices, Linear Algebra Appl. vol. 90 (1987), 165-219.

[2] R. Canto, B. Ricarte, A. M. Urbano, Full rank factorization and Flanders Theorem,Electronic Journal of Linear Algebra, vol. 18 (2009), 352-363.