matrix mul max value estimate

Question

Given matrix product C = A*B, is there N^2 way to estimate max value in C? Or rather what is a good way to do so?

Answer 1

How about this:

1. For each row in A and each column in B, find the vector-norm squared (i.e. sum of squares). O(n^2)
2. For each combination of row from A and column from B, multiply the corresponding vector-norm squareds. O(n^2)
3. Find the maximum of these. O(n^2)

The square-root of this will be an upper-bound for max(abs(C)). Why? Because, from the Cauchy-Schwartz inequality, we know that |<x,y>|^2 <= <x,x>.<y,y>, where <> denotes the inner-product. We have calculated the RHS of this relationship for each point in C; we therefore know that the corresponding element of C (the LHS) must be less.

Disclaimer: There may well be a method to give a tighter bound; this was the first thing that came to mind.

Answer 2

Obviously,

N * max(abs(A)) * max(abs(B))

is an upper bound (since each element of C is the sum of N products of two values from A and B).

Answer 3

this is my take:

A,B,C

a(i) = max(abs(A(i,:)))
b(j) = max(abs(B(j,:)))

c(i,j) = N*max(a(i)*b(j))

What you think? Gonna try Oli's answer and see what gives me best approximation/performance.