剩下的時間不多,我們只講到四點,所以我們只講用得上的地方,作業要出一個這個啦,所以我們就只講作業要用到的東西就好了,然後是星號的地方啦,其實作業我記得開學有說過六次只算五次嘛對不對,你就少做一次也是可以的啦。

我們今天要講的是singular value decomposition,它是範圍外的東西。這個東西其實很神奇,我們之前講過對角化,我們可以確定說一個對稱的矩陣它一定可以被對角化,但不是隨便拿一個矩陣,如果它不是對稱的,我隨便拿一個矩陣出來,它有可能可以被對角化,也有可能不行被對角化,所以感覺對角化這個東西也還好,沒有那麼general。

但是singular value decomposition它很general,任何的function,而且不一定要是方形的,討論對角化的時候我們只討論方形的square的matrix,但是任何matrix都有singular value decomposition,這個地方寫在課本的七點七。

這個singular value decomposition是什麼意思呢?它的意思是說,任何一個,是任何一個喔,你就不用再想任何什麼限制,它是不是對稱的,什麼都不用想,任何的matrix A,它都可以拆成三個matrix U, sigma,跟V的transpose的相乘,等一下我們會講說作業裡面會怎麼用到這個拆解。

這個A可以拆解成U乘以sigma乘以V的transpose,U是mxn的matrix,sigma是mxn的matrix,V的transpose是nxn的matrix。

那這個U跟V的transpose,它們的column都是orthonormal,就是V的這些,U的這些column它們都是orthonormal,V的這些row它們都是orthonormal,它們都是orthonormal。

然後這個sigma,它是diagonal,它是只有對角線的地方有值,而且等一下還會講說它的對角線的地方有值還有某種特別的型態,我們先講它的對角線的地方有值的意思是什麼呢?

它的對角線的地方有值的意思是說,當然一般我們討論diagonal matrix的時候都假設它是正方形的,所以它就是從左上到右下,那一個不是正方形的matrix,它說它是diagonal是什麼意思呢?

就是說還是一樣從左上往下看,但是到某個地方就會停,我想大家應該知道我的意思吧,就是一樣是在對角線的地方是有值的,然後其他地方都是0,其他地方都是0,其他地方都是0。

好,所以任何一個matrix都可以拆解成這個樣子啦,然後我們知道說orthonormal的vector set它是independent的,而independent不見得是orthogonal或orthonormal,但orthonormal一定是independent,如果orthogonal還不見得是independent,因為你要考慮zero vector的狀況,但orthonormal沒有zero vector,所以orthonormal一定是independent。

所以U它的column都是independent,V它的row都是independent,然後這個σ還有一個神奇的地方就是,它的對角線的值一定都是非負的,就是一定都是大於等於零的。

好,所以其實σ它可以寫成右上角這個樣子,它只有對角線的地方有值,其他地方都是零,那雖然說只有對角線的地方有值,但是它也可以是零,了解嗎?

就不是對角線的地方一定要是零,不是對角線的地方一定要是零,這個地方一定要是零,這個地方一定要是零,那對角線的地方如果是零的話也沒有問題,而且σ它對角線的地方一定是大於等於零的,不會是負的,它一定是大於等於零的。

然後它對角線的值是由大排到小的,就假設它最右上角的值是σ1,然後再來是σ2,那σ1一定是大於等於σ2,然後大於等於σ3,一直排到σk,然後因為零是最小的,它一定是非負的,所以零是最小的。

所以σ1到σ2到σk是大於零的,然後剩下的部分就一直是零零零這樣排下去,這樣大家聽得懂嗎?這個大家有問題嗎?

有些人不問為什麼,它就是這個樣子,就是很厲害這樣,它就是這樣子。你想問說這個會不會考試嗎?這個不會考,這個是考試範圍之外。

期中考第五題。期中考第五題不是叫你算一個reduceable hreform,然後在control再算reduceable hreform?就是這個東西這樣子嗎?好啊,你可以回去想看看這樣子。

那期中考那一題不是習題裡有嗎?這樣子,啊,習題你全部刷過了這樣,我記得那一題是習題裡有的。好,那不重要,期中考考完就算了這樣,不重要。

好,那現在我們要問的問題是,從σ,你其實可以看出matrix A的rank,怎麼看呢?

假設我已經告訴你說matrix A它就長右上角這個樣子,它的對角線只有k個非零的值,就σ1到σk,你其實就可以看出matrix A它的rank是多少,怎麼看呢?

matrix A的rank就是k,你中間的σ,它對角線有幾個非零的數字,matrix A它的rank就是多少,怎麼說呢?

假設我問你的不是整個matrix A的rank,我直接問你σ的rank是多少,這個大家知道嗎?σ的rank是多少,大家知道嗎?對,就是k,沒錯,σ的rank就是k。

那怎麼說呢?比如說你就對它做reduce row a to the form,其實它已經很接近reduce row a to the form,你就做一下,a就會發現它的rank是k,對角線有k個非零的值,它的rank就是k。

好,但是它的rank是k並不代表A的rank是k,左邊乘上一個u,右邊乘上一個v的transpose,到底對rank有什麼樣的影響呢?

