Я знаю определение симметричной положительно определенной (SPD) матрицы, но хочу понять больше.
Почему они так важны, интуитивно понятно?
Вот что я знаю. Что еще?
Для заданных данных матрица Co-дисперсии является SPD. Ковариационная матрица является важной метрикой, см. Этот превосходный пост для интуитивного объяснения.
Квадратичная форма является выпуклой, если SPD. Выпуклость - это хорошее свойство для функции, которая может гарантировать, что локальное решение является глобальным решением. Для выпуклых задач есть много хороших алгоритмов, но не для задач, не связанных с выпуклостью.A
Когда является SPD, решение по оптимизации для квадратичной формы
и решение для линейной системыодинаково. Таким образом, мы можем проводить преобразования между двумя классическими задачами. Это важно, потому что это позволяет нам использовать уловки, обнаруженные в одном домене в другом. Например, мы можем использовать метод сопряженных градиентов для решения линейной системы.Есть много хороших алгоритмов (быстрых, числовых устойчивых), которые лучше работают для матрицы SPD, таких как разложение Холецкого.
РЕДАКТИРОВАТЬ: Я не пытаюсь спросить тождества для матрицы SPD, но интуиция за свойство, чтобы показать важность. Например, как упомянул @Matthew Drury, если матрица SPD, все собственные значения являются положительными действительными числами, но почему все положительные значения. У @Matthew Drury был отличный ответ, и именно это я и искал.
Ответы:
(Вещественная) симметричная матрица имеет полный набор ортогональных собственных векторов, для которых соответствующие собственные значения являются действительными числами. Для несимметричных матриц это может не получиться. Например, вращение в двумерном пространстве не имеет собственного вектора или собственных значений в действительных числах, вы должны перейти в векторное пространство над комплексными числами, чтобы найти их.
Если матрица дополнительно положительно определена, то все эти собственные значения являются положительными действительными числами. Этот факт намного проще, чем первый, поскольку, если - собственный вектор с единичной длиной, а λ - соответствующее собственное значение, тоv λ
где последнее равенство использует определение положительной определенности.
Важность здесь для интуиции состоит в том, что собственные векторы и собственные значения линейного преобразования описывают систему координат, в которой преобразование легче всего понять. Линейное преобразование может быть очень трудно понять в «естественном» базисе, таком как стандартная система координат, но каждый из них имеет «предпочтительный» базис из собственных векторов, в которых преобразование действует как масштабирование во всех направлениях. Это значительно упрощает понимание геометрии преобразования.
Например, второй производный тест для локальных экстремумов функции часто дается как ряд загадочных условий, включающих запись во второй производной матрице и некоторые детерминанты. Фактически эти условия просто кодируют следующее геометрическое наблюдение:R2→R
Вы можете понять это с помощью приведенных выше геометрических рассуждений. Первая производная в критической точке исчезает, поэтому скорости изменения функции здесь контролируются второй производной. Теперь мы можем рассуждать геометрически
Поскольку собственные векторы охватывают все пространство, любое другое направление представляет собой линейную комбинацию собственных направлений, поэтому скорости изменения в этих направлениях являются линейными комбинациями скоростей изменения в собственных направлениях. Таким образом, на самом деле это имеет место во всех направлениях (это более или менее означает, что функция, определенная в пространстве более высокого измерения, будет дифференцируемой). Теперь, если вы рисуете маленькую картинку в своей голове, это имеет смысл из чего-то, что является довольно загадочным в текстах для начинающих.
Это относится непосредственно к одному из ваших пунктов пули
Матрица вторых производных везде , которая симметрично положительно определена. Геометрически это означает, что если мы отойдем в любом собственном направлении (и, следовательно, в любом направлении, потому что любое другое является линейной комбинацией собственных направлений), сама функция будет отклоняться выше касательной плоскости. Это означает, что вся поверхность является выпуклой.A
источник
Вы найдете некоторую интуицию во многих элементарных способах показать, что все собственные значения реальной симметричной матрицы реальны: /mathpro/118626/real-symmetric-matrix-has-real-eigenvalues-elementary- доказательство / 118640 # 118640
В частности, квадратичная форма естественным образом встречается в факторе Рэлея, а симметричные матрицы обеспечивают, пожалуй, наиболее естественный способ демонстрации большого семейства матриц, собственные значения которых действительны. См. Теорему Куранта о минимаксе, например: https://en.wikipedia.org/wiki/Courant_minimax_principlexTAx
Кроме того , строго симметричные положительно определенные матрицы только набор матриц , которые можно определить нетривиальное скалярное произведение, наряду с индуцированной нормой: . Это связано с тем, что по определению для действительных векторов x , y d ( x , y ) = d ( y , x ) для всех x , y и ‖ x ‖ 2 =d(x,y)=⟨x,Ay⟩=xTAy x,y d(x,y)=d(y,x) x,y для x ≠ 0 . Таким образом, симметричные положительно определенные матрицы могут рассматриваться как идеальные кандидаты для преобразования координат.∥x∥2=xTAx>0 x≠0
Это последнее свойство является абсолютно ключевым в области машин опорных векторов, в частности методов ядра и трюка ядра , где ядро должно быть симметрично положительным, чтобы индуцировать правильный внутренний продукт. Действительно , теорема Мерсера обобщает интуитивные свойства симметрических матриц на функциональные пространства.
источник
Что касается оптимизации (поскольку вы пометили свой вопрос тегом оптимизации), матрицы SPD чрезвычайно важны по одной простой причине - гессенец SPD гарантирует, что направление поиска является направлением спуска. Рассмотрим вывод метода Ньютона для неограниченной оптимизации. Сначала мы формируем разложение Тейлора функции :f(x+Δx)
При использовании метода Ньютона матрицы Гессена, не относящиеся к SPD, обычно «подталкиваются» к SPD. Существует аккуратный алгоритм под названием модифицированный Холецкий, который обнаружит не-СПД-гессиана, соответствующим образом «подтолкнет» его в правильном направлении и будет факторизовать результат, все за (по существу) ту же стоимость, что и факторизация Холецкого. Квазиньютоновские методы позволяют избежать этой проблемы, заставляя приближенный гессиан быть SPD.
Кроме того, симметричные неопределенные системы получают большое внимание в эти дни. Они возникают в контексте методов внутренней точки для ограниченной оптимизации.
источник
Геометрически положительно определенная матрица определяет метрику , например риманову метрику, поэтому мы можем сразу использовать геометрические понятия.
Кроме того, положительно определенные матрицы связаны с внутренним продуктом:рN мы можем определить внутренний продукт
⟨ Х , у⟩ = ХТу
где A как указано выше, является положительно определенным. Более того, все внутренние продукты нарN возникает таким образом.
источник
Уже есть несколько ответов, объясняющих, почему симметричные положительно определенные матрицы так важны, поэтому я приведу ответ, объясняющий, почему они не так важны, как думают некоторые люди, включая авторов некоторых из этих ответов. Для простоты я ограничу внимание симметричными матрицами и сосредоточусь на гессианах и оптимизации.
Если бы Бог сделал мир выпуклым, не было бы выпуклой оптимизации, была бы просто оптимизация. Точно так же не было бы (симметричных) положительно определенных матриц, просто были бы (симметричные) матрицы. Но дело не в этом, так что разберитесь с этим.
Если задача квадратичного программирования выпуклая, ее можно решить «легко». Если он не выпуклый, глобальный оптимум все еще можно найти, используя методы ветвления и привязки (но это может занять больше времени и больше памяти).
Если для оптимизации используется метод Ньютона, а гессиан на некоторой итерации неопределен, то нет необходимости «искать» его в положительной определенности. При использовании поиска линии можно найти направления отрицательной кривизны и выполнить поиск линии вдоль них, и если используется область доверия, то существует некоторая достаточно небольшая область доверия, такая, что решение проблемы области доверия достигает спуска.
Что касается квазиньютоновских методов, BFGS (демпфированный, если задача ограничена) и DFP поддерживают положительную определенность гессианского или обратного гессенского приближения. Другие квазиньютоновские методы, такие как SR1 (симметричный ранг один), не обязательно поддерживают положительную определенность. Прежде чем вы все изогнетесь из-за этого, это хорошая причина для выбора SR1 для многих задач - если гессиан действительно не является положительно определенным на пути к оптимуму, тогда принудительное приближение квазиньютоновского приближения является положительно определенным может привести к паршивому квадратичному приближению к целевой функции. В отличие от этого, метод обновления SR1 «свободен, как гусь», и может резко изменить свою определенность по мере продвижения вперед.
For nonlinearly constrained optimization problems, what really matters is not the Hessian of the objective function, but the Hessian of the Lagrangian. The Hessian of the Lagrangian may be indefinite even at an (the) optimum, and indeed, it is only the projection of the Hessian of the Lagrangian into the nullspace of the Jacobian of the active (linear and nonlinear) constraints which need be positive semi-definite at the optimum. If you model the Hessian of the Lagrangian via BFGS and thereby constrain it to be positive definite, it might be a terrible fit everywhere, and not work well. By contrast, SR1 can adapt its eigenvalues to what it actually "sees".
There's much more that I could say about all of this, but this is enough to give you a flavor.
Edit: What I wrote 2 paragraphs up is correct. However, I forgot to point out that it also applies to linearly constrained problems. In the case of linearly constrained problems, the Hessian of the Lagrangian is just (reduces down to) the Hessian of the objective function. So the 2nd order optimality condition for a local minimum is that the projection of the Hessian of the objective function into the nullspace of the Jacobian of the active constraints is positive semi-definite. Most notably, the Hessian of the objective function need not (necessarily) be psd at the optimum, and often isn't, even on linearly constrained problems.
источник
Вы уже привели множество причин, по которым SPD важны, но вы все еще разместили вопрос. Поэтому мне кажется, что сначала нужно ответить на этот вопрос: почему положительные величины имеют значение?
Мой ответ заключается в том, что некоторые величины должны быть положительными, чтобы соответствовать нашему опыту или моделям. Например, расстояния между предметами в пространстве должны быть положительными. Координаты могут быть отрицательными, но расстояния всегда неотрицательны. Следовательно, если у вас есть набор данных и какой-то алгоритм, который его обрабатывает, у вас вполне может получиться, что он сломается, когда вы введете в него отрицательное расстояние. Итак, вы говорите: «Мой алгоритм всегда требует ввода положительного расстояния», и это не будет звучать как необоснованная потребность.
В контексте статистики лучшей аналогией была бы разница. Итак, мы рассчитываем дисперсию как
Таким образом, дисперсионно-ковариационные матрицы являются положительными полуопределенными, то есть «неотрицательными» в этой аналогии. Примером алгоритма, который требует этого условия, является разложение Холецкого, это очень удобно. Его часто называют «квадратный корень матрицы». Итак, подобно квадратному корню из действительного числа, которое требует неотрицательности, Холецкий хочет неотрицательные матрицы. Мы не находим это ограничение при работе с ковариационными матрицами, потому что они всегда есть.
Итак, это мой утилитарный ответ. Такие ограничения, как неотрицательность или SPD, позволяют нам создавать более эффективный алгоритм расчета или удобные инструменты моделирования, которые доступны, когда ваши входные данные удовлетворяют этим ограничениям.
источник
Here are two more reasons which haven't been mentioned for why positive-semidefinite matrices are important:
The graph Laplacian matrix is diagonally dominant and thus PSD.
Positive semidefiniteness defines a partial order on the set of symmetric matrices (this is the foundation of semidefinite programming).
источник