СВД и сингулярные/несингулярные матрицы

Мне нужно использовать форму матрицы SVD для извлечения понятий из серии документов. Моя матрица имеет вид A = [d1, d2, d3 ... dN], где di — двоичный вектор из M компонентов. Затем разложение svd дает мне svd(A) = U x S x V' с S, содержащими сингулярные значения.

Я использую SVDLIBC для обработки в nodejs (используя небольшой модуль, который я написал для его использования ). Вроде все работало хорошо, но я заметил что-то довольно странное в поведении времени выполнения в зависимости от состояния моей матрицы (где N, M растут, но уже выше 1000 для каждого). Во-первых, я не рассматривал возможность извлечения одних и тех же векторов документов, но теперь, после некоторых тестов, похоже, что добавление документа дважды иногда чрезвычайно ускоряет обработку.

  1. Должен ли я убедиться, что каждый из столбцов A попарно независимый? Должны ли они быть все линейно независимыми? (Я подумал, что нет, поскольку SVD, кажется, хорошо выполняет свою работу, даже если некоторые столбцы абсолютно одинаковы, он просто покажет в результирующей декомпозиции, какие столбцы/строки бесполезны, имея 0 компонентов в U или V)
  2. Теперь, когда вычисление SVD моей большой матрицы иногда занимает слишком много времени, я пытался уменьшить ее размер, удалив те же столбцы, но обнаружил, что на самом деле добавление фиктивных одинаковых векторов может сделать это намного быстрее. Это нормально? Что происходит?

Логически я бы сказал, что хочу, чтобы моя матрица содержала как можно больше информации, и, таким образом,

  • [A] Удалите все одинаковые столбцы, а в лучшем случае,
  • [B] Удалить линейно зависимые столбцы.

Выполнение [A] кажется довольно простым и не слишком затратным в вычислительном отношении, я мог бы хэшировать свои векторы при построении, чтобы проверить, какие, возможно, одинаковые векторы, а затем потратить время на их проверку, но существуют ли хорошие методы вычисления для [A] и [B ]?
(Я был бы признателен, если бы [A] не приходилось проверять равенство нового вектора со всеми прошлыми векторами методом грубой силы, а что касается [B], я не знаю никакого хорошего способа проверить/сделать).

Добавлен связанный вопрос: о моем втором вопросе, почему поведение SVD во время работы изменилось бы так сильно, просто добавив один похожий столбец? Это нормальное возможное поведение или это означает, что я должен искать ошибку в SVDLIBC?


node.js matrix svd
person Alexandre Kaspar    schedule 11.01.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Чтобы ответить на ваш вопрос о том, является ли медленное поведение ошибкой в ​​​​библиотеке, которую вы используете, я бы предложил попытаться получить SVD той же матрицы с помощью другого инструмента. Например, в Octave извлеките SVD вашей матрицы для сравнения времени выполнения:

[U, S, V] = svd(A)
person Sam    schedule 18.02.2014