Can I recover only the diagonal elements of A' * B with SVD vectors of A and B?

Asked by Xiaohan Du

Xiaohan Du (view profile)

on 28 Jun 2018
Latest activity Answered by Anton Semechko

Anton Semechko (view profile)

on 28 Jun 2018
Hi all,
Imagine I have 2 matrices A and B and I need the diagonal elements of (A' * B). If say A and B are both m*n matrices which contains column vectors as follows:
A = [a1, ..., an];
B = [b1, ..., bn];
Then the diagonal elements of (A' * B) can be calculated by the vector products of the paired vectors a1'*b1, a2'*b2, ..., an' * bn.
Now if I perform economy size SVD to A and B:
[ua, sa, va] = svd(A, 'econ');
[ub, sb, vb] = svd(B, 'econ');
Then my question is: can I calculate only the diagonal elements of (A' * B) with SVD components [ua, sa, va] and [ub, sb, vb]? Notice only the diagonal elements, none of the other elements can be computed.
My understanding is no, I can't. Because if recovering (A' * B) by the SVD components, say
A' * B = (ua1 * sa1 * va1')' * (ub1 * sb1 * vb1') + ... + (uan * san * van')' * (ubn * sbn * vbn')
then each component product
(uan * san * van')' * (ubn * sbn * vbn')
is a full m*n matrix, which only recovers part of the whole diagonal line. Summing all n full m*n matrices will recover the matrix (A' * B), but this is not cheaper than computing (A' * B), because it involves computation of all elements of (A' * B). So if SVD is involved, there is no efficient way of getting diagonal elements of (A' * B) by only computing the diagonal elements.
I don't know if I'm right, and please excuse me if it's not so clear.
Many thanks!

Tags

Answer by Anton Semechko

Anton Semechko (view profile)

on 28 Jun 2018

i-th diagonal of A'*B equals dot product of the i-th columns of A and B. Here is a demo showing how to recover only the diagonals of A'*B using SVDs of A and B:
% Generate two M-by-N matrices
M=100;
N=100;
A=randn(M,N);
B=randn(M,N);
% Get SVDs
[Ua,Da,Va]=svd(A,0);
[Ub,Db,Vb]=svd(B,0);
% Pre-multiply D and V'
Va=Da*Va';
Vb=Db*Vb';
% Get diagonal entries of C=A'*B; i-th diagonal element = dot product between i-th columns of A and B
C_diag=zeros(N,1);
for n=1:N
A_n=Ua*Va(:,n); % n-th column of A <--> n-th row of transpose(A)
B_n=Ub*Vb(:,n); % n-th column of B
C_diag(n)=A_n'*B_n;
end
% Verify computed solution
C_diag_ref=diag(A'*B);
E_max=max(abs(C_diag-C_diag_ref));
fprintf('Maximum absolute error: %.10E\n',E_max)
When using this approach, over 100 runs, I got maximum and mean errors of 1.59872115546023e-13 and 1.02029495963052e-13, respectively.