матричная оценка муль макс значения

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) * ** тысяча двадцать два ** тысячи двадцать-три 1024 *

Квадратный корень этого будет верхней границей для max(abs(C)). Зачем? Потому что из неравенства Коши-Шварца мы знаем, что |<x,y>|^2 <= <x,x>.<y,y>, где <> обозначает внутренний продукт. Мы вычислили RHS этого отношения для каждой точки в C; поэтому мы знаем, что соответствующий элемент C (LHS) должен быть меньше.

Отказ от ответственности: Вполне может быть, что метод дает более жесткую оценку; это было первое, что пришло в голову.

Answer 2

Очевидно,

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

является верхней границей (поскольку каждый элемент C является суммой N произведений двух значений из A и B).

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))

Что ты думаешь? Попробую ответ Оли и посмотрим, что дает мне лучшее приближение / производительность.