那其實在期中考前,在複習的時候,我們講了一個課本的習題,這個課本的習題告訴我們這件事,它說如果我們把A跟B乘起來算它的rank,它會小於等於A的rank,也會小於等於B的rank,它會小於等於A跟B的rank裡面比較小的那一個。

所以我們現在至少確定說A的rank一定是小於等於k的,今天既然σ的rank都已經是k了,左邊乘u,右邊乘v的transpose,它的rank其實應該是會變少的,所以A的rank就是小於等於k啦。

但是我們接下來又說,如在剛才那個case,如果右邊乘的那個matrix,它的rank是n,如果右邊乘的那個matrix,就是這個B是nxk嘛,如果B是nxk,然後它的rank是n,也就是它的rank的數目等於它的row的數目的話,那rankAB就等於rankA。

所以今天v的transpose,因為它所有的row都是independent的,我剛才說因為所有的row都是orthonormal,所以所有的row都是independent的,既然所有的row都是independent的,那σ乘上v的transpose並不會改變它的rank。

然後左邊那個u啊,我們說左邊的那個matrix,如果它的rank也是n的話,那它AB的rank會等於rankB。所以左邊這個u,因為它的column是independent的,所以它乘上這個σ以後,它的rank也不會變。

所以你看這個σ,就可以知道A的rank是多少。或者是你可以說,假設n的A的rank是k,你對它做singular value decomposition,它的縮寫就是SVD。

假設A這個matrix,它的rank是k,你對它做SVD,那中間解出來的那個σ,你看對角線有多少非0的數值,那就知道說A的rank有多少。

好,那接下來啊,我們其實可以把σ裡面非0的部分通通蓋掉。我們把非0的部分通通蓋掉。通通蓋掉以後,我們這邊只剩一個kxk的matrix,只剩一個kxk的matrix。

那接下來我們可以把u跟v的transpose裡面,對應到黑色的部分也把它蓋住。也就是說,u只取它的前k個column,v也只取它的前k個column,也就是v的transpose只取它前k個row。

接下來呢,我們把這個改造後的u稱為u1,把這個改造後的σ稱為σ'、把改造後的vtranspose稱為v1的transpose。

把它們三個相乘以後,你會發現說它仍然是等於A的。為什麼呢?其實這個也可以秒說明,就是說,我們說這個k等於u乘上σ乘以1的乘後。

那現在呢,我們說這個A呢,你可以看作是一個matrix,它的左邊是這個u1,然後呢,這個地方就說它是u2,然後這個有一個σ,然後這個σ呢,它左上角的地方,我們稱之為σ'、剩下的地方呢,就是0。

然後v呢,我們就說它是v1的transpose跟v2的transpose,然後如果我們把它相乘的話,先把這兩個東西相乘,就做plot的相乘,x乘以x加x乘以x,是什麼東西呢?

是u1乘以σ',那右邊呢,0、0、0、0,所以它是0,再乘以這樣,再乘以v1的transpose、v2的transpose,然後接下來這個乘這個加這個乘這個,等於u1σ'、v1的transpose。

好,所以我們其實可以把中間σ等於0的部分通通都拿掉,等於0的部分拿掉,然後u呢,只保留前k個column,v只保留前k個row,那得到這樣子的結果,乘出來的A呢,仍然不變,乘出來的A仍然不變。

好,那這個東西可以拿來做什麼呢?其實它就是等於是拿來做矩陣的壓縮,其實就是拿來做矩陣的壓縮,那等一下呢,我們再來講這件事情。

好,那其實啊,那假設我們今天不只是拿掉0的部分,我們剛才只拿掉了0的部分,如果我們現在拿的部分是超過於0的部分,

我們連σk的部分也拿掉的話,會發生什麼事呢?當我們把σk的部分也拿掉的話,那顯然乘出來的結果,u1乘σ'乘以v1t就已經不等於A了。

就是如果我們今天把σk拿掉,我們把σk拿掉,所以這邊變成是一個σ'變成k-1乘k-1的matrix,u1變成n乘以k-1的matrix,v1的transpose變成k-1乘n的matrix。

假設我們做這樣子的operation,中間我們是k-1乘k-1,那乘出來以後呢,就會等於A',這個時候A'就不等於A了,就假設我們只拿掉等於0的部分,只保留這個部分的話,跟原來是一樣的。

但是如果我們拿掉了有對應到非0的地方的值的話,那得出來的A'就跟A就不一樣,雖然說這個A'跟A不一樣,但是有什麼要神奇的地方呢?

它的神奇的地方就是,這個我其實寫錯了,我忘了改了,等我一下喔,這個B呢,其實是A',其實是A'.好,這個神奇的地方是什麼?

神奇的地方是A'它現在是一個k-1的,rank是k-1的matrix,為什麼?

因為σ塊裡面有k-1個不等於0的value,所以A'是一個rank是k-1的matrix。而這邊沒有要證明,但是是很神奇的地方就是,A'它是所有rank是k-1的matrix裡面,最接近A的那個matrix。

什麼叫做最接近?什麼叫最接近?所謂的最接近就是距離最短,什麼叫距離最短?

