Эффективная аппроксимация низкого ранга в MATLAB - PullRequest
Новая
       2

Эффективная аппроксимация низкого ранга в MATLAB

8 голосов
/ 09 января 2012

Я бы хотел вычислить аппроксимацию низкого ранга для матрицы, которая является оптимальной по норме Фробениуса.Тривиальный способ сделать это состоит в том, чтобы вычислить декомпозицию матрицы SVD, установить наименьшее единичное значение в ноль и вычислить матрицу низкого ранга путем умножения коэффициентов.Есть ли простой и более эффективный способ сделать это в MATLAB?

Ответы [ 2 ]

6 голосов
/ 10 января 2012

Если ваша матрица разрежена, используйте svds.

Предполагая, что она не разреженная, но большая, вы можете использовать случайные проекции для быстрого приближения низкого ранга.

Из учебное пособие :

Оптимальное приближение низкого ранга можно легко рассчитать с использованием SVD A в O (mn ^ 2) .Используя случайные проекции, мы показываем, как достичь «почти оптимального» pproximation низкого ранга в O (mn log (n)) .

код 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.

5 голосов
/ 10 января 2012

Вы можете быстро вычислить аппроксимацию низкого ранга на основе SVD, используя функцию 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

С размером - n квадратными матрицами, k единичные / собственные значения и время выполнения в секундах. Я использовал функцию обмена файлами Steve Eddins timeit для бенчмаркинга, которая пытается учесть изменения накладных расходов и времени выполнения.

svds и eigs быстрее, если вы хотите получить несколько значений из очень большой матрицы. Это также зависит от свойств рассматриваемой матрицы (edit svds должно дать вам некоторое представление о том, почему).

...