Получить нулевое пространство или одномерное пространство, которое является его наилучшим приближением эффективно - PullRequest
Новая
       47

Получить нулевое пространство или одномерное пространство, которое является его наилучшим приближением эффективно

3 голосов
/ 14 декабря 2011

Я делал это, используя вычисления SVD 

[U, S, V] = svd(A)

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

Для нуля (A) документация предполагает, что он все равно делает SVD. Кроме того, это не работает, если A имеет полный ранг. SVD продолжает поиск наибольшего единственного значения, затем следующего и т. Д., В то время как мне просто нужно наименьшее.

Это, кажется, большое узкое место. Буду очень признателен за помощь в этом. Использую MATLAB.

Спасибо.

Ответы [ 3 ]

2 голосов
/ 14 декабря 2011

В этой статье Википедии описаны три метода численного расчета нулевого пространства: сокращение (исключение Гаусса), SVD и QR-разложение . Вкратце, (1) сокращение «не подходит для практического вычисления нулевого пространства из-за проблем с числовой точностью при наличии ошибок округления», (2) SVD является «современным подходом», но оно «как правило, стоит примерно столько же, сколько несколько матрично-матричных умножений с матрицами одинакового размера», и (3) численная стабильность и стоимость QR-разложения находятся «между методами SVD и редукционных подходов».

Так что, если SVD слишком медленный, вы можете дать шанс QR-разложение . Алгоритм с вашими обозначениями выглядит следующим образом: «A - это матрица 4xN с 4<N. Используя QR-факторизацию A', мы можем найти такую ​​матрицу, что A'*P = Q*R = [Q1 Q2]*R, где где P матрица перестановок Q равна NxN и R равна Nx4. Матрица Q1 равна Nx4 и состоит из первых 4 столбцов Q. Матрица Q2 равна Nx(N-4) и состоит из из последних N-4 столбцов Q. Поскольку A*Q2 = 0, столбцы Q2 охватывают нулевое пространство A. "

Реализация Matlab: [Q, R, P] = qr(A', 'matrix'); Столбцы матрицы Q2 = Q(:, 5:end); дают нулевое пространство A.

1 голос
/ 14 декабря 2011

Этот ответ основан на вашем комментарии о том, что вы на самом деле хотите решить Ax = 0. Для этого полное вычисление нулевого пространства обычно неэффективно. Если вы хотите приближение наименьших квадратов к x, взгляните на оператор Matlab \ (см. help mldivide).

В других случаях «экономичный» SVD через svd(A,0) может быть полезен для неквадратных матриц (он вычисляет не полный S, а только ненулевой блок).

0 голосов
/ 14 декабря 2011

Если все точки с плоскости, вызывайте SVD только с образцом.

...