它的距離最短,它的距離就是剛才講的Frobenius inner product所定義出來的那個距離,我們說你要算兩個object之間的距離,你要定義inner product嘛,那我現在用Frobenius inner product當作我們的inner product,可以定義矩陣間的距離。

那A'是所有rank是k-1的matrix裡面,它的距離跟A最近的那個matrix,也就是它是最接近A的那個matrix。好,那這個東西可以拿來做什麼事情呢?

它其實就可以拿來做一張圖片的壓縮,那我們其實可以把一張圖片想成是一個MxN的matrix,假設一張圖片的解析度是比如說1024x768,那這張圖片它對應到的matrix就是高是1024,高是768,寬是1024,我想大家應該知道我的意思吧,每一個pixel就對應到一個value。

好,那今天呢,我找個板插在另外一邊,那今天假設我們有一張圖片,它的解析度是MxN,它是MxN的pixel。

那假設這張圖片是黑白的,假設它是黑白的,那這邊的matrix裡面的每一個element其實就是對應到一個pixel,而它有一個數值,這個數值呢,它就是介於,你可以做一下normalization,你可以做一下normalization,讓它介於一樣,如果是1的話,就是最黑的。

那如果0的話呢,就是白的。

好,那接下來你就可以對這個matrix做decomposition,你就可以把這個matrix做SVD,任何matrix都可以做SVD,把它拆解成MxK,然後呢,這個KxK,跟這個,我這樣畫可能不太好,KxN的三個matrix。

所以本來你要存這張圖,你需要存MxN的數值,如果你要存這張圖,你要存這張圖,你這邊需要存MxK的數值,你這邊需要存K的數值,因為不需要存這整個matrix,因為它最多就是對角線的地方有值,最多就是對角線的地方有值。

好,那這邊呢,你就只需要存N乘以K的數值,所以整體來說你現在要存的數字就是N加N,我再加1好了,N加N加1乘上K。

好,那N乘以N,跟N加N加1乘上K,它們誰比較大呢?你其實可以讓這個K非常的small這樣子,非常的小。為什麼這個K可以非常的小呢?因為這個K它是你自己決定的,它是你自己決定的。

首先,假設你不要lose任何一個matrix,假設你今天希望說這三個matrix乘起來跟原來的圖一模一樣,那你K必須要等於rank,假設這個叫A好了,它必須要等於rankA,它必須要等於rankA。

那rankA是多少呢?rankA我們知道它至少小於等於minimum的N跟N,它至少小於N跟N裡面比較小的那一個。

好,但是實際上,在實作上,你這個K可以設一個比rank還要小的數值,你可以讓你的K實際上是比rank還要小的,可以讓它實際上比rank還要小。

那為什麼讓它比rank還要小沒有關係呢?因為我們說,如果它比rank還要小,你這兩個相乘以後會變成A',A'的不等於A,但是它是跟A最接近的那一個,那代表你lose掉的資訊是最少的。

所以這個技術就可以用來做圖片的壓縮,你可以自己定這個K的數值就等於是你的壓縮率,K的數值設成越小,壓縮率就越大,然後你的lose的資訊就會越多。

好,那這邊就是我在網路上實際上找到的一個例子,左邊這個圖是原圖,然後這個圖是什麼?這個圖是K等於1的時候所做出來的結果。

你可以想一下K等於1是什麼樣的概念呢?K等於1的話,那意味著這是一個M by E的vector,中間是一個E by E的scalar,這邊是一個M by E的東西,中間它乘上一個E by E的東西,然後再乘上一個E by N的東西。

你可以想像說,這個東西它乘起來其實也是一個matrix,那這個matrix的rank是1,所以你會發現說它這邊的每一個row或每一個column,彼此之間都是其他人的一個倍數而已,只要長得是這個樣子。

這樣大家可以想像嗎?那當然跟你真實的圖片相差非常多,那左邊跟右邊這個就是把這張圖片剪掉這張圖片以後剩下來的結果,所以差很多,這邊完全看不出來像是一個人,完全看不出來跟左邊這張圖片有任何的關係。

所以你K如果設1,那雖然這個可以把圖片壓縮得很小,但是你解回來以後就會完全不知道原來是什麼東西。但是這個是一個影片,它就是從那個K由小到大,然後看看說會發生什麼樣的事情。

K越來越大,然後很快的你會發現說壓縮以後再解回來的圖片跟原來的圖片是非常像的。左下角這個值就是K,大家看到這個K就是一直增加,那現在K再增加已經沒有什麼用了,那K也不用太大。

然後你其實發現說,其實這個K真的是不用太大。比如說你看這邊是12,其實看起來還有點模糊,然後你看到28的時候,其實左邊的圖跟右邊的圖其實已經差不多大了,其實已經幾乎是一樣了。

然後兩邊這張圖相減幾乎是全黑,就代表說它們基本上是沒有什麼不同。所以你其實K不用設太大,你可以把圖片壓縮得很小,然後解回來以後跟原來的圖片看起來是非常非常像的。

那這個就是你在最後一個作業裡面我們要大家做的事情。

那最後一點時間就是我找到一首SVD的歌啦!真的啊!我看看!