Самый быстрый способ проверить, увеличивает ли вектор ранг матрицы - PullRequest
Новая
       11

Самый быстрый способ проверить, увеличивает ли вектор ранг матрицы

5 голосов
/ 01 февраля 2012

Учитывая матрицу A размером n × m, с гарантией, что n> m = rank (A), и с учетом столбца v размером n × 1, какой самый быстрый способ проверить, является ли [A v] имеет ранг строго больше, чем A?

Для моего приложения A разрежено, n равно 2 ^ 12, а m где-то в 1: n-1. Сравнение рейтинга (полное ([A v])) на моей машине занимает около секунды, и мне нужно делать это десятки тысяч раз, поэтому я был бы очень рад найти более быстрый способ.

Ответы [ 3 ]

6 голосов
/ 01 февраля 2012

Нет необходимости выполнять повторные вычисления, если вы можете позволить ОДНО вычисление нулевого пространства. Достаточно всего одного вызова на ноль. Для нового вектора V, если скалярное произведение с V и базисом нулевого пространства не равно нулю, то V увеличит ранг матрицы. Например, предположим, что у нас есть матрица M, которая, конечно, имеет ранг 2. 

M = [1 1;2 2;3 1;4 2];
nullM = null(M')';

Будет ли новый вектор-столбец [1; 1; 1; 1] увеличивать ранг, если мы добавим его к M? 

nullM*[1;1;1;1]
ans =
       -0.0321573705742971
        -0.602164651199413

Да, поскольку он имеет ненулевую проекцию, по крайней мере, на один из базисных векторов в nullM.

Как насчет этого вектора: 

nullM*[0;0;1;1]
ans =
      1.11022302462516e-16
      2.22044604925031e-16

В этом случае оба числа по существу равны нулю, поэтому рассматриваемый вектор не увеличил бы ранг M.

Суть в том, что необходимо только простое умножение матрицы на вектор после генерации нулевого пространства. Если ваша матрица слишком велика (и матрица почти полного ранга), что при вызове null здесь произойдет сбой, вам потребуется проделать дополнительную работу. Однако n = 4096 не слишком велико, если в матрице не слишком много столбцов.

Одной из альтернатив, если null слишком много, является вызов svds, чтобы найти те сингулярные векторы, которые по существу равны нулю. Они сформируют базу пустого пространства, которая нам нужна.

2 голосов
/ 01 февраля 2012

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

Редактировать : Как правильно указал @IanHincks, это не ранг. Я оставляю ответ здесь, на случай, если кому-то еще он понадобится в будущем.

1 голос
/ 01 февраля 2012

Возможно, вы можете попытаться решить систему A*x=v, если у нее есть решение, означающее, что ранг не увеличивается. 

x=(B\A)';
norm(A*x-B) %% if this is small then the rank does not increase
...