положительные полуопределенные матрицы и численная устойчивость?

Я пытаюсь провести факторный анализ для матрицы совместного возникновения (C), которая вычисляется из матрицы терминов-документов (TD) следующим образом: C=TD*TD'

Теоретически C должен быть положительно полуопределенным, но это не так, и алгоритм факторного анализа не может работать с ним из-за этого. Я не могу изменить алгоритм из соображений скорости).

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

Какой хороший способ продолжить здесь?


matrix math numerical-methods numerical-stability
person Alex Brooks    schedule 22.01.2010    source источник
comment
по определению A*A' всегда является pos semi-def .. Какова точная ошибка, которую вы получаете при реализации факторного анализа?   -  person Amro    schedule 22.01.2010

Ответы (3)


arrow_upward
7
arrow_downward

Я бы сделал собственное разложение матрицы:

C=Q D Q^-1

Если ваша матрица действительно является положительно-полуопределенной, то все собственные значения (элементы на диагонали D) должны быть неотрицательными. (Вероятно, это тест, который также выполняет ваш алгоритм факторного анализа, чтобы определить, является ли матрица положительно-полуопределенной.)

Если у вас проблемы с числами, некоторые из собственных значений, вероятно, будут чуть меньше нуля. Попробуйте установить для этих записей нулевое значение, вычислите Q D Q^-1, чтобы получить новую, скорректированную C, а затем отправьте ее в свой алгоритм факторного анализа.

С другой стороны, если вы обнаружите, что ваша матрица C имеет действительно отрицательные собственные значения, то вы знаете, что где-то ошиблись в построении C.

person Martin B    schedule 22.01.2010
comment
Благодарю. насколько малы должны быть собственные значения, чтобы считать числовой ошибкой? я получаю отрицательные значения от -9e-15 до -1e-32. - person Alex Brooks; 22.01.2010
comment
Это определенно находится в пределах числовой погрешности. Есть ли у вас доступ к исходному коду вашей процедуры факторного анализа? Скорее всего, он сам выполняет собственное разложение - в этом случае вы можете просто изменить код, чтобы разрешить слегка отрицательные собственные значения. В противном случае используйте метод, который я предложил выше, но имейте в виду, что после повторного умножения Q D Q^-1 вы можете получить новые числовые ошибки, из-за которых ваши собственные значения снова станут чуть ниже нуля. Одна вещь, которую вы могли бы попробовать в этом случае, — это сделать собственные значения очень немного положительными, а не нулевыми. - person Martin B; 22.01.2010
comment
Я немного опоздал на бал, но решил оставить комментарий. Вы должны быть осторожны при вычислении собственного разложения C, так как при формировании C вы удваиваете число обусловленности TD, что может привести к численной нестабильности. Имея это в виду, я бы посмотрел на номер состояния TD. Может быть, что при формировании этих матриц очень плохие условия, что приводит к плохим результатам при формировании и использовании C. - person SplittingField; 27.02.2010

arrow_upward
4
arrow_downward

Не имея возможности прокомментировать, мне придется повторить комментарий SplittingField с придиркой, что формирование C=TD*TD' возводит в квадрат число условия TD, а не удваивает его. Эквивалентным и гораздо более стабильным для нахождения собственного разложения C было бы выполнение разложения по сингулярным числам (SVD) на TD. В качестве бонуса вы получаете число обусловленности: отношение наибольшего единственного числа к наименьшему единственному значению является числом обусловленности матрицы, а логарифм этого числа по основанию 10 является оценкой того, сколько десятичных цифр вы потеряете, если вы использовали C в своих вычислениях (конечно, если наименьшее сингулярное значение равно 0, ваша проблема сингулярна!)

person Community    schedule 09.08.2010
comment
Не говоря уже о том, что выполнение факторной декомпозиции равнозначно выполнению СВД на ТД! Хорошая мысль о плохом состоянии номера TD TD^t. - person Alexandre C.; 30.08.2011

arrow_upward
1
arrow_downward

Прежде всего, существуют методы исправления «патологий» матриц с отрицательными собственными значениями — напомню, матрица возникает в результате серии вычислений, и обычно эти шаги в первую очередь приводят к патологиям. Не совсем уместно принять тот факт, что, поскольку матрица имеет маленькие, близкие к нулю отрицательные собственные значения, это «плохая» матрица. Лучше поработайте над устранением патологий. Что касается SVD, я согласен с тем, что это один из лучших подходов, однако я обычно не использую его в работе так часто, потому что он слишком затратен в вычислительном отношении. Однако если у вас есть один или несколько матричных элементов, равных нулю, т. е. матрица разреженная, то вы должны использовать SVD, так как это будет один из немногих работающих методов.

person lep11    schedule 28.08.2011