信息检索与数据挖掘 2019年4月9日 20 低秩逼近 给定M×N的矩阵C及正整数k,我们想寻找一个 秩不高于k的M×N的矩阵Ck,使得两个矩阵的差 X=C-Ck的F范数(Frobenius Norm,弗罗宾尼其 范数)最小，即下式最小： M N IXI ·因此，X的F范数度量了Ck和C之间的差异程度。 我们的目标是找到一个矩阵C,会使得这种差异极 小化，同时又要限制Ck的秩不高于k。如果r是C 的秩，那么很显然C,=C,此时矩阵差值的F范数为 0。当k比r小得多时，我们称Ck为低秩逼近(low- rank approximation)矩阵
信息检索与数据挖掘 2019年4月9日 20 低秩逼近 • 给定M × N 的矩阵C 及正整数k，我们想寻找一个 秩不高于k 的M × N 的矩阵Ck，使得两个矩阵的差 X = C − Ck 的F范数（Frobenius Norm，弗罗宾尼其 范数）最小，即下式最小： • 因此，X 的F范数度量了Ck 和C 之间的差异程度。 我们的目标是找到一个矩阵Ck，会使得这种差异极 小化，同时又要限制Ck 的秩不高于k。如果r 是C 的秩，那么很显然Cr =C，此时矩阵差值的F范数为 0。当k 比r 小得多时，我们称Ck 为低秩逼近（lowrank approximation）矩阵
信息检索与数据挖掘 2019年4月9日 21 SVD用于矩阵的低秩逼近 ·进行如下三步操作： (1)给定C,构造SVD分解，因此C=UU∑VT; ·(2)把∑对角线上r-k个最小奇异值置为0，得到Σ： (3)计算Ck=U∑r作为C的逼近。 ·由于∑最多包含k个非零元素，所以C的秩不高 于k。将这些小特征值替换成0将不会对最后的乘 积有实质性影响，也就是说该乘积接近C。 Eckart及Young给出的定理将会告诉我们，上述过程产生了 一个秩为k的矩阵，它的F-范数误差最小
信息检索与数据挖掘 2019年4月9日 21 SVD 用于矩阵的低秩逼近 • 进行如下三步操作： • (1) 给定C，构造SVD 分解，因此C = UΣVT； • (2) 把Σ对角线上r-k 个最小奇异值置为0，得到Σk； • (3) 计算Ck = UΣkVT 作为C 的逼近。 • 由于 Σk 最多包含k 个非零元素，所以Ck 的秩不高 于k。将这些小特征值替换成0 将不会对最后的乘 积有实质性影响，也就是说该乘积接近C。 Eckart 及Young 给出的定理将会告诉我们，上述过程产生了 一个秩为k 的矩阵，它的F−范数误差最小
信息检索与数据挖掘 2019年4月9日 22 SVD用于图像压缩 20 15 10 10 15 20 A 24*24 image Rank 3 approximation Rank 5 approximation 01 0 A=[u1ukuk+1um Ok 0 0 http://www.math.umn.edu/-lerman/math5467/svd.pdf
信息检索与数据挖掘 2019年4月9日 22 SVD用于图像压缩 A 24*24 image Rank 3 approximation Rank 5 approximation http://www.math.umn.edu/~lerman/math5467/svd.pdf
信息检索与数据挖掘 2019年4月9日 23 375 entries in the matrix SVD用于图像压缩 an array of 15*25 black or white pixels 01=14.72 02=5.22 03=3.31 represent the data in a more compact form M=U 01 ViT u202 V2T u303 V3T This means that we have three vectors vi,each of which has 15 entries,three vectors ui,each of which has 25 entries,and three singular values o:.This implies that we may represent the matrix using only 123 numbers rather than the 375 that appear in the matrix.In this way,the singular value decomposition discovers the redundancy in the matrix and provides a format for eliminating it. http://www.ams.org/samplings/feature-column/fcarc-svd
信息检索与数据挖掘 2019年4月9日 23 SVD用于图像压缩 an array of 15*25 black or white pixels represent the data in a more compact form 375 entries in the matrix M=u1σ1 v1 T + u2σ2 v2 T + u3σ3 v3 T σ1 = 14.72 σ2 = 5.22 σ3 = 3.31 This means that we have three vectors vi , each of which has 15 entries, three vectors ui , each of which has 25 entries, and three singular values σi . This implies that we may represent the matrix using only 123 numbers rather than the 375 that appear in the matrix. In this way, the singular value decomposition discovers the redundancy in the matrix and provides a format for eliminating it. http://www.ams.org/samplings/feature-column/fcarc-svd
信息检索与数据挖掘 2019年4月9日 24 SVD用于图像去噪 Noisy image Improved image 01=14.15 02=4.67 03=3.00 04=0.21 05=0.19 016=0.05 M=U01 ViT U202 V2T u303 V3T http://www.ams.org/samplings/feature-column/fcarc-svd
信息检索与数据挖掘 2019年4月9日 24 SVD用于图像去噪 σ1 = 14.15 σ2 = 4.67 σ3 = 3.00 σ4 = 0.21 σ5 = 0.19 ... σ15 = 0.05 M=u1σ1 v1 T + u2σ2 v2 T + u3σ3 v3 T http://www.ams.org/samplings/feature-column/fcarc-svd