MATLAB中的高效低秩逼近

Question

我想计算一个在Frobenius范数下最优的矩阵的低秩近似值。实现这一点的简单方法是计算矩阵的SVD分解，将最小奇异值设置为零，并通过乘以因子来计算低秩矩阵。在MATLAB中有没有一种更简单、更有效的方法来做到这一点？

Answer 1

如果您的矩阵是稀疏的，请使用svds。

假设它不是稀疏的，但它很大，你可以使用随机投影进行快速的低秩近似。

从tutorial

利用A在O(mn^2 )中的奇异值分解(

)可以很容易地计算出最优的低秩近似。使用随机投影，我们展示了如何在O(mn log(n))中实现“几乎最优”的低阶近似。

来自blog的Matlab代码

clear
% preparing the problem
% trying to find a low approximation to A, an m x n matrix
% where m >= n
m = 1000;
n = 900;
%// first let's produce example A
A = rand(m,n);
%
% beginning of the algorithm designed to find alow rank matrix of A
% let us define that rank to be equal to k
k = 50;
% R is an m x l matrix drawn from a N(0,1)
% where l is such that l > c log(n)/ epsilon^2
%
l = 100;
% timing the random algorithm
trand =cputime;
R = randn(m,l);
B = 1/sqrt(l)* R' * A;
[a,s,b]=svd(B);
Ak = A*b(:,1:k)*b(:,1:k)';
trandend = cputime-trand;
% now timing the normal SVD algorithm
tsvd = cputime;
% doing it the normal SVD way
[U,S,V] = svd(A,0);
Aksvd= U(1:m,1:k)*S(1:k,1:k)*V(1:n,1:k)';
tsvdend = cputime -tsvd;

另外，请记住svd的econ参数。

Answer 2

您可以使用svds函数基于奇异值分解快速计算低阶近似值。

[U,S,V] = svds(A,r); %# only first r singular values are computed

svds使用eigs来计算奇异值的子集-对于大型稀疏矩阵，它将特别快。请参阅文档；您可以设置公差和最大迭代次数，或者选择计算小的奇异值而不是大的奇异值。

我认为对于密集矩阵，svds和eigs可能比svd和eig更快，但后来我做了一些基准测试。只有当请求足够少的值时，它们才能更快地处理大型矩阵：

 n     k       svds          svd         eigs          eig            comment
10     1     4.6941e-03   8.8188e-05   2.8311e-03   7.1699e-05    random matrices
100    1     8.9591e-03   7.5931e-03   4.7711e-03   1.5964e-02     (uniform dist)
1000   1     3.6464e-01   1.8024e+00   3.9019e-02   3.4057e+00
       2     1.7184e+00   1.8302e+00   2.3294e+00   3.4592e+00
       3     1.4665e+00   1.8429e+00   2.3943e+00   3.5064e+00
       4     1.5920e+00   1.8208e+00   1.0100e+00   3.4189e+00
4000   1     7.5255e+00   8.5846e+01   5.1709e-01   1.2287e+02
       2     3.8368e+01   8.6006e+01   1.0966e+02   1.2243e+02
       3     4.1639e+01   8.4399e+01   6.0963e+01   1.2297e+02
       4     4.2523e+01   8.4211e+01   8.3964e+01   1.2251e+02


10     1      4.4501e-03   1.2028e-04   2.8001e-03   8.0108e-05   random pos. def.
100    1      3.0927e-02   7.1261e-03   1.7364e-02   1.2342e-02    (uniform dist)
1000   1      3.3647e+00   1.8096e+00   4.5111e-01   3.2644e+00
       2      4.2939e+00   1.8379e+00   2.6098e+00   3.4405e+00
       3      4.3249e+00   1.8245e+00   6.9845e-01   3.7606e+00
       4      3.1962e+00   1.9782e+00   7.8082e-01   3.3626e+00
4000   1      1.4272e+02   8.5545e+01   1.1795e+01   1.4214e+02
       2      1.7096e+02   8.4905e+01   1.0411e+02   1.4322e+02
       3      2.7061e+02   8.5045e+01   4.6654e+01   1.4283e+02
       4      1.7161e+02   8.5358e+01   3.0066e+01   1.4262e+02

使用size-n方阵，k奇异值/特征值和运行时间以秒为单位。我使用Steve Eddins的timeit文件交换函数进行基准测试，该函数尝试考虑开销和运行时变化。

如果你想从一个非常大的矩阵中得到几个值，svds和eigs会更快。它还取决于有问题的矩阵的属性(edit svds应该会告诉您一些原因)。