MATLAB: How to calculate trace(A’ * B) using SVD vectors of A and B

diagonalmemorysvdtrace

Hi all,
Imagine I have 2 large matrices which have more rows than columns, I'd like to calculate trace(A' * B) for N times. I have 2 options: 1. calculate trace(A' * B) directly; 2. only calculate vector product of the diagonal, then sum it. I test with the following minimum example, it turns out the 2nd option is faster:
clear; clc;
nd = 100000;
nt = 500;
A = rand(nd, nt);
B = rand(nd, nt);
N = 100;
%%no SVD.
% option 1.
tic
for i = 1:N
    abTr = trace(A' * B);
end
toc
% option 2.
tic
abSum = 0;
for i = 1:N
    for j = 1:nt
        abSum = abSum + A(:, j)' * B(:, j);
    end
end
toc
Elapsed time is 58.320345 seconds.
Elapsed time is 13.558039 seconds.
Now I need to apply truncated-SVD to A and B to optimise storage. the following code is applied to leave only 10 vectors
% apply svd  
[ua, sa, va] = svd(A, 'econ'); 
[ub, sb, vb] = svd(B, 'econ');
% group in cells
nRem = 10;
ucell = {ua va ub vb};
scell = {sa sb};
% truncate
ucell = cellfun(@(v) v(:, 1:nRem), ucell, 'un', 0);
scell = cellfun(@(v) v(1:nRem, 1:nRem), scell, 'un', 0);
My question is: is it possible to calculate trace (it's an approximation due to truncation) using option 2 with these SVD vectors in ucell and singular values in scell? I can do it with option 1 using
trace((vb' * va * sa' * (ua' * ub) * sb)
But I'd like to be faster by only considering diagonal elements.
Many thanks!

Best Answer

I am not aware of any identities that can express trace(A'*B) in terms of SVDs of A and B, and I dont think one exists, but there is an identity that does not require explicit calculation of the A'*B matrix:
 trace(A'*B) = sum(A(:).*B(:))
For example,
 nd = 100000;
 nt = 500;
 A = rand(nd, nt);
 B = rand(nd, nt);
 N = 100;
 tic
 tr1=trace(A'*B);
 t1=toc;
 %Elapsed time is 0.857053 seconds.
 tic 
 t2=sum(A(:).*B(:));
 toc
 %Elapsed time is 0.210807 seconds.
As you can see, you obtain the result about 4 times faster when using the above identity. This identity is especially useful when nt is 'large', because the machine may not have insufficient memory to hold the nt-by-nt matrix A'*B.
Related Question