Aproximaciones de rango bajo de una matriz basadas en la descomposición en valores singulares
Abstract
Departamento de Matemática Aplicada
Full text
FACULTAD DE CIENCIAS
TRABAJO FIN DE GRADO
G ado en Ma emá icas
Ap oximaciones de ango bajo de una ma iz basadas en la descomposición
en alo es singula es.
Au o : Pablo González Cas año
Tu o a: Ma ía Paz Cal o Cab e o
Año 2022
´
Indice gene al
In oducci´on 3
1. La descomposici´on en alo es singula es 5
1.1. Teo ema de exis encia ................................ 5
1.2. Teo ema de Ecka -Young .............................. 7
1.3. Dos esul ados adicionales sob e la SVD ...................... 12
2. SVD alea o izada 15
2.1. Ap oximaci´on alea o izada del p oduc o de ma ices ................ 15
2.2. Un algo i mo alea o izado pa a la SVD ....................... 22
3. Aplicaciones 29
3.1. Inco po aci´on de una ma ca de agua a una imagen ................ 29
3.1.1. El p oblema de la p opiedad leg´ı ima .................... 29
3.1.2. Esquemas de ma ca de agua basados en la SVD .............. 30
3.1.3. Una ilus aci´on num´e ica ........................... 33
3.2. LSI: An´alisis sem´an ico la en e ............................ 38
3.2.1. In oducci´on. ................................. 38
3.2.2. B´usqueda y ac ualizaci´on ........................... 39
3.2.3. Una ilus aci´on de LSI. ............................ 40
Bibliog a ´ıa 44
A. C´odigo de Ma lab. 47
A.1. P oduc o alea o izado de dos ma ices. ....................... 47
A.2. Descomposici´on en alo es singula es alea o izada. ................. 48
A.3. Esquema de Liu y Tan ................................ 49
A.4. Esquema de Jain ................................... 50
A.5. Implemen aci´on del an´alisis sem´an ico la en e ................... 51
1
2´
INDICE GENERAL
In oducci´on
El T abajo Fin de G ado que p esen amos iene po obje i o ob ene ap oximaciones de ango
bajo a una ma iz dada haciendo uso de su descomposici´on en alo es singula es, o de una
e si´on alea o izada de dicha descomposici´on que equie e un cos e compu acional bas an e
meno .
En el Cap´ı ulo 1, se incluyen los esul ados m´as ele an es sob e la descomposici´on en alo es
singula es de una ma iz: el eo ema que ga an iza su exis encia pa a cualquie ma iz eal, y el
eo ema de Ecka -Young, que p opo ciona a a ´es de dicha descomposici´on la mejo ap oxi-
maci´on a la ma iz de pa ida po ma ices de ango ijado, an o en la no ma espec al, como
en la no ma de F obenius.
En el Cap´ı ulo 2, se in oducen dos algo i mos que pe mi en ob ene ap oximaciones de ango
bajo de una ma iz de o ma m´as e icien e, a cambio de pe de algo de p ecisi´on. En conc e o,
se p esen a un p ime algo i mo pa a e ec ua el p oduc o alea o izado de dos ma ices, que
se u iliza despu´es pa a calcula la descomposici´on en alo es singula es alea o izada de una
ma iz. Adem´as, se p ueban algunos esul ados e´o icos sob e el e o en las ap oximaciones
conside adas y se incluyen expe imen os num´e icos que ilus an dichos esul ados.
En el Cap´ı ulo 3, se p esen an dos aplicaciones p ´ac icas de la descomposici´on en alo es sin-
gula es. La p ime a se e ie e a la inco po aci´on de ma cas de agua a im´agenes, con is as a
p oba la au o ´ıa o p opiedad de las mismas, y se analizan los esquemas basados en la SVD. La
segunda es ´a elacionada con la ex acci´on de in o maci´on, y se cen a en el an´alisis sem´an ico
la en e, una p opues a que busca mejo a los sis emas de b´usqueda basados en palab as indi-
iduales.
Finalmen e, en el Ap´endice A, se incluyen las unciones en Ma lab que implemen an los algo-
i mos in oducidos en los Cap´ı ulos 2y3, y que han se ido como base pa a c ea las igu as
que apa ecen en esos mismos cap´ı ulos.
3
4´
INDICE GENERAL
Cap´ı ulo 1
La descomposici´on en alo es
singula es
Comenzamos es e p ime cap´ı ulo enunciando y demos ando el eo ema que ga an iza la exis-
encia de la descomposici´on en alo es singula es de cualquie ma iz eal.
1.1. Teo ema de exis encia
Teo ema 1.1.1. Sea A∈Rm×nuna ma iz de ango . Exis en ma ices o ogonales U∈Rm×m
yV∈Rn×n ales que A=UΣVT, donde Σ∈Rm×n iene elemen os σij,1≤i≤m, 1≤j≤n,
dados po
σij = 0 pa a i=j,
σii = 0 pa a i≤ ,
σii = 0 pa a i > .
Demos aci´on. Vamos a oma la ma iz ATA, que es sim´e ica y, po an o, es diagonalizable
o ogonalmen e, es deci , exis e V∈Rn×no ogonal de o ma que
VT(ATA)V=D,
donde Des diagonal, con elemen os diagonales λ1≥λ2≥ ··· ≥ λ > λ +1 =··· =λn= 0,
que son los au o alo es de ATA. Adem´as, si V= [ 1, 2, ..., n], donde ideno a la columna
i-´esima de V, se e i ica que ies un au o ec o asociado a λi.
Aho a buscamos la ma iz U. Pa a ello comp obamos en p ime luga que las im´agenes po A
de las columnas de Vson o ogonales dos a dos
(A i)T(A j) = T
iATA j= T
iλj j=λj T
i j= 0 si i=j, (1.1)
5
6CAP´
ITULO 1. LA DESCOMPOSICI ´
ON EN VALORES SINGULARES
pues o que la ma iz Ves o ogonal. Tenemos po an o un conjun o de n ec o es o ogonales
de Rmy adem´as como el ango de Aes ,λi=0pa a i> y, po an o, A i= 0 si i> .
Vemos que an o las columnas de Vcomo sus im´agenes po Anos dan una exp esi´on diagonal
de A
(AV )TAV =VTATAV =D.
No malicemos aho a los ec o es {A i}n
i=1.
Si en (1.1) hacemos j=i, se comp ueba que
∥A i∥2
2=λi>0,si i≤ .
De es e modo, λi≥0 y como hemos elegido Vpa a que
λi≥λjsi i < j,
enemos que
λ1≥λ2≥ ··· ≥ λ >0,
con λi= 0 si i> .
Tiene sen ido en onces oma pa a 1 ≤i≤
ui=A i
∥A i∥2
=1
√λi
A i,
de o ma que
A i=pλiui,1≤i≤ .
Si aho a omamos σi=√λi, 1 ≤i≤ , se iene que
A i=σiui,1≤i≤ ,
que es exac amen e lo que busc´abamos.
En el caso de que < m, bas a con amplia el sis ema o ono mal {u1,u2, ..., u }has a una
base o ono mal de Rm.
Pa a conclui , omamos como ma iz Ula que iene po columnas los ec o es ui, 1 ≤i≤m,
con lo que enemos
AV =UΣ,
donde Σ es la ma iz de ama˜no m×ncon odos los elemen os nulos, excep o los p ime os
elemen os diagonales que son iguales a σ1, . . . , σ , las a´ıces cuad adas de los au o alo es no
nulos de ATAo denados en o den dec ecien e. Usando aho a la o ogonalidad de Vse llega a
la exp esi´on buscada.
A=UΣVT.(1.2)
1.2. TEOREMA DE ECKART-YOUNG 7
Obse aci´on 1.1.1. Llama emos a las columnas de U,{ui}m
i=1, y a las columnas de V,{ i}n
i=1,
los ec o es singula es de A po la izquie da y po la de echa, espec i amen e. Denomina emos
alo es singula es de Aa los elemen os diagonales no nulos de la ma iz Σ, o denados en o den
dec ecien e, y los deno a emos po {σi}
i=1 o po {σi(A)}
i=1 en caso de que es emos hablando
de a ias ma ices y pueda exis i con usi´on. No emos adem´as que, dada la es uc u a de ce os
de la ma iz Σ, la igualdad (1.2)se puede esc ibi de mane a m´as compac a como
A=
X
i=1
σiui T
i,(1.3)
es deci , A es ´a esc i a como la suma de ma ices de ango 1.
Obse aci´on 1.1.2. Bas´andonos en la demos aci´on del Teo ema 1.1.1, enemos que los p i-
me os ec o es singula es po la izquie da {ui}
i=1 son una base del subespacio gene ado po
las columnas de A. Del mismo modo, los p ime os ec o es singula es po la de echa { i}
i=1
son una base del subespacio gene ado po las ilas de A(el gene ado po las columnas de AT).
Es deci , los ec o es singula es e ienen g an pa e de la in o maci´on de la ma iz o iginal.
1.2. Teo ema de Ecka -Young
Una ez p obado que exis e la descomposici´on en alo es singula es de cualquie ma iz eal A,
amos a e que a pa i de dicha descomposici´on podemos cons ui la mejo ap oximaci´on de
ango ka dicha ma iz. Pe o an es, amos a eco da la de inici´on de dos no mas ma iciales
que amos a usa , y a in oduci un lema auxilia .
De inici´on 1.2.1. Sea A∈Rm×nuna ma iz con elemen os aij,1≤i≤m, 1≤j≤n. Se
de ine la no ma de F obenius de A, que deno a emos po ∥A∥F, como
∥A∥F=
u
u
m
X
i=1
n
X
j=1 |aij|2.(1.4)
De inici´on 1.2.2. Sea Auna ma iz como en la De inici´on 1.2.1. Se de ine la no ma espec al
de A(o la no ma inducida po la no ma eucl´ıdea), que deno a emos po ∥A∥2, como
∥A∥2= sup
x=0
∥Ax∥2
∥x∥2
= m´ax
∥x∥2=1 ∥Ax∥2.(1.5)
donde ∥·∥2deno a la no ma eucl´ıdea an o en Rncomo en Rm.
Lema 1.2.1. Sea A∈Rm×nuna ma iz de ango , y sea A=UΣVTsu descomposici´on en
alo es singula es. En onces
14 CAP´
ITULO 1. LA DESCOMPOSICI ´
ON EN VALORES SINGULARES
Podemos conclui en onces que
|σi(A+δA)−σi(A)| ≤ σ1(δA) = ∥δA∥2pa a i= 1, ..., m´ın{m, n}.
El siguien e esul ado p opo ciona una ca ac e izaci´on a iacional de los alo es singula es.
Teo ema 1.3.2. Sea A∈Rm×nyσksu k-´esimo alo singula . En onces
σk= m´ax
u∈<u1,...,uk−1>⊥
∈< 1,..., k−1>⊥
uTA
∥u∥2∥ ∥2
, k > 1,(1.12)
donde <u1,...,uk−1>y< 1,..., k−1>son los subespacios gene ados po los k−1 p ime os
ec o es singula es de Apo la izquie da y po la de echa, {u1,...,uk−1}y{ 1,..., k−1},
espec i amen e.
Demos aci´on. Hemos is o en (1.3) que podemos esc ibi
A=
X
i=1
σiui T
i.
Po an o, si omamos u∈<u1,...,uk−1>⊥y ∈< 1,..., k−1>⊥, se iene que
uTA =
X
i=1 σiuTui T
i =uT
X
i=k
σiui T
i! =uT(A−Ak−1) ,(1.13)
donde se ha u ilizado (1.3) y (1.6). Si aho a empleamos la desigualdad de Cauchy-Schwa z, nos
queda
|uTA |≤∥uT∥2∥A−Ak−1∥2∥ ∥2=σk∥u∥2∥ ∥2,
es deci ,
σk≥|uTA |
∥u∥2∥ ∥2
,u∈<u1,...,uk−1>⊥, ∈< 1,..., k−1>⊥.
Adem´as, si en (1.13) omamos u=uk, = kel k-´esimo ec o singula de Apo la izquie da
y po la de echa, espec i amen e, enemos
uT
kA k=
X
i=1 σiuT
kui T
i k=σkuT
kuk T
k k=σk,
lo cual concluye la demos aci´on.
Cap´ı ulo 2
La descomposici´on en alo es
singula es alea o izada
An es de nada, amos a in oduci una no aci´on que usa emos a lo la go de es e cap´ı ulo.
Sea A∈Rm×nuna ma iz, Deno a emos
1. Las columnas de Apo aipa a 1 ≤i≤n.
2. Las ilas de Apo aipa a 1 ≤i≤m.
3. Los elemen os de Apo aij pa a 1 ≤i≤m, 1 ≤j≤n.
4. Dada una ma iz B∈Rn×p, los elemen os de la ma iz p oduc o AB los deno a emos po
(AB)ij pa a 1 ≤i≤m, 1 ≤j≤p.
Adem´as, como en es a secci´on ambi´en amos a u iliza a iables alea o ias, deno a emos como
es habi ual en la li e a u a su espe anza po E[X] y la a ianza po Va [X], donde Xes dicha
a iable alea o ia.
2.1. Ap oximaci´on alea o izada del p oduc o de ma i-
ces
Vamos a conside a un algo i mo sencillo pa a ap oxima el p oduc o de dos ma ices de o ma
alea o izada. Mul iplica ma ices es un p oblema undamen al den o del ´
Algeb a Lineal, po
lo que el algo i mo iene in e ´es en s´ı mismo. Pe o adem´as, es o es algo que se usa en muchos
o os algo i mos, luego ambi´en a a se ´u il como una he amien a auxilia en o os p oblemas.
El p oblema es el siguien e: dadas ma ices A∈Rm×nyB∈Rn×p, que emos ob ene la ma iz
15
16 CAP´
ITULO 2. SVD ALEATORIZADA
p oduc o AB. Sabemos que el p oduc o usual de ma ices equie e m×n×pp oduc os y o as
an as sumas, que se aduce en un iempo de c´alculo O(m×n×p). La p egun a es, ¿podemos
hace lo m´as ´apido, aunque hallemos el p oduc o solo de mane a ap oximada?.
Pa a ello, amos a in e p e a el p oduc o de dos ma ices como una suma de ma ices de ango
uno, es o es
AB =
n
X
i=1
aibi,(2.1)
El algo i mo que amos a in oduci oma una mues a alea o ia de las columnas y las ilas de las
ma ices AyB, espec i amen e, y hace el p oduc o con las ma ices esul an es. An´alogamen e,
cuando es amos a ando una suma de n´ume os, podemos oma una mues a alea o ia de es os
siguiendo cualquie dis ibuci´on y amos a ob ene un es imado insesgado de dicha suma. Sin
emba go, si que emos minimiza la a ianza del es imado , amos a necesi a elegi la mues a
(y eescala ) en unci´on del ama˜no de los n´ume os. Pa a el p oduc o de ma ices a a se igual.
Comenza emos desc ibiendo el algo i mo que nos a a pe mi i ap oxima el p oduc o de dos
ma ices.
Algo i mo 1. Mul iplicaci´on Alea o izada de Ma ices.
Dadas ma ices A∈Rm×nyB∈Rn×p, un en e o posi i o c<ny p obabilidades {pi}n
i=1,
hacemos
Pa a desde 1 has a c
1.Elegimos i ∈ {1, . . . , n}con p obabilidad P[i =k] = pken expe imen os
independien es e id´en icamen e dis ibuidos con eemplazamien o.
2.Hacemos c =ai
√cpi
y =bi
√cpi
.
De ol emos Cla ma iz de ama˜no m×cque iene po columnas c ,1≤ ≤cy
Rla ma iz de ama˜no c×pque iene po ilas ,1≤ ≤c. (2.2)
La ma iz CR es una ap oximaci´on de la ma iz AB. Podemos in oduci aho a los siguien es
esul ados.
Lema 2.1.1. Sean A∈Rm×nyB∈Rn×pdos ma ices, CyRcomo en el Algo i mo 1.
En onces
Eh(CR)iji= (AB)ij yVa h(CR)ij i=1
c
n
X
k=1
a2
ikb2
kj
pk−1
c(AB)2
ij .(2.3)
Demos aci´on. Fijamos i,j, y pa a = 1, . . . , c de inimos las a iables alea o ias
X =c ij =ai bi
cpi ij
=aii bi j
cpi
.
2.1. APROXIMACI ´
ON ALEATORIZADA DEL PRODUCTO DE MATRICES 17
En onces,
E[X ] =
n
X
k=1
pkXk=
n
X
k=1
pk
aikbkj
cpk
=1
c
n
X
k=1
aikbkj =1
caibj=1
c(AB)ij .
Adem´as,
EX2
=
n
X
k=1
pkX2
k=
n
X
k=1
a2
ikb2
kj
c2pk
.
Po o o lado, po de inici´on, enemos
(CR)ij =
c
X
=1
X ,
luego
Eh(CR)iji=
c
X
=1
E(X ) =
c
X
=1
1
c(AB)ij = (AB)ij .
Po o o lado, como (CR)ij es la suma de c a iables alea o ias independien es,
Va h(CR)iji=
c
X
=1
Va (X ) =
c
X
=1 EX2
−E[X ]2
=
c
X
=1 n
X
k=1
a2
ikb2
kj
c2pk−(AB)ij
c2!
=c
n
X
k=1
a2
ikb2
kj
c2pk−(AB)2
ij
c2
=1
c
n
X
k=1
a2
ikb2
kj
pk−(AB)2
ij
c.
Es amos aho a en condiciones de da una co a supe io pa a E[∥AB −CR∥2
F] y e que el e o
a a depende de las p obabilidades elegidas.
Lema 2.1.2. Sean A∈Rm×nyB∈Rn×pdos ma ices, c∈Z+,CyRcomo en el Algo i mo
1. En onces
E∥AB −CR∥2
F=
n
X
k=1
∥ak∥2
2∥bk∥2
2
cpk−1
c∥AB∥2
F.(2.4)
Adem´as, si se eligen
pk=∥ak∥2∥bk∥2
Pn
l=1 ∥al∥2∥bl∥2
,1≤k≤n, (2.5)
en onces
E∥AB −CR∥2
F=1
c n
X
k=1 ∥ak∥2∥bk∥2!2
−1
c∥AB∥2
F.
18 CAP´
ITULO 2. SVD ALEATORIZADA
Demos aci´on. Comencemos no ando que
∥AB −CR∥2
F=
m
X
i=1
p
X
j=1 (AB)ij −(CR)ij
2=
m
X
i=1
p
X
j=1
(AB −CR)2
ij .
Adem´as, usando el lema an e io y que Va h(CR)iji=Eh(CR)2
iji−Eh(CR)iji2, enemos
que
Eh(AB −CR)2
iji=E(AB)ij −(CR)ij2=Eh(AB)2
ij −2 (AB)ij (CR)ij + (CR)2
iji
= (AB)2
ij −2 (AB)ij Eh(CR)iji+Eh(CR)2
iji
= (AB)2
ij −2 (AB)ij (AB)ij +Va h(CR)ij i+Eh(CR)iji2
= (AB)2
ij −2 (AB)2
ij + (AB)2
ij +Va h(CR)iji
=Va h(CR)iji.
Po an o, podemos asegu a que
E∥AB −CR∥2
F=
m
X
i=1
p
X
j=1
Eh(AB −CR)2
iji=
m
X
i=1
p
X
j=1
Va h(CR)iji.
Siguiendo de nue o el Lema 2.1.1, se iene que
E∥AB −CR∥2
F=
m
X
i=1
p
X
j=1 1
c
n
X
k=1
a2
ikb2
kj
pk−1
c(AB)2
ij!
=1
c
n
X
k=1
1
pk m
X
i=1
a2
ik! p
X
j=1
b2
kj!−1
c∥AB∥2
F
=1
c
n
X
k=1
1
pk∥ak∥2
2∥bk∥2
2−1
c∥AB∥2
F.
Si aho a omamos pk, 1 ≤k≤n, como en (2.5), en onces
E∥AB −CR∥2
F=1
c
n
X
k=1
1
∥ak∥2∥bk∥2
Pn
l=1 ∥al∥2∥bl∥2
∥ak∥2
2∥bk∥2
2−1
c∥AB∥2
F
=1
c n
X
k=1 ∥ak∥2∥bk∥2!2
−1
c∥AB∥2
F.
2.1. APROXIMACI ´
ON ALEATORIZADA DEL PRODUCTO DE MATRICES 19
A con inuaci´on enunciamos un esul ado que a i ma que e ec i amen e las p obabilidades o-
madas en (2.5) son las que minimizan la espe anza del e o al ap oxima la ma iz p oduc o
AB.
Teo ema 2.1.1. Las p obabilidades {pi}n
i=1 de la o ma de (2.5)minimizan E[∥AB −CR∥2
F].
Demos aci´on. Empezamos de iniendo la unci´on
(p1, . . . , pn) =
n
X
k=1
1
pk∥ak∥2
2∥bk∥2
2,
que ca ac e iza la dependencia de E[∥AB −CR∥2
F] espec o de las p obabilidades. Pa a mini-
miza suje o a Pn
k=1 pk= 1 in oducimos el mul iplicado de Lag ange λy de inimos
g(p1, . . . , pn) = (p1, . . . , pn) + λ n
X
k=1
pk−1!.
Tenemos que pedi que se cumpla pa a 1 ≤i≤n,
0 = ∂g
∂pi
=−1
p2
i∥ai∥2
2∥bi∥2
2+λ,
po lo que
pi=∥ai∥2∥bi∥2
√λ.
Aho a, imponiendo la condici´on de que
n
X
k=1
pk= 1,
nos queda lo siguien e
1 =
n
X
k=1
∥ak∥2∥bk∥2
√λ,
y podemos conclui que
√λ=
n
X
k=1 ∥ak∥2∥bk∥2.
Adem´as, ∂2g
∂p2
i
>0 pa a odo i= 1, . . . , n, luego podemos asegu a que la unci´on p esen a un
m´ınimo en
pi=∥ai∥2∥bi∥2
Pn
k=1 ∥ak∥2∥bk∥2
,1≤i≤n.
20 CAP´
ITULO 2. SVD ALEATORIZADA
In oducimos a con inuaci´on un esul ado que p opo ciona una co a supe io pa a la espe anza
del e o en unci´on de la no ma de F obenius de las ma ices que se quie en mul iplica y del
ama˜no de la mues a.
Teo ema 2.1.2. Sean A∈Rm×nyB∈Rn×p,c∈Z+ al que 1≤c≤ny{pi}n
i=1 como en
(2.5). Si cons uimos CyRcomo en el Algo i mo 1, en onces
E||AB −CR||2
F≤1
c∥A∥2
F∥B∥2
F.
Demos aci´on. No hay m´as que no a que usando (2.4),
E∥AB −CR∥2
F=1
c n
X
k=1 ∥ak∥2∥bk∥2!2
−1
c∥AB∥2
F≤1
c n
X
k=1 ∥ak∥2∥bk∥2!2
≤1
c∥A∥2
F∥B∥2
F,
donde en la ´ul ima desigualdad hemos usado la desigualdad de Cauchy-Schwa z.
Es e esul ado a i ma algo que pod´ıamos in ui desde un p incipio: cuan o m´as g ande sea
la mues a de columnas de Ay ilas de Bu ilizadas, meno a a se el e o ela i o en la
ap oximaci´on E||AB −CR||2
F
∥A∥2
F∥B∥2
F
.
Aho a amos a ilus a es os esul ados con la ayuda de Ma lab. Pa imos de una imagen
cuad ada de dimensi´on 916×916 de la cual ob enemos la ma iz de alo es num´e icos asociados,
A. De es a ma iz calculamos la ac o izaci´on LU y hacemos el p oduc o ap oximado de LyU
mil eces pa a e c´omo de p ecisa es la media de dichas ap oximaciones.
Figu a 2.1: Imagen o iginal 916×916. Figu a 2.2: Ap oximaci´on hallada con c= 10.
La Figu a 2.1 ep esen a la imagen o iginal, mien as que el es o de igu as son la media de
las ap oximaciones del p oduc o de LyUpa a dis in os alo es de c. En pa icula , la Figu a
2.2 es pa a c= 10, la Figu a 2.3 oma c= 50 y en la Figu a 2.4 c= 100.
2.1. APROXIMACI ´
ON ALEATORIZADA DEL PRODUCTO DE MATRICES 21
Es e iden e que cuando mues eamos solo con 10 columnas la ap oximaci´on no es buena, apenas
somos capaces de e nada de la imagen o iginal. Sin emba go, en cuan o aumen amos a 50 la
imagen ya es bas an e m´as isible, aunque cie os n´ume os pueden da luga a duda. Con el
alo de c= 100 s´ı que se econocen odos los d´ıgi os.
Figu a 2.3: Ap oximaci´on hallada con c= 50 Figu a 2.4: Ap oximaci´on hallada con c= 100.
Si seguimos aumen ando el alo de c, es e iden e que las ap oximaciones segui ´an mejo ando,
pe o ya hemos is o que c= 100 es su icien emen e buena en es e caso.
Todo es o se e e lejado en la Figu a 2.5, que mues a el e o ela i o come ido E||AB −CR||2
F
∥A∥2
F∥B∥2
F
en e al n´ume o de columnas cque hemos mues eado.
Figu a 2.5: Relaci´on en e el ama˜no de la mues a y el e o come ido
Obse amos que al mul iplica po 2 el ama˜no de la mues a, el e o come ido se di ide
22 CAP´
ITULO 2. SVD ALEATORIZADA
ap oximadamen e en e 2. Sin emba go, con una mues a de ama˜no c= 100 (que en es e caso
equi ale a poco m´as que la d´ecima pa e del ama˜no de la ma iz), podemos consegui p ecisi´on
del o den de 10−2, y hemos is o que es su icien e como pa a se capaz de dis ingui los d´ıgi os
que apa ecen en la imagen. Po o o lado, es e iden e que siguiendo es e algo i mo, el p oduc o
ap oximado equie e solo un n´ume o de ope aciones del o den de O(m×c×p), y gene almen e
amos a usa c≪n, lo cual es una mejo a sus ancial.
En [3] se pueden encon a m´as de alles ace ca de la mul iplicaci´on alea o izada de ma ices
(ya hemos mencionado que es un p oblema que en s´ı mismo iene mucho in e ´es). Nues o
obje i o p incipal es, sin emba go, u iliza la mul iplicaci´on alea o izada de ma ices pa a da
un algo i mo alea o izado pa a la descomposici´on en alo es singula es de una ma iz.
2.2. Un algo i mo alea o izado pa a la SVD
Un an´alisis del iempo de c´alculo de la SVD de una ma iz A∈Rm×nnos lle a a que dicho
iempo a a se del o den de O(m´ın{mn2, m2n}) [9]. De nue o nos cen amos en e si so-
mos capaces de ap oxima la SVD de una ma iz de un modo m´as ´apido sin pe de mucha
in o maci´on en el p oceso.
Dada una ma iz A∈Rm×n, que emos elegi cie as columnas de Ade o ma que la p oyecci´on
de la ma iz sob e el espacio gene ado po dichas columnas cap e la m´axima in o maci´on posible.
En pa icula , si podemos hace una buena ap oximaci´on de ango kde A, nos gus a ´ıa que
A∼PSA, donde Ses el espacio gene ado po las ccolumnas que hemos elegido de AyPSes
una p oyecci´on de Aen dichas columnas. Pa a ello, amos a segui un algo i mo que se asemeja
al p esen ado en la secci´on an e io .
Algo i mo 2. La SVD alea o izada.
Dada A∈Rm×n,c,k ales que 1 ≤k≤c≤n,{pi}n
i=1 un conjun o de p obabilidades,
Pa a desde 1 has a c
1.Elegimos i ∈ {1, . . . , n}con p obabilidad P[i =j] = pj.
2.Hacemos c =ai
√cpi
.
3.Calculamos CTCy su SVD, ´ease, CTC=
c
X
=1
σ2
(C)y yT
.
4.Calculamos h =Cy
σ (C),pa a = 1, . . . , k.
5.De ol emos la ma iz Hk= [h1, . . . hk] y σ (C) pa a = 1, . . . , k. (2.6)
2.2. UN ALGORITMO ALEATORIZADO PARA LA SVD 23
En esencia, es amos ob eniendo los kp ime os alo es singula es de Cy sus espec i os k
ec o es singula es po la izquie da, h1,...,hk.
Que emos pode a i ma que de alguna o ma Ces simila a A. Puede pa ece complicado
pues o que no son ma ices con las mismas dimensiones, pe o los subespacios gene ados po sus
columnas i en ambos en Rm, as´ı que di emos que son simila es si sus ec o es singula es po
la izquie da gene an subespacios pa ecidos, o lo que es lo mismo, AAT∼CCT.
An es de en a en los esul ados ace ca de la calidad de la ap oximaci´on, eamos que e ec i a-
men e el iempo de c´alculo a a se lineal.
1. Si abajamos con p obabilidades p opo cionales a la no ma eucl´ıdea de las columnas
de A(como hac´ıamos en el Algo i mo 1), enemos que hace una lec u a de la ma iz.
Adem´as, es necesa io elegi y gua da los ´ındices de las columnas, lo cual supone iempo
de c´alculo y espacio adicional del o den de O(c).
2. Una ez elegidos los ´ındices, es necesa ia o a lec u a y a mayo es se eligen las columnas
y se cons uye la ma iz C, que co esponde a un iempo de c´alculo y espacio adicional
del o den de O(m×c).
3. Dada la ma iz C, el c´alculo de CTC equie e O(m×c2) iempo de compu aci´on y espacio
adicional. Aho a, pa a el c´alculo de su SVD es necesa io un iempo de compu aci´on y
espacio adicional del o den de O(c3).
4. Dada la SVD de CTC, pa a calcula Hkson necesa ias kmul iplicaciones de ma iz po
ec o , es o es, O(m×c×k) iempo y espacio adicional.
5. En esumen, podemos conside a c, k =O(1), de modo que solo necesi amos espacio y
iempo de c´alculo del o den de O(m). Es deci , el iempo de c´alculo de es e algo i mo es
lineal en la dimensi´on de la ma iz.
Damos aho a un esul ado sob e la calidad de la ap oximaci´on en la no ma de F obenius.
Teo ema 2.2.1. Sea A∈Rm×ny sea Hkla ma iz ob enida as aplica el Algo i mo 2.
En onces
∥A−HkHT
kA∥2
F≤ ∥A−Ak∥2
F+ 2√k∥AAT−CCT∥F,(2.7)
donde Akes la ma iz de inida en el Teo ema 1.2.1.
Demos aci´on. An es de nada, eco demos que pa a ma ices X, Y ∈Rm×n,∥X∥2
F= (XTX),
(X+Y) = (X) + (Y) y que, po c´omo la hemos cons uido, HT
kHk=Ik, con Ikla ma iz
30 CAP´
ITULO 3. APLICACIONES
el documen o que esul a as es e p oceso.
El p incipal obje i o de las ma cas de agua es p o ege los de echos de au o . Sin emba go,
muchos de los dise˜nos exis en es pe mi en manipula de o ma sencilla la imagen con ma ca de
agua y eclama la como p opia. Algunos p ocedimien os necesi an la imagen o iginal pa a pode
e i ica la p opiedad, pe o incluso en es as condiciones a eces siguen su giendo p oblemas. Es e
ipo de dise˜nos que pe mi en la c eaci´on de alsi icaciones o iginales se denominan in e ibles.
C a e y sus coau o es in oducen en [2] el concep o de no in e ibilidad. De mane a in o mal,
es o signi ica que es compu acionalmen e imposible pa a un a acan e encon a una imagen
alsa y una ma ca de agua ales que jun as sean id´en icas a la imagen con ma ca de agua
o iginal. Da emos aho a una de inici´on m´as p ecisa.
Sea Ala ma iz o iginal y Wla ma ca de agua usada po el au o pa a ob ene la imagen con
ma ca de agua AW. Esc ibimos en onces
AW=E(A, W),(3.1)
donde E ep esen a el algo i mo de implemen aci´on de ma ca de agua. Si un a acan e que iene
acceso a la imagen AWpublicada sin conoce A, c ea una ma ca de agua alsi icada WFy una
imagen alsa AFque cumplen
AW=E(AF, WF),(3.2)
en onces puede usa AFcomo imagen o iginal pa a eclama la p opiedad de AW.
Si (3.2) se sos iene, el dise˜no se denomina in e ible. De lo con a io, se denomina no in e ible.
Las ecuaciones (3.1) y (3.2) son las ecuaciones b´asicas pa a de ini la no in e ibilidad.
3.1.2. Esquemas de ma ca de agua basados en la SVD
An es de in oduci algunos p ocedimien os pa a inco po a una ma ca de agua a una ima-
gen, e isamos algunas de las p opiedades m´as impo an es de la descomposici´on en alo es
singula es desde el pun o de is a del a amien o de im´agenes:
1. Los alo es singula es son muy es ables, es deci , peque˜nas pe u baciones en la imagen
se aducen en peque˜nas pe u baciones en los alo es singula es de la ma iz asociada
( e Teo ema 3.1.1).
2. Los alo es singula es ep esen an p opiedades algeb aicas in ´ınsecas de la imagen [8].
3. No es necesa io que la imagen sea cuad ada.
3.1. INCORPORACI ´
ON DE UNA MARCA DE AGUA A UNA IMAGEN 31
El esquema de Liu y Tan
Liu y Tan p oponen en [8] el siguien e p ocedimien o pa a inco po a una ma ca de agua
a una imagen dada. Pa imos de la ma iz A∈Rm×nasociada a la imagen y hallamos su
descomposici´on en alo es singula es, A=UΣVT. A con inuaci´on, si W∈Rm×nes la ma iz
asociada a la ma ca de agua, a˜nadimos Wescalada po un pa ´ame o eal aa la ma iz diagonal
Σ, ob eniendo Σ + aW , y hallamos a con inuaci´on la descomposici´on en alo es singula es
de Σ + aW =UWΣWVT
W. La imagen con su ma ca de agua se ´a la asociada a la ma iz
AW=UΣWVT. Siguiendo la no aci´on de [8] los pasos se ´ıan los siguien es:
A→UΣVT,(3.3)
Σ + aW →UWΣWVT
W,(3.4)
AW←UΣWVT.(3.5)
No amos que los pasos (3.3) y (3.4) equie en la SVD de las ma ices Ay Σ + aW. En la
de ecci´on de ma cas de agua, conocidas UW, Σ, VW,ay la imagen posiblemen e dis o sionada
A∗
W, se puede ex ae una ma ca de agua co up a W∗in i iendo los pasos an e io es:
A∗
W→U∗ΣW(V∗)T,
D∗←UWΣWVT
W,(3.6)
W∗←1
a(D∗−Σ) .
De nue o, es necesa ia la SVD en el p ime paso de (3.6).
P obamos a con inuaci´on un esul ado ace ca de la impe cep ibilidad de la ma ca de agua
desc i a p e iamen e.
Teo ema 3.1.1. Sean A,WyAWcomo en (3.3)-(3.5). En onces los alo es singula es de la
ma iz o iginal y de la ma iz con la ma ca de agua sa is acen
|σi(AW)−σi(A)| ≤ a∥W∥2pa a i= 1, ..., m´ın{m, n}.(3.7)
Demos aci´on. No hay m´as que e que, pues o que Ay Σ ( espec i amen e AWy ΣWcom-
pa en los alo es singula es,
|σi(AW)−σi(A)|=|σi(ΣW)−σi(Σ)|=|σi(Σ + aW)−σi(Σ)| ≤ a∥W∥2,
donde la ´ul ima desigualdad la deducimos del Teo ema 1.3.1.
El Teo ema 3.1.1 indica que podemos usa ay∥W∥2pa a de e mina la di e encia en e Ay
AW. Po an o amos a pode ajus a la no ma espec al de la ma ca de agua pa a ene m´as o
32 CAP´
ITULO 3. APLICACIONES
menos impe cep ibilidad. Al inal, lo m´as ´acil a a se ija Wy educi el alo del escala a.
Desde el pun o de is a de la impe cep ibilidad, cuan o m´as peque˜na sea a∥W∥2, m´as pa ecida
a a se la imagen ma cada a la o iginal.
Liu y Tan p opusie on es e modelo en el a˜no 2002, bajo la p emisa de que e a no in e ible [8].
Sin emba go, Zhang y Li demos a on en 2005 [12] que no solo e a un dise˜no in e ible, sino que
adem´as se puede ob ene cualquie ma ca de agua deseada median e el p oceso de ex acci´on
(3.6). Es o se debe a que en (3.4), como Σ es una ma iz diagonal, las ma ices UWyVW
ep esen an subespacios muy simila es a los que gene a ´ıa la SVD de W. Adem´as, sabemos que
la SVD e iene la mayo pa e de la in o maci´on de una imagen (como hemos mencionado en
la Obse aci´on 1.1.2). En onces, en la ex acci´on, da igual la ma iz Σ∗que usemos, la ma iz
inal D∗es ´a en el mismo subespacio de inido po Σ + aW . En o as palab as, (3.6)es ampa la
in o maci´on de la ma ca de agua Wen D∗, independien emen e de AWy de la ma ca de agua
o iginal W. M´as adelan e incluimos un ejemplo pa a ilus a es e hecho.
El esquema de Jain, A o a y Panig ahi.
Jain y colabo ado es [6] p opusie on una mejo a al esquema de Liu y Tan, buscando sol en a
los allos que es e ´ul imo p esen aba an o en la obus ez como en la con ianza.
La soluci´on que los au o es p oponen es que, como la mayo ´ıa de in o maci´on eside en los
ec o es singula es, solo amos a usa los ec o es singula es po la izquie da pa a la ex acci´on
de la ma ca de agua. El esquema es el siguien e:
Dadas A∈Rm×nla ma iz asociada a la imagen o iginal, a∈Rel ac o de escala y W∈Rm×n
la ma iz asociada a la ma ca de agua, hacemos la SVD de las ma ices AyW, y se cons uye
la ma iz de las componen es p incipales AW,a.
A→UΣVT,
W→UWΣWVT
W,(3.8)
AW,a =UWΣW.
A con inuaci´on, se o ma Σ1inco po ando la ma iz AW,a a Σ y a pa i de Σ1ob enemos la
imagen con ma ca de agua,
Σ1= Σ + aAW,a,
AW←UΣ1VT.(3.9)
Si aho a A∗
Wes una imagen con ma ca de agua posiblemen e dis o sionada, pa a ecupe a la
3.1. INCORPORACI ´
ON DE UNA MARCA DE AGUA A UNA IMAGEN 33
ma ca de agua o iginal, dadas A(y po an o UyV), VWya, seguimos los es pasos
A∗
W−A→A1.
1
aUTA1V→A∗
W,a.(3.10)
A∗
W,aVT
W→W∗.
Podemos in oduci un esul ado ace ca de la p ecisi´on de la ma ca de agua ex a´ıda con (3.10).
Teo ema 3.1.2. Sean AWcomo en (3.9),A∗
Wla imagen con ma ca de agua dis o sionada y
W∗como en (3.10). En onces
∥W−W∗∥F=∥A∗
W−AW∥F
|a|.(3.11)
Demos aci´on. Conside emos A=UΣVTyW=UWΣWVT
Wlas descomposiciones en alo es
singula es de AyW, espec i amen e. Si ex aemos la ma ca de agua dis o sionada de la ma iz
pe u bada A∗
Wsiguiendo (3.9), hacemos P=A∗
W−AWy u ilizamos (3.8), enemos
W∗=1
aUT(A∗
W−A)VVT
W=1
aUT(AW−A+P)V V T
W
=1
aUTU(Σ + aUWΣW)VT−A+PV V T
W
=1
aUTA+aUUWΣWVT−A+PV V T
W=1
aUTaUUWΣWVT+PV V T
W
=UWΣWVT
W+1
aUTPV V T
W
=W+1
aUTPV V T
W.
Si aho a calculamos el e o en la ma ca de agua medido en la no ma de F obenius, nos queda
∥W∗−W∥F=∥1
aUTPV V T
W∥F=∥P∥F
|a|=∥A∗
W−AW∥F
|a|,
ya que las ma ices U,V,VWson o ogonales y P=A∗
W−AW.
3.1.3. Una ilus aci´on num´e ica
Pa a mos a el uncionamien o de los esquemas desc i os en la Secci´on 3.1.2 conside amos la
ma iz Aasociada a la imagen mos ada en la Figu a 3.1 y la ma ca de agua W ep esen ada en
la Figu a 3.2. Hemos implemen ado en Ma lab el algo i mo de Jain y sus colabo ado es, (3.8)-
(3.9), y mos amos en las Figu as 3.3 y3.4 las im´agenes con la ma ca de agua inco po ada
cuando a= 0,1 y a=1
255 ( omado de [12]), espec i amen e.
34 CAP´
ITULO 3. APLICACIONES
Figu a 3.1: Imagen o iginal Figu a 3.2: Ma ca de agua
Figu a 3.3: Imagen con ma ca de agua a=
0,1.
Figu a 3.4: Imagen con ma ca de agua a=
1
255 .
S´ı que podemos obse a c´omo pa a el alo de a= 0,1 la ma ca de agua es bas an e pe cep ible
en la imagen, pe o en la Figu a 3.4 ya no se ap ecia apenas di e encia con la imagen o iginal
de la Figu a 3.1.
Aho a pe u bamos la ma iz de la imagen con ma ca de agua sum´andole o a ma iz alea o ia
Bgene ada siguiendo una dis ibuci´on uni o me con un ac o de escala b= 0,1, es deci ,
A∗
W=AW+bB (donde AWes la imagen con la ma ca de agua de la Figu a 3.4), ob enemos lo
siguien e
3.1. INCORPORACI ´
ON DE UNA MARCA DE AGUA A UNA IMAGEN 35
Figu a 3.5: Ma ca de agua eal ex a´ıda.
Es deci , hemos sido capaces de ob ene la ma ca de agua implemen ada en la Figu a 3.4 sin
p oblema.
A con inuaci´on, en las Figu as 3.6 y3.7 podemos e ep esen ada an o la pe cep ibilidad
ela i a de la ma ca de agua, ∥A−AW∥F
∥A∥F, como el e o ela i o come ido en la ex acci´on de
dicha ma ca, ∥W−W∗∥F
∥W∥F, ambos como unci´on del pa ´ame o a. En colo azul se ha ep esen ado
la in o maci´on pa a el m´e odo de Liu y Tan y en colo magen a la co espondien e al m´e odo
de Jain.
Figu a 3.6: Pe cep ibilidad Figu a 3.7: E o en la ex acci´on.
Es as dos igu as ilus an pe ec amen e las a i maciones que se hacen en los Teo emas 3.1.1 y
3.1.2. Cuan o mayo sea el alo de a, la ma ca de agua a a se m´as pe cep ible, pe o ambi´en
amos a pode ecupe a la con mayo p ecisi´on. Tambi´en obse amos que con el m´e odo de
Liu y Tan la pe cep ibilidad es meno , aunque ya hemos is o que aquel esquema en´ıa o as
ca encias.
Aho a, amos a e ´como a ec a a la ex acci´on de la ma ca de agua el hecho de pa i de una
36 CAP´
ITULO 3. APLICACIONES
imagen pe u bada A∗
Wque sea una ap oximaci´on de ango ka la imagen con la ma ca de agua
inco po ada. Pa a ello, oma emos como A∗
W an o la mejo ap oximaci´on AW,k a pa i de la
SVD exac a como la ap oximaci´on de ango kque ob enemos u ilizando la SVD alea o izada.
Las siguien es igu as ep esen an la ma ca de agua ex a´ıda a pa i de la ap oximaci´on de
ango kde la imagen con ma ca de agua mos ada en la Figu a 3.3 (a= 0,1) cuando AW,k se
calcula con la SVD exac a (Figu a 3.8) o con la SVD alea o izada (Figu a 3.9), pa a k= 100.
Figu a 3.8: SVD exac a, k= 100. Figu a 3.9: SVD alea o izada, c= 200, k= 100.
Obse amos que la calidad no es su icien emen e buena en ninguno de los dos casos, aunque en
la Figu a 3.8 s´ı que es posible lee la mayo ´ıa de los d´ıgi os.
Hemos epe ido el mismo expe imen o con dis in os alo es de ay a iando ambi´en el ango
de la ap oximaci´on a la imagen con ma ca de agua AW,k desde k= 1 has a k= 150. En la
Figu a 3.10 se mues an los esul ados cuando AW,k se halla con la SVD exac a y en la Figu a
3.11 cuando se u iliza la SVD alea o izada.
Figu a 3.10: SVD exac a Figu a 3.11: SVD alea o izada
3.1. INCORPORACI ´
ON DE UNA MARCA DE AGUA A UNA IMAGEN 37
Vemos que el e o es m´as peque˜no cuando aes mayo , y que disminuye al aumen a kde o ma
m´as es able y ´apida en la Figu a 3.10 (sin las oscilaciones de la Figu a 3.11), debido a que
pa imos de la SVD exac a pa a hace la ap oximaci´on, y no de la alea o izada. Es deci , pa a
a ijo amos a necesi a un alo mayo de ksi que emos ob ene el mismo e o pa iendo de
la ap oximaci´on calculada con la SVD alea o izada que con la SVD exac a.
En cuan o al alo de a, ya imos en la Figu a 3.3 que pa a a= 0,1 en el caso del esquema
de Jain la impe cep ibilidad no es buena, y de hecho la Figu a 3.6 nos dice que pa a a= 0,25
a a se oda ´ıa peo . Po an o el alo de k a a ene que se al o si que emos ex ae la
ma ca de agua de o ma p ecisa man eniendo un al o g ado de impe cep ibilidad. Sob e es e
´ul imo pun o, no amos que exis e un p ocedimien o que mejo a al de Jain [7], en cuan o a la
impe cep ibilidad, aunque no se ha conside ado en es e abajo.
Finalmen e, podemos comp oba que si ejecu amos el algo i mo de ex acci´on de la ma ca de
agua que p oponen Liu y Tan, es o es, las ecuaciones (3.6), podemos in en a nos cualquie
ma ca de agua en la Figu a 3.4 y ecupe a la a pa i de ella.
Figu a 3.12: Imagen que amos a ex ae de
la Figu a 3.4
Figu a 3.13: Ma ca de agua ex a´ıda de la Fi-
gu a 3.4 con el m´e odo de Liu y Tan.
Figu a 3.14: Ma ca de agua alsa ex a´ıda de la Figu a 3.4 con el m´e odo de Jain.
38 CAP´
ITULO 3. APLICACIONES
En la Figu a 3.12 se mues a la ma ca de agua in en ada que amos a ex ae de la Figu a 3.4,
aunque ealmen e no es ´a ocul a en ella y en la Figu a 3.13 la alsa ma ca de agua ex a´ıda. Sin
emba go, como emos en la Figu a 3.14, si in en amos ex ae con el algo i mo de Jain dicha
ma ca de agua, no lo conseguimos. No hemos podido in en a nos una ma ca de agua que no
exis e, como s´ı hemos podido hace con el m´e odo de Liu y Tan en la Figu a 3.13.
3.2. LSI: An´alisis sem´an ico la en e
Habi ualmen e la in o maci´on se ecupe a empa ejando ´e minos que apa ecen en los documen-
os con los de una b´usqueda. Sin emba go, es e m´e odo puede se imp eciso, debido a que hay
palab as que ienen dis in os signi icados (polisemia) o a ias palab as que ienen signi icados
simila es (sinonimia).
El an´alisis sem´an ico la en e (La en seman ic indexing, LSI) in en a esol e es os p oblemas
usando la elaci´on en e las palab as, la ecuencia con que apa ecen en los documen os y su
elaci´on con o as palab as con las que suelan apa ece de mane a conjun a en ez de conside a
palab as indi iduales pa a la ecupe aci´on.
3.2.1. In oducci´on.
Lo p ime o que necesi a el LSI es cons ui una ma iz que elacione ´e minos con documen os.
Pongamos, po ejemplo, una ma iz A= (aij), 1 ≤i≤m, 1 ≤j≤n, donde aij ep esen a
la ecuencia con la que apa ece el ´e mino ien el documen o j. Como no odas las palab as
apa ecen en odos los documen os, la ma iz Agene almen e a a se una ma iz dispe sa.
La descomposici´on en alo es singula es ob iene y almacena la in o maci´on de Aen las ma ices
U,ΣyV. Es as ep esen an un desglose de las elaciones o iginales en ec o es linealmen e
independien es (las bases de los subespacios columna y ila de las que hablamos en la Obse -
aci´on 1.1.2). El uso de los kp ime os alo es y ec o es singula es es equi alen e a ap oxima
la ma iz de ´e minos-documen os o iginal po Ak. De alguna o ma, la SVD es una ´ecnica
pa a ob ene una se ie de ec o es donde cada ´e mino y documen o es ´a ep esen ando po un
ec o usando los ec o es singula es po la de echa o la izquie da. En pa icula , las columnas
de UyVse conside an los ec o es ´e minos y documen os, espec i amen e.
Es impo an e ene en cuen a que Akno econs uye exac amen e la ma iz o iginal A, pe o
la SVD uncada ecoge la mayo pa e de la es uc u a en la asociaci´on en e ´e minos y do-
cumen os. Al mismo iempo, elimina el uido que abunda en los m´e odos de ecupe aci´on de
in o maci´on basados en palab as.
De o ma in ui i a, como k≪m, el n´ume o de ´e minos, las peque˜nas di e encias en e mino-
3.2. LSI: AN ´
ALISIS SEM ´
ANTICO LATENTE 39
log´ıa se igno a ´an. Po o o lado, ´e minos que apa ecen en dis in os documen os es a ´an ce ca
en el subespacio de dimensi´on k. Es o se aduce en que documen os que no con engan ninguna
palab a de la b´usqueda de un usua io puedan es a ce ca en el subespacio de dimensi´on ksi
exis en o os documen os que engan palab as en com´un con los p ime os.
Conside emos las palab as coche, au om´o il, conduc o y ele an e. Coche y au om´o il son
sin´onimos, ienen elaci´on con conduc o y no ienen nada que e con ele an e. En la ma-
yo ´ıa de sis emas de ecupe aci´on de in o maci´on, la b´usqueda de la palab a coche no a a
p opo ciona m´as documen os sob e au om´o iles que sob e ele an es si no apa ece la palab a
coche en el documen o. Se ´ıa p e e ible que s´ı lo hicie a, incluso que ambi´en incluye a alg´un
documen o sob e conduc o es. La p incipal idea del LSI es modela las elaciones en e ´e minos
(median e la SVD uncada) y ap o echa lo pa a mejo a la b´usqueda.
3.2.2. B´usqueda y ac ualizaci´on
Pa a pode ecupe a la in o maci´on, la b´usqueda debe ep esen a se como un ec o en el
subespacio de dimensi´on k. Una b´usqueda es una se ie de palab as. Po ejemplo, se puede
ep esen a como
ˆ
qT=qTUk(Σk)−1(3.12)
donde qes el ec o con las palab as de la b´usqueda, Uk, Σkson las ma ices de ama˜no m×k
yk×kde la SVD uncada (1.6). En esencia, el ec o b´usqueda es una suma ponde ada de los
´e minos de la b´usqueda, que podemos compa a pos e io men e con los ec o es documen os
exis en es y o dena los po simili ud. Una o ma de medi es a simili ud es el coseno en e el
ec o de b´usqueda y el ec o documen o (midiendo la o ogonalidad en e ambos ec o es).
Po o o lado, suponiendo que ya enemos una base de da os gene ada. Si que emos a˜nadi
nue os ´e minos o nue os documen os, enemos dos opciones: c ea una nue a ma iz, y epe i
odo el p oceso desde el p incipio (incluida la SVD) o ac ualiza las ma ices que ya enemos.
Pa a ac ualiza una base de da os ya c eada, inco po a emos nue os ´e minos y documen os de
la siguien e o ma. Dado d∈Rm×1el ec o del nue o documen o, calculamos
ˆ
dT=dTUk(Σk)−1(3.13)
y lo inco po amos a la de echa de VT
k, es deci , hacemos ˜
VT
k=VT
k|ˆ
d.
Pa a los ´e minos hacemos algo muy simila . Dado el ec o del nue o ´e mino ∈Rn×1,
calculamos
ˆ
T= TVk(Σk)−1,(3.14)
e inco po amos ˆ
Tpo debajo a la ma iz Uk.
46 BIBLIOGRAF´
IA
[11] G. S ang, “Linea Algeb a and Lea ning om Da a”, Wellesley - Camb idge P ess, 2019.
[12] X. Zhang and K. Li, Commen s on “An SVD-Based Wa e ma king Scheme o P o ec ing
Righ ul Owne ship”, IEEE T ansac ions on Mul imedia, Vol. 7, No. 2, pp. 593-594, 2005
Ap´endice A
C´odigo de Ma lab.
En es e ap´endice incluimos los p og amas de Ma lab que implemen an los algo i mos b´asicos
que se han es udiado en es e abajo y que se han u ilizado pa a elabo a las dis in as igu as
que se han incluido en la memo ia.
A.1. P oduc o alea o izado de dos ma ices.
En es e p ime c´odigo se ha implemen ado el Algo i mo 1, p esen ado en el Cap´ı ulo 2. La
unci´on acep a como en adas las ma ices AyBque se quie en mul iplica , el ama˜no cde la
mues a y el ec o de p obabilidades pa a el mues eo. La salida son las ma ices CyR, cuyo
p oduc o ap oxima el de AyB.
1 unc ion [C,R] = basicma ixp od (A,B, c , p ob )
2[m, n1 ] = s i z e (A) ;
3[ n2 , p ] = s i z e (B) ;
4
5i n1 == n2
6n = n1 ;
7C = ze os(m, c ) ;
8R = ze os( c , p) ;
9y = andsample (n , c , ue , p ob ) ;
10 o i =1:c
11 C( : , i ) = A( : , y( i ) ) /( sq ( c∗p ob (y( i ) ) ) ) ;
12 R( i , : ) = B(y( i ) , : ) /( sq ( c∗p ob (y( i ) ) ) ) ;
13 end
14 e l s e
47
48 AP´
ENDICE A. C ´
ODIGO DE MATLAB.
15 p in (’ Las dimensiones de l a s ma ices deben de s e adecuadas
pa a su p oduc o . ’ )
16 end
17
18 end
Incluimos a con inuaci´on una unci´on que, dada una ma iz, calcula las p obabilidades ´op imas
(2.5) an o pa a el p oduc o alea o izado de ma ices como pa a la SVD alea o izada.
1 unc ion p ob = p obabilidades (A,B)
2[˜ , n]= s i z e (A) ;
3p ob = ze os(1 ,n) ;
4denom = 0;
5
6 o i =1:n
7denom = denom + no m(A( : , i ) ) ∗no m(B( i , : ) ) ;
8end
9
10 o j =1:n
11 p ob ( j ) = (no m(A( : , j ) ) ∗no m(B( j , : ) ) ) /denom ;
12 end
13
14 end
A.2. Descomposici´on en alo es singula es alea o izada.
En el siguien e c´odigo implemen a el Algo i mo 2, p esen ado en la Secci´on 2.2. La unci´on
acep a como en adas la ma iz Ade la que se quie e calcula la SVD ap oximada, el ango k
de la ap oximaci´on buscada, el alo cdel ama˜no de la mues a con la que se a a ap oxima el
p oduc o de AATy el ec o de p obabilidades pa a el mues eo. La salida la o man la ma iz
Hky un ec o con los kp ime os alo es singula es de C.
1 unc ion [Hk, Sigma ] = Linea TimeSVD(A, k , c , p ob )
2
3[m, n ] = s i z e (A) ;
4C = ze os(m, c ) ;
5Hk = ze os(m, k) ;
A.3. ESQUEMA DE LIU Y TAN 49
6Sigma = ze os(1 , k) ;
7y = andsample (n , c , ue , p ob ) ;
8
9 o i =1:c
10 C( : , i ) = A( : , y( i ) ) /( sq ( c∗p ob (y( i ) ) ) ) ;
11 end
12
13 CC = anspose (C) ∗C;
14
15 [U, aux , ˜ ] = s d(CC) ;
16 aux = sq ( aux ) ;
17
18
19
20 o j =1:k
21 Hk( : , j ) = C∗U( : , j ) /aux ( j , j ) ;
22 Sigma ( j ) = aux ( j , j ) ;
23 end
24
25 end
A.3. Implemen aci´on y ex acci´on de una ma ca de agua
con el esquema de Liu y Tan.
En el siguien e p og ama se implemen a el esquema de Liu y Tan desc i o en la Secci´on 3.1.2.
La unci´on acep a como en ada dos im´agenes, la o iginal y la ma ca de agua que se quie e
implemen a , y el ac o de escala a. De uel e la imagen IMGWM con la ma ca de agua
inco po ada, jun o con las ma ices necesa ias pa a pode ex ae pos e io men e la ma ca de
agua.
1 unc ion [UW,IMGWM,VW, Sigma ] = ma cadeagua (IMG,MDA, a)
2
3A = im ead (IMG) ;
4W = im ead (MDA) ; %leemos l a s imagenes
5A = im2g ay (A) ;
50 AP´
ENDICE A. C ´
ODIGO DE MATLAB.
6W = im2g ay (W) ; %pasamos la ma ca de agua y la imagen a e sc al a de
g ises
7A = double (A) ;
8W = double (W) ;
9
10 [U, Sigma ,V] = s d(A) ;
11 [UW, SigmaW,VW] = s d( Sigma+a∗W) ;
12 IMGWM = U∗SigmaW∗ anspose(V); %hacemos e l algo i mo
13
14 end
Es a segunda unci´on acep a como en ada los da os que se suponen conocidos pa a pode
ealiza la ex acci´on de la ma ca de agua jun o con la imagen de la que que emos ex ae la, y
de uel e la ma ca de agua ex a´ıda.
1 unc ion [MDA] = ma cadeaguain (UW, Sigma ,VW,IMG, a )
2
3[ ˜ , SigmaW , ˜ ] = s d (IMG) ;
4D = UW∗SigmaW∗ anspose (VW) ;
5MDA = (1/ a ) ∗(D−Sigma ) ;
6
7end
A.4. Implemen aci´on y ex acci´on de una ma ca de agua
con el esquema de Jain e al.
Las siguien es unciones son an´alogas a las de la secci´on an e io , pe o implemen an el esquema
de ma ca de agua de Jain, p esen ado en la Secci´on 3.1.2.
1 unc ion [IMGWM,V,U,VW] = ma cadeaguaJaine (IMG,MDA, a )
2
3A = im ead (IMG) ;
4W = im ead (MDA) ; %leemos l a s imagenes
5A = im2g ay (A) ;
6W = im2g ay (W) ; %pasamos la ma ca de agua y la imagen a esc al a de
g ises
7A = double (A) ;
A.5. IMPLEMENTACI ´
ON DEL AN ´
ALISIS SEM ´
ANTICO LATENTE 51
8W = double (W) ;
9
10 [U, Sigma ,V] = s d(A) ;
11 [UW, SigmaW,VW] = s d(W) ;
12 AWa = UW∗SigmaW;
13 Sigma1 = Sigma+a∗AWa;
14 IMGWM = U∗Sigma1∗ anspose(V);
15
16 end
1 unc ion MDAW = in e s aJ ai ne (AW,A,U,V,VW, a )
2
3A1 = AW−A;
4AWa = (U’∗A1∗V) /a ;
5MDAW = AWa∗ anspose (VW) ;
6
7end
A.5. Implemen aci´on del an´alisis sem´an ico la en e
Finalmen e incluimos el c´odigo donde ep oducimos el ejemplo de [1].
1A( 1 , : ) = [ 0 ,0 , 1 ,0 , 1 ,0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0] ;
2A( 2 , : ) = [ 0 ,0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1] ;
3A( 3 , : ) = [ 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1 ,1 , 0 ,0 , 0 ,0 , 0] ;
4A( 4 , : ) = [ 0 ,0 , 0 ,1 , 0 ,0 , 0 ,1 , 0 ,1 , 1 ,1 , 1 ,1 , 1 ,0 , 0] ;
5A( 5 , : ) = [ 1 ,1 , 0 ,1 , 0 ,0 , 0 ,1 , 0 ,1 , 1 ,1 , 1 ,1 , 1 ,0 , 0] ;
6A( 6 , : ) = [ 0 ,0 , 1 ,0 , 0 ,0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0] ;
7A( 7 , : ) = [ 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,1 , 1] ;
8A( 8 , : ) = [ 0 ,0 , 0 ,0 , 1 ,1 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0] ;
9A( 9 , : ) = [ 0 ,0 , 0 ,0 , 0 ,0 , 0 ,1 , 0 ,0 , 0 ,0 , 0 ,1 , 0 ,0 , 0] ;
10 A( 1 0 , : ) = [ 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1 ,0 , 0 ,0 , 1 ,0 , 0 ,0 , 0] ;
11 A( 1 1 , : ) = [ 0 ,0 , 0 ,0 , 0 ,0 , 0 ,1 , 0 ,1 , 0 ,0 , 0 ,0 , 0 ,0 , 0] ;
12 A( 1 2 , : ) = [ 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1 ,1 , 0 ,0 , 0 ,0 , 0] ;
13 A( 1 3 , : ) = [ 0 ,0 , 0 ,1 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1 ,0 , 0 ,0 , 0] ;
14 A( 1 4 , : ) = [ 0 ,0 , 0 ,0 , 0 ,1 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,1 , 0] ;
52 AP´
ENDICE A. C ´
ODIGO DE MATLAB.
15 A( 1 5 , : ) = [ 0 ,0 , 0 ,0 , 0 ,1 , 0 ,1 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0] ;
16 A( 1 6 , : ) = [ 0 ,0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1 ,1 , 0 ,0 , 0 ,0 , 1] ;
17
18 [m, n ] = s i z e (A) ;
19
20 e minos = [” algo i hms ” ” ap pl ic a io n ” ” delay ” ” d i e e n i a l ” . . .
21 ” equa ions ” ” implemen a ion ” ” i n e g a l ” ” i n oduc ion ” . . .
22 ”me hods” ” nonlinea ” ” o dina y ” ” o s c i l l a i o n ” ” p a ia l ” . . .
23 ”p oblem” ” sys ems ” ” heo y ” ] ;
24 documen os = [”B1” ”B2” ”B3” ”B4” ”B5” ”B6” ”B7” ”B8” . . .
25 ”B9” ”B10” ”B11” ”12” ”B13” ”B14” ”B15” ”B16” ”B17 ” ] ;
26
27 k = 2;
28 [Uk, Sigmak ,Vk] = s ds (A, k) ;
29
30 igu e(1)
31 plo (Uk( : , 1 ) ,−Uk ( : , 2 ) , ’∗’,’colo ’ ,’ magen a ’ ) ;
32 o i =1:16
33 ex (Uk( i , 1 ) ,−Uk( i , 2 ) , e minos ( i ) , ’ Fon Size ’ ,8) ;
34 hold on
35 end
36 plo (Vk( : , 1 ) ,−Vk ( : , 2 ) , ’ o ’ ,’colo ’ ,’ blue ’ )
37 hold on
38 o i =1:17
39 ex (Vk( i , 1 ) +0.005,−Vk( i , 2 ) +0.005 , documen os ( i ) , ’ Fon Size ’ ,8) ;
40 hold on
41 end
42 plo ( [ 0 , 1 ] , [ 0 , 0 ] , ’−’) ;
43 hold on
44
45 que y = [0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1] ;
46
47 q = que y∗Uk/Sigmak ;
48 cos = 0 . 9 ;
49 sen = sq (1−cosˆ2) ;
A.5. IMPLEMENTACI ´
ON DEL AN ´
ALISIS SEM ´
ANTICO LATENTE 53
50 h eshold = [ q (1) ∗cos+q (2) ∗sen , q (1) ∗sen−q (2) ∗cos ] ;
51
52 cos2 = 0 . 5 5 ;
53 sen2 = sq (1−cos2 ˆ2) ;
54 h eshold55 = [ q (1) ∗cos2+q (2) ∗sen2 , q (1) ∗sen2−q (2) ∗cos2 ] ;
55
56 igu e(1)
57 plo ( [ 0 , q (1) ] ,[0 , −q (2) ] , ’d ’ ,’ LineS yle ’ ,’−’,’ Colo ’ ,’ ed ’ )
58 hold on
59 plo (2 ∗[ 0 , h e sh old (1) ] , 2 ∗[ 0 , h eshold (2) ] , ’ LineS yle ’ ,’−’,’ Colo ’ ,’
ed ’ )
60 hold on
61 plo (2 ∗[0 , h eshold55 (1) ] , 2 ∗[ 0 , h eshold55 (2) ] , ’ LineS yle ’ ,’−− ’,’
Colo ’ ,’ ed ’ )
62 hold on
63
64 pause
65
66 d = [0 , 0 ,0 ,0 , 1 ,0 ,0 ,0 , 0 ,1 ,0 , 0 ,0 ,0 , 1 ,0;
67 1 ,0 ,0 ,1 ,1 ,0 ,1 ,0 ,0 , 0 ,1 ,0 ,0 ,0 ,0 ,0;
68 0 ,1 ,0 , 0 ,0 ,0 , 0 ,0 ,0 , 0 ,1 ,1 ,0 ,0 ,0 ,1 ];
69 dd = d∗Uk/Sigmak ;
70
71 Vk = [Vk; dd ] ;
72
73 docsad = [” B18” , ”B19” , ”B20 ” ] ;
74
75
76 igu e(1)
77 plo (Vk(18 :20 ,1 ) ,−Vk(1 8:20 ,2 ) , ’ o ’ ,’colo ’ ,’ g een ’ )
78 hold on
79 o i =1:3
80 ex (Vk( i +17 ,1)+0.005,−Vk( i +17 ,2) +0.005 , docsad ( i ) , ’ Fon Size ’ ,8) ;
81 hold on
82 end
54 AP´
ENDICE A. C ´
ODIGO DE MATLAB.
83
84 AA = [A, d ’ ] ;
85 documen os2 = [ documen os , docsad ] ;
86 [UUk, Sigma2k ,VVk] = s ds (AA, k) ;
87
88 igu e(2)
89 plo (UUk( : , 1 ) ,−UUk( : , 2 ) , ’∗’,’colo ’ ,’ magen a ’ ) ;
90 o i =1:16
91 ex (UUk( i , 1 ) ,−UUk( i , 2 ) , e minos ( i ) , ’ Fon Size ’ ,8) ;
92 hold on
93 end
94 plo (VVk( : , 1 ) ,−VVk( : , 2 ) , ’ o ’ ,’colo ’ ,’ blue ’ )
95 hold on
96 o i =1:20
97 ex (VVk( i , 1 ) +0.005,−VVk( i , 2 ) +0.005 , documen os2 ( i ) , ’ Fon Size ’ ,8) ;
98 hold on
99 end
100 plo ( [ 0 , 1 ] , [ 0 , 0 ] , ’−’) ;
101 hold on
102
103 que y = [0 , 1 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 0 ,0 , 1] ;
104
105 qq = que y∗UUk/Sigma2k ;
106 h eshold2 = [qq(1)∗cos+qq (2) ∗sen , qq (1) ∗sen−qq (2) ∗cos ] ;
107 igu e(2)
108 plo ( [ 0 , qq (1) ] ,[0 , −qq (2) ] , ’d ’ ,’ LineS yle ’ ,’−’,’ Colo ’ ,’ ed ’ )
109 plo (2 ∗[0 , h eshold2(1) ] ,2∗[0 , h eshold2(2) ] , ’ LineS yle ’ ,’−’,’ Colo ’
,’ ed ’ )
110 hold on