How can I calculate the frobenius norm piecewise on matrix product?

I want to calculate norm(A*B - C*C,'fro')

A and B are huge but thin factor matrices (1000000 x 20 and 20 * 1000000). C (1000000 x 2000000)is a huge sparse matrix but C * C isn't sparse. A*B and C*C result in memory errors.

How can I calculate the frobeniusnorm without calculating the product explicitly? I guess I have to calculate the norm piecewise but how can I do this in matlab?

[Roger Stafford]

Don't you mean norm(A*B - C*C','fro')? C*C is not valid with C a non-square matrix..

[Steffen]

Yes, I meant C*C'. Sorry for the confusion.

[Matt J]

What about C'*C? Can you compute that without memory errors?

[Steffen]

Nope, I can't compute C' * C without a memory error.

Answer 1

[Matt J]

If you can compute C'*C without memory errors

    FrobeniusNorm= sqrt( trace((A'*A)*(B*B')) + norm(C'*C,'fro')^2 ...
                        -2*trace((A'*C)*(B*C)'))

[Matt J]

Nope, I can't compute C' * C without a memory error.

You can still use the above expression, but in place of norm(C'*C,'fro'), you will have to do, e.g.,

 Ccell=mat2tiles(C',[inf,2000]); %see link

 frob=@(q) norm(q,'fro');

 secondterm=frob(cellfun(@(z)frob(C*z), Ccell));

where MAT2TILES is available here.

[Matt J]

...and then do

FrobeniusNorm= sqrt( trace((A'*A)*(B*B')) + secondterm^2 ...
                    -2*trace((A'*C)*(B*C)'))