c - 行列の最大値の見積もり

Question

与えられた行列積、 Cの最大値を推定する方法C = A*Bはありますか？N^2というか、そうするための良い方法は何ですか？

Answer 1

これはどう：

1. の各行Aとの各列についてB、ベクトルノルムの2乗（つまり、2乗の合計）を求めます。 O（n ^ 2）
2. A行fromと列fromの組み合わせごとにB、対応するベクトルノルムの2乗を乗算します。 O（n ^ 2）
3. これらの最大値を見つけます。 O（n ^ 2）

これの平方根は、の上限になりmax(abs(C))ます。なんで？なぜなら、コーシー・シュワルツの不等式から、、は内積を表すこと|<x,y>|^2 <= <x,x>.<y,y>がわかっているからです。<>の各ポイントについて、この関係のRHSを計算しましたC。Cしたがって、 （LHS）の対応する要素は小さくなければならないことがわかります。

免責事項：より緊密な境界を与える方法があるかもしれません。これが最初に頭に浮かんだことでした。

Answer 2

明らかに、

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

は上限です（Cの各要素はAとBの2つの値の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の答えを試して、何が私に最高の近似/パフォーマンスを与えるかを見てみましょう。