在MATLAB中进行有效的低秩逼近 [英] Efficient low-rank appoximation in MATLAB

问题描述

我想计算在Frobenius范数下最优的矩阵的低秩近似.实现此目的的简单方法是计算矩阵的SVD分解，将最小的奇异值设置为零，并通过乘以因子来计算低阶矩阵.在MATLAB中有一种简单且有效的方法吗?

I'd like to compute a low-rank approximation to a matrix which is optimal under the Frobenius norm. The trivial way to do this is to compute the SVD decomposition of the matrix, set the smallest singular values to zero and compute the low-rank matrix by multiplying the factors. Is there a simple and more efficient way to do this in MATLAB?

推荐答案

如果矩阵稀疏，请使用svds.

If your matrix is sparse, use svds.

假设它不是稀疏的而是很大的，则可以使用随机投影进行快速的低秩逼近.

Assuming it is not sparse but it's large, you can use random projections for fast low-rank approximation.

通过教程:

使用 O(mn ^ 2)中的 A 的SVD可以轻松地计算出最优的低秩逼近 ).使用随机投影，我们展示了如何在 O(mn log(n)) 中实现几乎最佳"的低秩近似.

An optimal low rank approximation can be easily computed using the SVD of A in O(mn^2 ). Using random projections we show how to achieve an "almost optimal" low rank pproximation in O(mn log(n)).

来自博客的Matlab代码:

Matlab code from a blog:

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参数.

这篇关于在MATLAB中进行有效的低秩逼近的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！