Итеративный «решатель» для

9

Я не могу себе представить, что я первый думаю о следующей проблеме, поэтому я буду удовлетворен ссылкой (но всегда приветствуется полный, подробный ответ):

Скажем, у вас есть симметричная положительно определенная . считается очень большим, поэтому удержание в памяти невозможно. Однако вы можете оценить для любого . Учитывая, что , вы хотели бы найти .ΣRn×nnΣΣxxRnxRnxtΣ1x

Первое решение, которое приходит на ум, - это найти используя, скажем, сопряженные градиенты. Однако это кажется несколько расточительным - вы ищете скаляр, и в процессе вы обнаруживаете гигантский вектор в . Кажется, имеет больше смысла придумать метод вычисления скаляра напрямую (т.е. без прохождения ). Я ищу такой метод.Σ1xRnΣ1x

Яир Даон
источник
2
Ваша матрица возникает из для некоторого "короткого и широкого" прямоугольника ? Σ=ATAA
GeoMatt22
@ GeoMatt22 к сожалению нет. Но скажем так: что бы вы предложили в этом случае?
Яир Даон
1
Я просто подумал, есть ли какая-нибудь матрица меньшего размера для работы ... не уверен, что она все равно поможет. Вы пробовали прибегать к помощи "матрицы без расстояния махаланобисов" или подобного? Извините, что не могу помочь!
GeoMatt22
Спасибо @ GeoMatt22, я не смог ничего найти в Интернете.
Яир Даон

Ответы:

2

Я не думаю, что слышал о каком-либо методе, который делает то, что вы хотите, без фактического решения .y=Σ1x

Единственная альтернатива, которую я могу предложить, - это если вы знали что-то о собственных векторах и -значениях . Скажем, вы знали, что они , тогда вы можете представить где столбцы - это , а - диагональная матрица с собственными значениями на диагонали. Следовательно, у вас есть это и вы получаете это Это, конечно , может потребовать от вас , чтобы сохранить все собственные значения, то есть, полный матрицу . Но, если вам случится знать, что только некоторые из собственных значенийΣλi,viΣ=VTLVVviLΣ1=VTL1V

xTΣ1x=xTVTL1Vx=iλi1(viTx)2.
VΣ маленькие, скажем, первые , а остальные настолько велики, что вы можете пренебречь всеми терминами с помощью для , тогда вы можете приблизить Это требует только от вас сохранения векторов вместо всех собственных векторов.mλi1i>m
xTΣ1x=i=1nλi1(viTx)2i=1mλi1(viTx)2.
mn

Конечно, на практике часто одинаково или более сложно вычислить собственные значения и собственные векторы по сравнению с простым решением несколько раз.y=Σ1x

Вольфганг Бангерт
источник
Но тогда у вас остается задача найти наименьших собственных значений матрицы, что является непростой задачей ...m
Яир Даон
Правильный. Но, возможно, оно того стоит, если вам нужно много раз оценить . xTΣ1x
Вольфганг Бангерт
Можете ли вы предложить метод тогда?
Яир Даон
Есть много или разреженные решатели собственных значений вокруг. ARPACK и SLEPc на основе PETSc, вероятно, являются наиболее широко используемыми.
Вольфганг Бангерт
Bangreth Спасибо за ссылку. Я проверил SLEPc (хотя и не очень тщательно), и кажется, что способ поиска собственных пар - это (возможно, модифицированная) итерация Ланцоша. Если один ищет малейшие собственных пар, один должен найти и хранить все в памяти собственных пар. Это обычно невозможно для задач без матрицы - для этого требуется столько же памяти, сколько для хранения матрицы . Если кто-то хочет использовать обратную итерацию - не гарантируется порядок найденной собственной пары. Я что-то пропустил? mn×n
Яир Даон