Search code examples
cmatrixnumerical-analysis

matrix mul max value estimate

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?

Solution

  • 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.