矩阵乘最大值估计

Question

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

Answer 1

怎么样：

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

其平方根将是 max(abs(C)) 的上限。为什么？因为，根据 Cauchy-Schwartz 不等式，我们知道 ||^2 <=.，其中 <> 表示内积。我们已经在C中计算了每个点的这种关系的RHS；因此我们知道 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))

你觉得怎么样？要尝试奥利的答案，看看什么给了我最好的近似/性能。