MATLAB中的高效低阶应用

Question

我想计算一个矩阵的低秩近似,这在Frobenius范数下是最优的.这样做的简单方法是计算矩阵的SVD分解,将最小的奇异值设置为零,并通过乘以因子来计算低秩矩阵.在MATLAB中有一种简单而有效的方法吗？

Answer 1

如果您的矩阵稀疏,请使用svds.

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

从教程:

最佳的低秩近似可以使用的SVD来容易地计算阿在O(MN ^ 2) .使用随机投影,我们展示了如何在O(mn log(n))中实现"几乎最优"的低秩pproximation .

来自博客的 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;

另外,请记住econ参数svd.

Answer 2

您可以使用该svds函数快速计算基于SVD的低秩近似值.

[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

使用大小n平方矩阵,k奇异/特征值和运行时间(秒).我使用Steve Eddins的timeit文件交换功能进行基准测试,试图考虑开销和运行时变化.

svdseigs如果你想要一个非常大的矩阵中的一些值,它们会更快.它还取决于所讨论的矩阵的属性(edit svds应该给你一些想法).