Проверьте положительную определенность или положительную полуопределенность

Question

Я хочу проверить, является ли матрица положительно определенной или положительно полуопределенной с использованием Python.

Как я могу это сделать?Есть ли выделенная функция в SciPy для этого или других модулей?

Answer 1

Полагаю, вы уже знаете, что ваша матрица симметрична.

Хороший тест на положительную определенность (на самом деле стандартный!) - попытаться вычислить его факторизацию Холецкого. Это успешно, если ваша матрица положительно определена.

Это самый прямой способ, так как для этого требуется O (n ^ 3) операций (с небольшой константой), и вам потребуется как минимум n умножений матрицы на вектор для проверки «напрямую».

Answer 2

Разложение Холецкого является хорошим вариантом, если вы работаете с положительно определенными (PD) матрицами.

Однако, оно выдает следующую ошибку на положительной полу -определенной (PSD) матрицескажем,

A = np.zeros((3,3)) // the all-zero matrix is a PSD matrix
np.linalg.cholesky(A)
LinAlgError: Matrix is not positive definite -
Cholesky decomposition cannot be computed

Для матриц PSD вы можете использовать восемь () scipy / numpy, чтобы проверить, что все собственные значения неотрицательны.

>> E,V = scipy.linalg.eigh(np.zeros((3,3)))
>> E
array([ 0.,  0.,  0.])

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

def isPSD(A, tol=1e-8):
  E,V = scipy.linalg.eigh(A)
  return np.all(E > -tol)

, которая возвращает True для матриц, которые приблизительно соответствуют PSD с заданным допуском.

Answer 3

Проверка того, что целые собственные значения симметричной матрицы A неотрицательны, отнимает много времени, если A очень большой, а модуль scipy.sparse.linalg.arpack обеспечивает хорошее решение, поскольку можно настроить возвращенные собственные значения, указав параметры. (см. Scipy.sparse.linalg.arpack для получения дополнительной информации)

Поскольку мы знаем, что оба конца спектра A неотрицательны, то остальные собственные значения также должны быть неотрицательны.Таким образом, мы можем сделать так:

from scipy.sparse.linalg import arpack
def isPSD(A, tol = 1e-8):
    vals, vecs = arpack.eigsh(A, k = 2, which = 'BE') # return the ends of spectrum of A
    return np.all(vals > -tol)

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

Answer 4

Одним из хороших решений является вычисление всех минорных определителей и проверка того, что все они неотрицательные.

Answer 5

более простой способ - вычислить детерминанты миноров для этой матрицы.