c - 矩阵 mul 最大值估计

Question

给定矩阵乘积C = A*B，有没有N^2办法估计 C 中的最大值？或者更确切地说，这样做的好方法是什么？

Answer 1

这个怎么样：

1. 对于 中的每一行A和 中的每一列B，求向量范数的平方（即平方和）。 O(n^2)
2. 对于行 fromA和列 from的每个组合B，乘以相应的向量范数平方。 O(n^2)
3. 找出其中的最大值。 O(n^2)

它的平方根将是 的上限max(abs(C))。为什么？因为，根据Cauchy-Schwartz 不等式，我们知道|<x,y>|^2 <= <x,x>.<y,y>，其中<>表示内积。我们已经为 中的每个点计算了这种关系的 RHS C；因此，我们知道C（LHS）的相应元素必须更少。

免责声明：很可能有一种方法可以提供更严格的界限；这是首先想到的。

Answer 2

明显地，

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

是一个上限（因为 C 的每个元素都是来自 A 和 B 的两个值的 N 个乘积之和）。

Answer 3

这是我的看法：

A,B,C

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

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

你认为呢？将尝试 Oli 的答案，看看是什么给了我最好的近似值/性能。