Как вычислить ортонормированный базис для прямоугольной матрицы с недостаточным рангом

Я делаю проект, который должен вычислить ортонормированный базис прямоугольной матрицы, и эта матрица может иметь или не иметь ранг. В Matlab мы можем просто вызвать функцию orth(), которая основана на svd, чтобы справиться с этой проблемой, но мне нужно реализовать ее на C. Я пытался использовать Gram-Schmidt, и он хорошо работает, когда матрица имеет полный ранг. Есть ли какая-нибудь библиотека на C, которая может решить эту проблему? Или какие-нибудь подсказки по реализации на C? Большое спасибо.


rank orthogonal
person Jin Yan    schedule 01.07.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Когда матрица имеет ранг на k (например, если матрица 4x3 имеет ранг 2, тогда k=1), вам нужно сгенерировать k случайных векторов, а затем вычесть компоненты других ортонормированных векторов, ранее сгенерированных Gram- Шмидта из случайных векторов.

Генерировать векторы необходимо самостоятельно, как вы можете видеть на следующем примере:

Матрица 2x2

1 1
0 0

По Граму-Шмидту вы получите

1 0
0 0

Это связано с тем, что исходное пространство столбца содержит только одно направление. Когда вы обнаружите такой случай (norm(v2) < eps, где eps — достаточно маленькое число с плавающей запятой, например 1e-10), сгенерируйте случайный вектор для второго вектора v2, скажем

1  0.2
0 -0.3

вычесть компонент v1

1  0
0 -0.3

и нормализовать текущий v2

1  0
0  1

Таким образом, вы можете построить направления, которых нет в исходном пространстве столбцов.

Обратите внимание, что если вас беспокоит скорость вычислений, на данном этапе или в рабочем коде следует по возможности избегать использования SVD. Хотя SVD и матрично-матричное произведение имеют сложность O (N ^ 3), SVD обычно имеет коэффициент, который более чем в 10 раз медленнее по сравнению с матрично-матричным произведением. На самом деле, в такой задаче SVD может быть полезен в вашем исследовании, но лучшим инструментом должна быть QR-разложение, которая по сути является Грам-Шидтом, но в другом порядке операций для лучшей численной стабильности.

person Yo Hsiao    schedule 20.07.2013
comment
Большое спасибо. Я пробовал Modified Gram-Schmidt, но разные eps давали мне разные ответы, которые не были стабильными. Как вы думаете, было бы лучше QR с указанием ранга? - person Jin Yan; 21.07.2013
comment
Я думаю, будет ли ваша матрица дефицитной по рангу, зависит от того, какой eps вы выберете. То есть, когда вы выполняете Грам-Шмидт на матрице A и встречаете некоторый вектор-столбец, норма которого после вычитания Грама-Шмидта меньше eps, вы говорите, что матрица A не имеет полного ранга. Другими словами, выбор eps меняет ваше определение полного ранга. Так что, на мой взгляд, именно такое полноранговое определение не является уникальным, а численно устойчивым либо QR, либо модифицированный Грам-Шмидт. Это отвечает на ваш вопрос? - person Yo Hsiao; 21.07.2013

arrow_upward
0
arrow_downward

Попробуйте библиотеку LAPACK. У него есть подпрограмма svd (и многие другие).

person Doctor Dan    schedule 01.07.2013