c - 矩阵乘法最大值估计

Question

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

Answer 1

这个怎么样:

1. 对于 A 中的每一行和 B 中的每一列, 找到 vector 范数的平方(即平方和)。 O(n^2)
2. 对于来自 A 的行的每个组合和来自 B 的专栏, 乘以相应的 vector 范数平方。 O(n^2)
3. 找出其中的最大值。 O(n^2)

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

免责声明:很可能有一种方法可以给出更严格的界限；这是我想到的第一件事。