假设我有一个秩为3的矩阵3x3A。
我想创建一个秩为2的矩阵,它最接近${l}{2}$/frobenius范数中的a。
我们把这个矩阵称为f。
很容易通过svd实现,即如果$a=u s{v}^{h}$通过svd分解$f=u\hat{s}{v}^{h}$。
其中$\hat{s}$与最后一个单数值为零的$s$相同。
问题是,除了使用svd分解外,是否有一种计算量较小的方法来创建f?
谢谢。
最佳答案
如果你知道矩阵是秩3,那么3个householder变换就足以将nxm矩阵降为3xm矩阵。现在可以很容易地将其转化为特征值问题。计算特征多项式。例如,考虑这个矩阵(我将使用Matlab完成这项工作):
>> A = rand(10,3);
>> B = A*rand(3,6);
很明显,B的排名是3,但如果你不相信我,Rank会证实这一说法。
>> rank(B)
ans =
3
>> size(B)
ans =
10 6
所以b是一个10x6矩阵,秩为3。SVD也证实了这一事实。
>> svd(B)
ans =
6.95958965358531
1.05904552889497
0.505730235622534
7.37626877572817e-16
2.36322066654691e-16
1.06396598411356e-16
我觉得太懒了,写不出户主的转变。(我有一些代码,但是……)所以我会用二维码来帮我。
>> [Q,R] = qr(B,0);
>> C = Q(:,1:3)'*B
C =
-2.0815 -1.7098 -3.7897 -1.6186 -3.6038 -3.0809
0.0000 0.91329 0.78347 0.44597 -0.072369 0.54196
0.0000 0.0000 -0.2285 -0.43721 -0.85949 -0.41072
这里的乘法显示了我们在三次户主转换后所看到的情况。如我们所料,它是上三角的。接下来,计算特征多项式。我在这里用我自己的工具,象征性地说,但计算只是一点代数。
>> sympoly lambda
>> det(C*C' - lambda*eye(3))
ans =
13.8942 + 66.9996*lambda + 49.8132*lambda^2 + lambda^3
>> P = det(C*C' - lambda*eye(3))
P =
13.8942 - 66.9996*lambda + 49.8132*lambda^2 - lambda^3
p的根是什么,那么c*c'的特征值是什么?
>> r = roots(P)
r =
48.436
1.1216
0.25576
我们知道这里的特征值必须是奇异值的平方,所以这里的一个很好的测试是看我们是否恢复了svd发现的singlular值。所以再次扩展显示格式,我们看到它做得很好。
>> sqrt(roots(P))
ans =
6.95958965358531
1.05904552889497
0.505730235622533
数学在起作用的时候是很有趣的。我们如何处理这些信息?如果我知道一个特定的特征值,我可以计算相应的特征向量。本质上,我们需要解线性3x3齐次方程组
(C*C' - eye(3)*r(3)) * X = 0
再说一次,我会懒得在这里找到解决方案,而不实际编写任何代码。不过,高斯消去法可以做到这一点。
>> V = null((C*C' - eye(3)*r(3)))
V =
-0.171504758161731
-0.389921448437349
0.904736084157367
所以我们得到了v,一个c*c'的特征向量。我们可以通过下面的SVD电话来说服自己。
>> svd(C - V*(V'*C))
ans =
6.9595896535853
1.05904552889497
2.88098729108798e-16
所以通过在v方向上减去c的分量,我们得到一个秩2矩阵。
类似地,我们可以将v变换成原始问题空间,并用它通过b的秩一更新来变换矩阵b,我们的原始矩阵。
>> U = Q(:,1:3)*V;
>> D = B - U*(U'*B);
D的级别是多少?
>> svd(D)
ans =
6.95958965358531
1.05904552889497
2.62044567948618e-15
3.18063391331806e-16
2.16520878207897e-16
1.56387805987859e-16
>> rank(D)
ans =
2
正如你所看到的,尽管我做了很多数学工作,调用svd、qr、rank等,但所有这些都是多次的,最后,实际的计算相对来说是微不足道的。我只需要…
3个住户改造。(保存以备日后使用。注意,householder转换只是矩阵的秩一更新。)
计算特征多项式。
用你最喜欢的方法计算三次多项式的最小根。
恢复相应的特征向量。高斯消去在这里就足够了。
使用我们最初做的householder变换将特征向量返回到原始空间。
矩阵的一级更新。
所有这些计算步骤对于任何尺寸的矩阵都是快速有效的,只要我们知道实际的秩是3。甚至连一篇关于这个问题的论文都不值。
编辑:
由于问题已经被修正,使得矩阵本身只有3x3大小,所以计算更为简单。不过,我将按原样离开本文的第一部分,因为它描述了任何大小的秩为3的一般矩阵的完全有效的解。
如果你的目标是消除3x3矩阵的最后一个奇异值,那么3x3上的svd看起来是非常有效的。通过间接方法生成最后一个奇异值也会有一些精度损失。例如,在这里比较svd计算的最小奇异值,然后使用特征值。所以在这里你可能会看到一些小的错误,因为形成一个“*a将导致一些精度。这种损失的程度可能取决于a的条件数。
>> A = rand(3);
>> sqrt(eig(A'*A))
ans =
0.0138948003095069
0.080275195586312
1.50987693453097
>> svd(A)
ans =
1.50987693453097
0.0802751955863124
0.0138948003095054
但是,如果你真的想自己做这项工作,你可以做。
直接从3x3矩阵a'*a计算特征多项式。
计算三次多项式的根。选择最小的根。
生成相应的特征向量。
对A进行一级更新,去掉A中位于特征向量方向的部分。
这是否比简单地调用svd,然后进行秩一更新更简单或计算效率更低?我一点也不确定3x3是否值得。一个3x3的svd真的是非常快的计算。
关于performance - 下秩矩阵的计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9172648/