矩阵mul最大值估计

Question

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

Answer 1

这个怎么样:

1. 对于在每一行A和每一列中B,找到矢量范数的平方(即,平方和). 为O(n ^ 2)
2. 对于row from A和column from的每个组合B,乘以相应的vector-norm平方. 为O(n ^ 2)
3. 找到这些中的最大值. 为O(n ^ 2)

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

免责声明:可能有一种方法可以给予更严格的约束; 这是我想到的第一件事.