Предоставляет ли SciPy.sparse.linalg.svds матричный ранг? - PullRequest
Новая
       10

Предоставляет ли SciPy.sparse.linalg.svds матричный ранг?

0 голосов
/ 10 января 2019

У меня есть большая разреженная двоичная прямоугольная матрица, M , где n > m . Мое понимание ранга матрицы предполагает, что самый большой возможный ранг равен m , а мое понимание SVD предполагает, что ранг матрицы можно найти путем определения числа ненулевых сингулярных значений.

Я пытаюсь использовать SciPy.sparse.linalg.svds для определения ранга M . Первая проблема заключается в том, что я не могу вычислить m единичные значения, поскольку k может доходить только до p = m - 1. Поэтому я подумал Я был бы умным и вычислил бы p наивысшие значения, p наименьшие значения, объединил бы их, запустил set, чтобы найти уникальные значения, и в итоге получил бы список максимум м значения. Это не сработало в соответствии с планом.

Вот MWE: 

import scipy.sparse
import scipy.sparse.linalg
import numpy
import itertools  

m = 6
n = 10

test = scipy.sparse.rand(m, n, density=0.25, format='lil', dtype=None, random_state=None)

for i, j in itertools.product(list(range(m)), list(range(n))):
     test[i, j] = 1 if test[i, j] > 0 else 0

U1, S1, VT1 = scipy.sparse.linalg.svds(test, k = min(test.shape) - 1, ncv = None, tol = 1e-5, which = 'LM', v0 = None, maxiter = None, 
                                    return_singular_vectors = True)

U2, S2, VT2 = scipy.sparse.linalg.svds(test, k = min(test.shape) - 1, ncv = None, tol = 1e-5, which = 'SM', v0 = None, maxiter = None, 
                                    return_singular_vectors = True)

S = list(set(numpy.concatenate((S1, S2), axis = 0)))

len(S)

Вот пример вывода: 

10

с S, являющимся 

[0.5303120147925737,
 1.0725314055439354,
 2.7940865631779643,
 1.5060744813473148,
 1.8412737686034186,
 0.3208993522030293,
 0.5303120147925728,
 1.072531405543936,
 1.5060744813473153,
 1.841273768603419]

Как матрица m X n с m <<em> n может иметь ранг n ? Мои предположения выше неверны, или я неправильно использую функцию? Мои настоящие M редкие, двоичные, и примерно 300 X 500.

Спасибо за внимание!

С помощью @tch я придумал следующий взлом. Для проверки ранга = m мне нужно проверить только наименьшее значение и добавить его к значениям m - 1, полученным из функции самых высоких значений svds. Оказывается, svds не сообщает 0s при пороговом значении, поэтому функция с самыми низкими значениями вернет nan для ранга <<em> m . Вот пересмотренный код: 

import scipy.sparse
import scipy.sparse.linalg
import numpy
import itertools

m = 6
n = 10

test = scipy.sparse.rand(m, n, density=0.25, format='lil', dtype=None, random_state=None)

test = test > 0
test = test.astype('d')

U1, S1, VT1 = scipy.sparse.linalg.svds(test, k = min(test.shape) - 1, ncv = None, tol = 1e-5, which = 'LM', v0 = None, maxiter = None, 
                                    return_singular_vectors = True)

U2, S2, VT2 = scipy.sparse.linalg.svds(test, k = 1, ncv = None, tol = 1e-5, which = 'SM', v0 = None, maxiter = None, 
                                    return_singular_vectors = True)

S = list(set(numpy.concatenate((S1, S2), axis = 0)))

print(sum(x > 1e-10 for x in S))
S

1 Ответ

0 голосов
/ 10 января 2019

То, что вы пытаетесь сделать, будет работать в точной арифметике (при условии, что матрица не имеет повторяющихся сингулярных значений). Однако из-за ошибок округления чисел на практике это не сработает.

Чтобы увидеть это попробуйте 

C = np.random.randn(10,3)
u,s,vt = np.linalg.svd(C@C.T)

Обратите внимание, что C@C.T - это матрица 10x10 с рангом 3. Однако вы увидите, что ни одно из сингулярных значений не равно точно нулю (однако 7 близки к 0).

При численном нахождении ранга матрицы пороговое значение часто используется для определения значения единственного значения 0. Например, все, что ниже 1e-10, может быть установлено в ноль.

Если матрица имеет точный ранг k, надеюсь, вы увидите k особые значения вдали от 0, а затем min(m,n)-k особые значения, очень близкие к нулю. Однако, в зависимости от матрицы, может даже не быть четко определенного «отбрасывания».

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

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

В качестве замечания о том, где найти test[i,j] > 0, вы можете просто набрать test>0, и он даст логический массив с True в ненулевых записях и False в другом месте. Вы также можете установить dtype случайной матрицы на bool, и оно будет True всякий раз, когда случайное число отлично от нуля.

...