Нуль-пространство прямоугольной плотной матрицы

Для заданной плотной матрицы каков наилучший способ найти его нулевое пространство в пределах некоторого допуска ?

A \in R^{m \times n}, m >> n; m a x (m) \approx 100000

$A \in R^{m \times n}, m >> n; max(m) \approx 100000$

ϵ

$\epsilon$

Исходя из этого, могу ли я сказать, что некоторые столбцы линейно зависят от ? Другими словами, после вычисления нулевого пространственного базиса, какие столбцы должны быть удалены, чтобы получить неособую матрицу? $\epsilon$ $A$

Рекомендации приветствуются.

linear-algebra Александр
источник

Ответы:

Стандартные методы для определения нулевого пространства матрицы должны использовать QR-разложение или SVD. Если точность имеет первостепенное значение, SVD является предпочтительным; QR-разложение происходит быстрее.

$A = U\Sigma V^{H}$ $V$ $\Sigma$ $\max(m,n) \cdot \varepsilon$ $\varepsilon$

Используя QR-разложение, если $A^{T} = QR$ , и ранг $A$ равен $r$ , то последние $n-r$ столбцы $Q$ составляют пустое пространство $A$ , предполагая, что QR-разложение является раскрытием ранга. Чтобы определить $r$ , рассчитайте количество элементов на главной диагонали $R$ , величина которых превышает допуск (аналогично тому, который используется в подходе SVD).

Не используйте разложение LU. В точной арифметике это жизнеспособный подход, но с арифметикой с плавающей запятой накопление числовых ошибок делает его неточным.

Википедия охватывает эти темы здесь .

Джефф Оксберри
источник

Джефф, говоря в терминах QR, предположим, что у меня есть декомпозиция, как мне тогда связать базис пустого пространства и столбцы в исходной матрице? Другими словами, какие столбцы я должен удалить из , чтобы избавиться от пустого пространства? Дело здесь в том, чтобы работать с самим , а не с его разложением.

A

$A$

A

$A$

Александр

Подпрограммы, которые вычисляют декомпозицию QR, обычно включают опцию для возврата вектора перестановки, указывающего, как переставляются столбцы для получения факторизации QR. Последние записей этого вектора перестановки будут соответствовать строкам (столбцы ), которые находятся в нулевом пространстве. Первые записей этого вектора соответствуют столбцам которые являются линейно независимыми. Я не уверен, что вы подразумеваете под "избавиться от пустого пространства". Вы имеете в виду, что хотите удалить столбцы из чтобы получить неособую матрицу?

n - r

$n-r$

A

$A$

A^{T}

$A^{T}$

r

$r$

A^{T}

$A^{T}$

A

$A$

Джефф Оксберри

Да, я имею в виду это. Я посмотрю на перестановку, спасибо.

Александр

Это другой вопрос. Что вы бы тогда сделать вместо этого вычислить QR - разложение (или СВД) из . Если вы вычислите QR-разложение , вы можете вычислить ранг как в ответе выше (нет необходимости транспонировать матрицу), а затем первые записей (где - ранг ) вектора перестановки соответствуют для независимых столбцов . Такой же алгоритм применяется к SVD; если вы можете вернуть вектор перестановки вместе с разложением, это должно предоставить необходимую информацию.

A

$A$

A

$A$

A

$A$

r

$r$

r

$r$

A

$A$

A

$A$

Джефф Оксберри

Если , как показывает ваш вопрос, вы можете сохранить некоторую работу, сначала выбрав набор индексов из (скажем) случайных строк и используя ортогональную факторизацию . (QR-факторизация - это та, где - это квадрат, а - прямоугольник с рангом , а оставшиеся столбцы в равны нулю. Использование перестановочной QR-факторизации повысит стабильность; перестановка должна быть затем учтена более подробно. рецепт приготовления.) $m\gg n$ $I$ $p\approx 5n$ $A_{I:}^T=QR$ $Q$ $R$ $r$ $n-r$ $R$

Как правило, это даст вам гораздо ниже мерное подпространство , натянутое на столбцы , последние столбцов . Это подпространство содержит нулевое пространство . Теперь выбрать другой, непересекающийся случайный набор индексов и вычислить QR разложение . Умножьте полученное нулевое пространство слева на чтобы получить улучшенное возможно, даже меньшего размера. Итерируйте, пока размерность больше не уменьшится. Тогда вы , вероятно, правильное пространство нуля и можете проверить путем вычисления . Если это еще не незначительно, выполните дальнейшие итерации с наиболее значимыми строками. $N$ $n-r$ $Q$ $A$ $(A_{I:}N)^T$ $N$ $N$ $N$ $AN$

Изменить: Как только у вас есть , вы можете найти максимальное множество линейно независимых столбцов путем ортогональной факторизации с поворотом. Действительно, множество индексов, не выбранных в качестве опорных точек, будет обладать этим свойством. $N$ $J$ $A$ $N^T=QR$ $J$

Арнольд Ноймайер
источник

+1 за эффективный способ определения пустого пространства большой матрицы. Мне придется помнить, чтобы проконсультироваться с этим ответом позже, когда он мне понадобится.

Джефф Оксберри

Действительно, это звучит разумно, однако мои матрицы умещаются в 16 ГБ ОЗУ, поэтому я бы остановился на стандартном matlab qr.

Александр

Профессор Ноймайер, я решил протестировать этот алгоритм, но я точно не понимаю, что такое

и что означает «вычислить QR-факторизацию

»? Не могли бы вы объяснить немного больше.

N

$N$

(A_{I :} N)^{T}

$(A_{I:}N)^T$

Александр

Я немного отредактировал свой ответ.

рассчитывается по рецепту Джеффа Оксберри.

N

$N$

Арнольд Ноймайер

Спасибо. Я реализовал это. Однако, насколько я вижу, этот алгоритм не позволяет определить мне множество линейно независимых столбцов

(так как мы разложим

вместо

), а просто помогает оценить сам базис нуль - пространства?

A

$A$

A_{I :}^{T}

$A_{I:}^T$

A_{I :}

$A_{I:}$

Александр