Sistemi lineari sovradeterminati e SVD.
Alvise Sommariva Universit`a degli Studi di Padova
Sistemi lineari sovradeterminati.
Si consideri il problema
x1+ x2= 1
x1− x2= 0
x1+ 3x2= 0
Risulta chiaro che il sistema non ha soluzione. Infatti l’unica
soluzione delle prime due equazioni `e x1 = x2= 1/2, che per`o non
verifica x1+ 3x2= 0.
Ritrascrivendo tutto in termini matriciali, possiamo dunque affermare che il problema Ax = b, con
A = 1 1 1 −1 1 3 e b = (1, 0, 0) non ha soluzione.
Sistemi lineari sovradeterminati.
In alternativa, risulta quindi ragionevole calcolare x∗= (x1∗, x2∗)
tale che γ := min x ∈Cnkb − Axk2= kb − Ax ∗k 2 (1) dove kuk2= s X i u2i.
La prima questione riguarda l’esistenza e unicit`a di tale minimo x∗.
Sistemi lineari sovradeterminati.
Teorema
Sia X l’insieme dei vettori di Cn tali che ˆx ∈ X se e solo se
min
x ∈Cnkb − Axk2 = kb − Aˆx k2 (2)
Supponiamo A ∈ Cm×n con m ≥ n e b ∈ Cn. Allora
1. x ∈ X se e solo se
AHAx = AHb, (3)
cio´e x risolve il sistema delle equazioni normali.
2. X `e un insieme non vuoto, chiuso e convesso.
3. Esiste x∗ ∈ X (detto soluzione di minima norma) tale che
kx∗k2= min
x ∈Xkxk2.
4. L’insieme X si riduce ad un solo elemento x∗ se e solo se la
matrice A ha rango massimo.
Sistemi lineari sovradeterminati.
Alcune fattorizzazioni: QR.
Data una matrice A ∈ Cm×n esistono Q ∈ Cm×n unitaria (cio˙e
QQH = Im, QHQ = In) ed R ∈ Cn×n triangolare superiore tali che
A = QR.
Si osservi che a seconda degli autori la fattorizzazione QR sopraindicata viene sostituita con la fattorizzazione A = QR con
Q ∈ Cm×m unitaria ed R ∈ Cm×n triangolare superiore cio`e
R =
R1 0
con R1 ∈ Cn×n triangolare superiore. Per distingure le
fattorizzazioni chiamano la primaQR economy-size.
Alcune fattorizzazioni: SVD.
Sussiste il seguente teorema [8]:
Teorema
Sia A ∈ Cm×n. Allora esistono due matrici unitarie U ∈ Cm×m,
V ∈ Cn×n e una matrice diagonale Σ ∈ Rm×n+ avente elementi σij
nulli per i 6= j e uguali a σi ∈ R+ per i = j con
σ1 ≥ σ2≥ . . . ≥ σn≥ 0 (4)
tali che
A = UΣVH.
Il termine SVD sta persingular value decomposition e sottolinea la
presenza dei valori singolari σi. Se λi e σi sono rispettivamente gli
autovalori di ATA in ordine decrescente e i valori singolari di A in
ordine decrescente, allora
λi =
√
Alcune fattorizzazioni: SVD.
Nota.
Il costo computazionale del calcolo delle tre matrici U, V , Σ `e di
4m2n + 8mn2+ 9n3 se si utilizza l’algoritmo di Golub-Reinsch
oppure di 4m2n + 22n3 se si usa l’algoritmo R-SVD.
In generale esistono algoritmi speciali basati sull’algoritmo di Golub-Reinsch che a seconda si debba calcolare esclusivamente Σ,
Σ e V , Σ e U eseguono rispettivamente 4mn2− 4n3/3,
4mn2+ 8n3, 4mn2− 8mn2 operazioni.
Simili risultati si possono ottenere con l’algoritmo R-SVD con
complessit`a rispettivamente 2m2n + 2n3, 2m2n + 11n3,
2m2n + 13n3.
Ricordiamo che usualmente nelle applicazioni si ha m n.
Risoluzione equazioni normali: Cholesky.
Mostriamo ora tre metodi per risolvere il problema sopra descritto,
cio`e relativo al calcolo di x∗ che minimizza la norma 2 del residuo,
cio`e kb − Ax k2.
Supponiamo A ∈ Rm×n abbia rango n. Dal teorema 0.1 sappiamo
che la soluzione ai minimi quadrati esiste, `e unica e risolve
AHAx = AHb.
Nel caso A abbia coefficienti in R, ci´o si riduce a risolvere
ATAx = ATb. In questo caso AHA `e definita positiva e si p`o
Risoluzione equazioni normali: Cholesky.
Se LLH = AHA per L triangolare inferiore (fattorizzazione di
Cholesky) basta risolvere
Ly = AHb,
LHx = y .
Il costo computazionale `e di n2m/2 operazioni moltiplicative per la
costruzione di AHA e di n3/6 moltiplicative per la soluzione del
sistema, e quindi il costo totale `e di
n2m/2 + n3/6
operazioni moltiplicative.
Nota. (Facoltativo)
Se A non ha rango massimo non si pu`o applicare il metodo di
Cholesky, ma l’eliminazione gaussiana con la variante del massimo pivot.
Risoluzione equazioni normali: QR.
Supponiamo il rango di A ∈ Cm×n sia r = n (cio`e sia massimo).
Nota la fattorizzazione QR si deduce che
Rx = QHQRx = QHb ∈ Cn.
Osserviamo infatti che essendo QHQ = In
AHA = RHQHQR = RHQHQR = RHR
e che inoltre RH `e non singolare. Inoltre AHA `e definita non
negativa essendo
xHAHAx = kAx k2 ≥ 0.
Essendo AHAx = AHb ed AHA = RHR abbiamo che
RHRx = AHb. A questo punto posto y = Rx prima risolviamo il
Risoluzione equazioni normali: QR.
Se A ha rango massimo allora R `e non singolare e quindi il
problema Rx = QHb risolto facilmente per sostituzione all’indietro.
Il costo computazionale per la fattorizzazione QR `e di
n2(m − n/3), il costo computazionale della risoluzione del sistema
triangolare `e n2/2 operazioni moltiplicative.
Quindi il costo totale `e
n2(m − n/3) + n2/2.
Risoluzione equazioni normali: QR.
Nota. (Facoltativo)
Se A non ha rango massimo allora AE = QR con E matrice di permutazione, R = R1 S 0 0
dove R ∈ Cn×n, R1 ∈ Cr ×r sono matrici triangolari superiori. Si
dimostra (non facile) che posto
c = QHb = c1 c2 , c1 ∈ Cn, c2 ∈ Cn−m
Risoluzione equazioni normali: SVD.
Siano ui, vi le i-sime righe rispettivamente di U e V . Allora
Teorema
Sia A ∈ Cm×n di rango r con m ≥ n e sia
A = UΣVH
la decomposizione ai valori singolari di A. Allora la soluzione di
minima norma `e data da
x∗= r X i =1 uiHb σi vi e γ2= m X i =r +1 |uH i b|2 dove al solito γ := min x ∈Cnkb − Axk2 = kb − Ax ∗k 2. (5)
Osserviamo che la soluzione x∗ viene calcolata senza risolvere alcun
sistema lineare (a differenza di quanto accade col metodo QR).
Applicazione: approssimazione in norma 2
Sia f una funzione reale e continua e siano xi punti a due a due
distinti appartenenti al dominio di f . Si cerca il polinomio
pn−1(x ) = c0+ c1x + . . . + cn−1xn−1, c0, . . . , cn−1∈ R
per cui sia minimo m X
i =1
[pn−1(xi) − f (xi)]2.
Tale polinomio pn−1, detto di polinomio di miglior approssimazione,
esiste ed `e unico. Si prova che il calcolo di tale polinomio
corrisponde a risolvere il problema sovradeterminato Vc = ¯f dove
Applicazione: approssimazione in norma 2
Vediamo i dettagli. Sia Vi ,· la i -sima colonna di V . Notiamo
subito che
pn−1(xi) = c0+ c1xi + . . . + cn−1xin−1 = Vi ,·c
e quindi per definizione di ¯f
m X i =1 [pn−1(xi) − f (xi)]2 = m X i =1 [Vi ,·c − ¯fi]2
Ricordiamo ora che la soluzione di un sistema sovradeterminato
Vc = ¯f (con V ∈ Rm×n) `e quella che minimizza kVc = ¯f k2 e
quindi pure
kVc − ¯f k22=X
i
[(V ∗ x )i− ¯fi]2.
Di conseguenza il vettore c avente quali coefficienti i termini ci del
polinomio di miglior approssimazione del problema di
approssimazione `e il vettore che risolve il sistema sovradeterminato
Vc = ¯f , che pu`o essere risolto con uno dei metodi
precedentemente indicati.
Fattorizzazione QR in Matlab
Vediamo di seguito alcuni dettagli di come tali fattorizzazioni sono implementate in Matlab. In merito alla fattorizzazione QR, l’help di Matlab fornisce le seguenti indicazioni:
>> h e l p q r
QR O r t h o g o n a l−t r i a n g u l a r d e c o m p o s i t i o n .
[ Q , R ] = QR ( A ) p r o d u c e s an u p p e r t r i a n g u l a r m a t r i x R of the s a m e d i m e n s i o n as A and a u n i t a r y m a t r i x Q so t h a t A = Q∗R .
[ Q , R , E ] = QR ( A ) p r o d u c e s a p e r m u t a t i o n mat rix E , an u p p e r
t r i a n g u l a r R and a u n i t a r y Q so t h a t A∗E = Q∗R . The c o l u m n p e r m u t a t i o n E is c h o s e n so t h a t a b s(d i a g( R ) ) is d e c r e a s i n g . [ Q , R ] = QR ( A , 0 ) p r o d u c e s the ” e c o n o m y s i z e” d e c o m p o s i t i o n . If A is m−by−n w i t h m > n , t h e n o n l y the f i r s t n c o l u m n s of Q are c o m p u t e d . [ Q , R , E ] = QR ( A , 0 ) p r o d u c e s an ” e c o n o m y s i z e” d e c o m p o s i t i o n in w h i c h E is a p e r m u t a t i o n vector , so t h a t Q∗R = A ( : , E ) . The c o l u m n p e r m u t a t i o n E is c h o s e n so t h a t a b s(d i a g( R ) ) is d e c r e a s i n g .
Fattorizzazione QR in Matlab
For s p a r s e m a t r i c e s , QR can c o m p u t e a ” Q−l e s s QR d e c o m p o s i t i o n ” ,
w h i c h has the f o l l o w i n g s l i g h t l y d i f f e r e n t b e h a v i o r .
R = QR ( A ) r e t u r n s o n l y R . N o t e t h a t R = c h o l( A ’∗ A ) .
[ Q , R ] = QR ( A ) r e t u r n s both Q and R , but Q is often nearly f u l l. [ C , R ] = QR ( A , B ) , where B has as many rows as A , r e t u r n s C = Q ’∗ B . R = QR ( A , 0 ) and [ C , R ] = QR ( A , B , 0 ) p r o d u c e e c o n o m y s i z e r e s u l t s . The s p a r s e v e r s i o n of QR d o e s not do c o l u m n p e r m u t a t i o n s . The f u l l v e r s i o n of QR d o e s not r e t u r n C .
The l e a s t s q u a r e s a p p r o x i m a t e s o l u t i o n to A∗x = b can be found w i t h the Q−l e s s QR d e c o m p o s i t i o n and one s t e p of i t e r a t i v e r e f i n e m e n t :
x = R \( R ’ \ ( A ’∗ b ) ) r = b − A∗x e = R \( R ’ \ ( A ’∗ r ) ) x = x + e ;
See a l s o LU , NULL , ORTH , Q R D E L E T E , Q R I N S E R T , Q R U P D A T E .
>>
Fattorizzazione QR in Matlab
Nel caso della matrice
A = 1 1 1 −1 1 3
Fattorizzazione QR in Matlab
>> Q ’∗ Q a n s = 1 . 0 0 0 0 0 −0.0000 0 1 . 0 0 0 0 −0.0000 −0.0000 −0.0000 1 . 0 0 0 0 >>norm( A−Q∗R ) a n s = 4 . 9 9 3 8 e−016 >>% SECONDA FATTORIZZAZIONE QR . >> [ Q , R ]=q r( A , 0 ) Q = −0.5774 0 . 0 0 0 0 −0.5774 −0.7071 −0.5774 0 . 7 0 7 1 R = −1.7321 −1.7321 0 2 . 8 2 8 4 >> Q ’∗ Q a n s = 1 . 0 0 0 0 0 0 1 . 0 0 0 0 >>norm( A−Q∗R ) a n s = 4 . 9 9 3 8 e−016Fattorizzazione QR e SVD in Matlab
Nota. (Facoltativo)
Dal punto di vista implementativo `e facile calcolare la
fattorizzazione QR di A anche quando il rango A non `e massimo,
utilizzando [Q,R,E]=qr(A). Si stabilisce facilmente il rango r di A cercando il numero di elementi diagonali di R non nulli.
Fattorizzazione SVD in Matlab
Osserviamo che Matlab dispone del comando svd. La descrizione
dell’help `e la seguente:
>> h e l p s v d
SVD S i n g u l a r v a l u e d e c o m p o s i t i o n .
[ U , S , V ] = SVD ( X ) p r o d u c e s a d i a g o n a l matrix S , of the same d i m e n s i o n as X and w i t h n o n n e g a t i v e d i a g o n a l e l e m e n t s in d e c r e a s i n g order , and u n i t a r y m a t r i c e s U and V so t h a t X = U∗S∗V ’ .
S = SVD ( X ) r e t u r n s a v e c t o r c o n t a i n i n g the s i n g u l a r v a l u e s .
[ U , S , V ] = SVD ( X , 0 ) p r o d u c e s the ” e c o n o m y s i z e”
d e c o m p o s i t i o n . If X is m−by−n w i t h m > n , t h e n o n l y the f i r s t n c o l u m n s of U are c o m p u t e d and S is n−by−n .
See a l s o SVDS , G S V D .
O v e r l o a d e d m e t h o d s
Fattorizzazione SVD in Matlab
Per fare pratica con questo comando sia A = 1 1 1 −1 1 3
e utilizziamo [U,S,V] = svd(A) per avere la decomposizione
SVD della matrice A. Il risultato `e
>> A =[1 1 ; 1 −1; 1 3 ] ; >> [ U , S , V ] = s v d( A ) U = 0 . 3 6 5 1 0 . 4 4 7 2 −0.8165 −0.1826 0 . 8 9 4 4 0 . 4 0 8 2 0 . 9 1 2 9 −0.0000 0 . 4 0 8 2 S = 3 . 4 6 4 1 0 0 1 . 4 1 4 2 0 0 V = 0 . 3 1 6 2 0 . 9 4 8 7 0 . 9 4 8 7 −0.3162
Fattorizzazione SVD in Matlab
Nota.
Si pu´o dimostrare che il rango della matrice `e esattamente il
numero di σi non nulli.
In realt´a la tentazione di determinarlo in virt´u dei termini diagonali
di Σ pu´o risultare fallace in quanto il computer fornisce solo
un’approssimazione dei σi e qualora questi siano molto piccoli non
si pu´o determinare con sicurezza il rango della matrice.
Nota. (Facoltativo)
Esiste un legame tra valori singolari e autovalori. Pi`u precisamente
se {λi} sono gli autovalori di AHA allora σi =
√ λi.
Fattorizzazione SVD in Matlab
Vediamolo con un esempio: >> A =[1 1 ; 1 −1; 1 3 ] A = 1 1 1 −1 1 3 >> [ U , S , V ]=s v d( A ) ; >> S S = 3 . 4 6 4 1 0 0 1 . 4 1 4 2 0 0
>>% LEGAME VALORI SINGOLARI E AUTOVETTORI .
Esempio sistemi sovradeterminati
Proviamo a risolvere il problema iniziale
x1+ x2= 1
x1− x2= 0
x1+ 3x2= 0
coi metodi sopracitati.
Esempio sistemi sovradeterminati
Lavoriamo direttamente nella shell di Matlab/Octave: >>% EQUAZIONI NORMALI . >> A =[1 1 ; 1 −1; 1 3 ] ; >> b =[1 0 0 ] ’ ; >> C=A ’∗ A ; >> b1=A ’∗ b ; >> f o r m a t l o n g >> x=C\b1 x = 0 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 −0.00000000000000 >>% METODO QR >> [ Q , R ]=q r( A ) ; >> s i z e( Q ) a n s = 3 3 >> s i z e( R ) a n s = 3 2
>>% COMMENTO: NON E ’ LA FATTORIZZAZIONE CERCATA
>>% ”R” DEVE ESSERE QUADRATA .
Esempio sistemi sovradeterminati
>> x=R\b1 x = 0 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >>% SOLUZIONE VIA SVD . >> [ U , S , V ]=s v d( A ) ; >> s i z e( U ) a n s = 3 3 >> s i z e( V ) a n s = 2 2 >> s i z e( b ) a n s = 3 1 >> c1=U ’∗ b ; >> s i z e( c1 ) a n s = 3 1 >> c2=c1 ( 1 :s i z e( V , 1 ) ) ; >> s=c2 . /d i a g( S ) ; >> x=V∗s x = 0 . 3 3 3 3 3 3 3 3 3 3 3 3 3 3 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 >> g a m m a _ v a l u e=norm( A∗x−b , 2 ) g a m m a _ v a l u e = 0 . 8 1 6 4 9 6 5 8 0 9 2 7 7 3 >> a b s( ( U ( : , 3 ) ) ’∗ b ) a n s = 0 . 8 1 6 4 9 6 5 8 0 9 2 7 7 3 >>Esempio sistemi sovradeterminati
Commentiamo i risultati a partire da quanto visto per il metodo
QR, visto che la risoluzione via equazioni normali `e del tutto ovvia.
I L’implementazione in Matlab di QR per matrici rettangolari A
richiede una precisazione. Sia x∗ la soluzione del problema
sovradeterminato. Il comando [Q,R]=qr(A) comporta che Q
sia quadrata, mentre [Q,R]=qr(A,0) implica che R `e
quadrata, come da noi richiesto.
I Per quanto riguarda la soluzione via SVD, l’unico punto da
osservare `e che in un precedente teorema si dice che
x∗ = k X i =1 uiHb σi vi
dove ui, vi sono le righe di U e V . La sommatoria `e limitata
alle prime k righe e per questo abbiamo effettuato >> c1=U ’∗ b ;
Esempio sistemi sovradeterminati
I Si osservi che il rango k per la matrice in questione `e uguale a
n cio`e 2, che altri non `e che size(V , 1). Se il rango non fosse
stato massimo, cio`e r 6= n, prima sarebbe stato opportuno
calcolare il rango r e poi sostituire c1(1:size(V,1),:); con c1(1:r,:);
Ricordiamo che 1:r genera il vettore riga [1 2 . . . r ] e che c2=c1(1:r); assegna a c2 le righe dalla prima all’ r -sima del vettore c1 >> r =5; 1 : r a n s = 1 2 3 4 5 >> c1 =[1 4 2 6 4 8 4 ] c1 = 1 4 2 6 4 8 4 >> c1 ( 1 : r ) a n s = 1 4 2 6 4
Esempio sistemi sovradeterminati
I Essendo vi le righe di V , posto si = uHi b/σi risulta che
x∗= r X i =1 uiHb σi vi = Vs.
Nell’ultima parte si mostra che effettivamente la norma 2 del
residuo cio`e kAx∗− bk coincide con
γ2=
m X
i =r +1
|uiHb|2.
In merito osserviamo che il rango della matrice `e r = 2 ed
Esempio sistemi sovradeterminati
I Pu`o restare il dubbio di come si faccia a sapere per via
numerica che il rango di A `e 2. Questo corrisponde al numero
di coefficienti diagonali di S non nulli e quindi da >> A =[1 1 ; 1 −1; 1 3 ] ; >> [ U , S , V ]=s v d( A ) ; >> d i a g( S ) a n s = 3 . 4 6 4 1 1 . 4 1 4 2 >> t=f i n d(a b s(d i a g( S ) ) >0) ; >> rango=l e n g t h( t ) r a n g o = 2 >>
deduciamo che il rango `e 2.
Compressione di immagini
Consideriamo i siti web [6], [2], [5]. L’argomento esposto `e la
compressione di immagini via SVD. In particolare si accenna ad una interessante implementazione in Matlab (non funziona in Octave!) relativa alla compressione di immagini. Entriamo nei dettagli. Sia
A = UΣVT la fattorizzazione SVD della matrice A. Se σi sono gli
elementi diagonali della matrice diagonale e rettangolare Σ, uk la
k-sima colonna di U, vk la k-sima colonna di V , allora
A = n X
k=1
Compressione di immagini
Infatti, se ek ∈ Rm `e il vettore colonna avente tutte componenti
nulle eccetto la k sima che `e uguale a 1, indicato con Vk,·H ∈ Cn la
k-sima riga di VH e con U·,k la k-sima colonna di U abbiamo dopo
qualche conto (provare a farli, anche a modo proprio!) che
ΣVH =
n X
k=1
σkek∗ Vk,·H
da cui evidenziando il prodotto tra matrici ∗, ricordando la sua
propriet`a associativa e ricordando la linearit`a delle operazioni
U ∗ Σ ∗ VH = U ∗ (Σ ∗ VH) = U ∗ n X k=1 σkek∗ Vk,·H ! = n X k=1 σkU ∗ ek∗ Vk,·H = n X k=1 σk(U ∗ ek) ∗ Vk,·H = n X k=1 σkU·,k∗ Vk,·H (6)
Compressione di immagini
Quindi essendo uk la k-sima colonna di U, vk la k-sima colonna di
V abbiamo uk = U·,k e vkH = Vk,·H, nonch`e
U ∗ Σ ∗ VH =
n X
k=1
σkuk∗ vkH.
Osserviamo che le matrici Ck := uk ∗ vkH hanno rango 1 in quanto
la loro immagine `e uno spazio di dimensione 1, visto che
Ck ∗ y = uk ∗ vkH∗ y = (v , y )uk
dove al solito (·, ·) `e il prodotto scalare in Cn.
Se l’indice k viene ordinato cosicch`e i valori singolari siano in
ordine decrescente, cio`e
σ1 ≥ σ2≥ . . . ≥ σn
Compressione di immagini
Se in particolare la matrice A `e una matrice ottenuta codificando i
bit di un’immagine, si capisce che si pu`o comprimere la foto
utilizzando per r < n invece di A la matrice
Ar =
r X
k=1
σkukvkH.
Vediamone un implementazione in Matlab. Scarichiamo dal sito [5] il file compression.zip e una volta decompresso, utilizziamo la routine imcompr.m per comprimere un’immagine di tipo bitmap, come ad esempio il gatto salvato in gatto.bmp. Osserviamo che il
gatto `e codificato tramite una matrice di interi di dimensione
416 × 325.
Lanciando dalla shell di Matlab (non funziona in Octave!) il comando
>> [ im ] = i m c o m p r (’ g a t t o . bmp ’, 2 0 ,’ g a t t o 2 0 . bmp ’) ; >> [ im ] = i m c o m p r (’ g a t t o . bmp ’, 5 0 ,’ g a t t o 5 0 . bmp ’) ; >> [ im ] = i m c o m p r (’ g a t t o . bmp ’, 1 0 0 ,’ g a t t o 1 0 0 . bmp ’) ;
Compressione di immagini
Il risultato sono 3 foto dello stesso gatto, con diversi fattori di compressione, in quanto abbiamo usato valori di r diversi (r=20, 50, 100).
Figura : Compressione di una foto via SVD.
Per ulteriori dettagli si confronti [4], p.180, esempio 6.9.
Compressione di immagini
Nota.
Si pu`o notare che dopo la compressione, la dimensione del file
compresso `e maggiore di quello originale. La ragione `e che il
secondo `e relativo ad una matrice avente componenti intere
mentre quelle del primo sono reali. Nonostante questo problema, l’idea mostra una possibile strada per comprimere immagini.
Bibliografia
D. Bini, M. Capovani, O. Menchi, Metodi numerici per l’algebra lineare, Zanichelli, 1988. Cleve’s corner, Professor SVD
http://www.mathworks.com/company/newsletters/news notes/oct06/clevescorner.html.
G. H. Golub e C.F. Van Loan, Matrix Computatations, Third Edition, John Hopkins University Press, 1996. A. Quarteroni ed F. Saleri, Introduzione al Calcolo Scientifico, Springer, 2006.
L. Rosa, Image compression
http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=4772&objectType=File. K. Sandberg, The Singular Value Decomposition of an Image
http://amath.colorado.edu/courses/4720/2000Spr/Labs/SVD/svd.html G.W. Steward, On the Early History of the Singular Value Decomposition http://www.ima.umn.edu/preprints/April92/952.pdf.
Wikipedia (Singular value decomposition)
