Divide and conquer SVD algorithm

Duc Anh Le

2020 3 31

0 个回答

5 次查看（30 天）

0 个投票

I'm trying to implement Divide and Conquer SVD, but my code is not working. Can somebody help me fix it? Thanks.

EDIT: Note that here B is an upper bidigonal matrix.

function [U,S,V] = DivideConquer_SVD(B)
[m,n] = size(B);
k = floor(m/2);
if k == 0
    U = 1;
    V = 1;
    S = B;
    return;
else
    % Divide the input matrix
    alpha = B(k,k);
    beta = B(k,k+1);
    e1 = zeros(m,1);
    e2 = zeros(m,1);
    e1(k) = 1;
    e2(k+1) = 1;
    B1 = B(1:k-1,1:k);
    B2 = B(k+1:m,k+1:m);
    %recursive computations
    [U1,S1,V1] = DivideConquer_SVD(B1);
    [U2,S2,V2] = DivideConquer_SVD(B2);
    U_bar = zeros(m);
    U_bar(1:k-1,1:k-1) = U1;
    U_bar(k,k) = 1;
    U_bar((k+1):m,(k+1):m) = U2;
    D = zeros(m);
    D(1:k-1,1:k) = S1;
    D((k+1):m,(k+1):m) = S2;
    V_bar = zeros(m);
    V_bar(1:k,1:k) = V1;
    V_bar((k+1):m,(k+1):m) = V2;
    u = alpha*e1'*V_bar + beta*e2'*V_bar;
    u = u';
    D_tilde = D*D + u*u';
    % compute eigenvalues and eigenvectors of D^2+uu'
    [L1,Q1] = eig(D_tilde);
    eigs = diag(L1);
    S = zeros(m,n)
    S(1:(m+1):end) = eigs
    U_tilde = Q1;
    V_tilde = Q1;
    %Compute eigenvectors of the original input matrix T
    U = U_bar*U_tilde;
    V = V_bar*V_tilde;
    return;
end