¿Cómo se verifica computacionalmente si una función es positiva definida?

Answer 1

Sí, hablando de la matriz del núcleo definida como [math] \ mathbb {K} _ {i, j} = k (x_ {i}, x_ {j}) [/ math] que siempre debe ser un semi- positivo simétrico matriz definida como si doy un ejemplo de muestra [matemática] x = (x_1, x_2,…, x_m) [/ matemática] la información disponible para los algoritmos basados ​​en el núcleo está contenida completamente en la matriz de evaluaciones del núcleo:

[matemáticas] \ mathbb {K} = (k (x_ {i}, x_ {j}) _ {i, j = 1} ^ m [/ matemáticas]

Probablemente quieras aplicar una de las proposiciones de Saitoh:

“Una función [matemática] k (x, \ tilde {x}) [/ matemática] es un núcleo válido si y solo si para cualquier conjunto finito de fecha [matemática] (x_1, x_2,…, x_m) [/ matemática] para cualquier [matemática] (a_1, a_2,…, a_m) ‘\ in \ mathbb {R} ^ {m} [/ math] tenemos [math] \ sum \ limits_ {i, j = 1} ^ {M} a_ {i} a_ {j} k (x_ {i}, x_ {j}) \ geqslant 0 [/ math] “.

El usuario de Quora tiene toda la razón: “verificar si su función es definitivamente positiva, es equivalente a verificar por K.” Todas las formas en que le dijo que lo hiciera son buenas.

Pero solo quiero agregar que a veces su matriz es una matriz de bloque diagonal y, por lo tanto, puede usar el complemento Schur:

[matemáticas] \ begin {pmatrix} A & B \\ B ‘& C \\ \ end {pmatrix} \ geqslant 0 \ Leftrightarrow CB’A ^ {- 1} B \ geqslant 0 [/ math]

Computacionalmente es mejor cuando puedes usarlo.

Gracias por A2A.

Answer 2

Una característica de la matriz positiva definida es que tiene que ser simétrica y todos sus valores propios son positivos (matriz positiva definida). Por lo tanto, puede reducir el problema a la búsqueda de valores propios, que es un problema bien estudiado pero difícil (algoritmo de valor propio). La iteración de potencia es una variante utilizada en Page Rank, aunque solo encuentra un valor propio.

Ahora hay algo más eficiente llamado prueba determinante / prueba pivote. Recomiendo revisar el curso de Álgebra Lineal del Prof. Gilbert Strang y, en particular, la conferencia Matrices simétricas y definición positiva. Una matriz es positiva definida si todos sus pivotes son positivos. Todos los pivotes son positivos si los determinantes de todas las submatrices kxk superiores izquierdas son positivos. En el peor de los casos, sería [math] \ mathcal {O} (n ^ {4}) [/ math]. Creo que esto puede mejorarse a partir de la naturaleza recursiva del cálculo de determinantes.

Editar: No sabía que el criterio se llama criterio de Sylvester. Me alegra saber 🙂

Answer 3

Como ha formulado su problema, supongo que la matriz representativa de su función es K. Sin embargo, la definición debería ser más bien:

[math] \ mathbf {X} ^ TK \ mathbf {X} = \ underset {i, j} {\ sum} x_i k_ {ij} x_j \ ge 0 [/ math]

(Si esto no es lo que quieres decir, considera mi respuesta nula).

Entonces, para verificar si su función es positiva definida, es equivalente a verificar si tiene K. Tiene varias formas de hacerlo:

-O K es diagonalizable y todos sus valores propios son positivos (en realidad, esta es una forma de verificar la fuerza bruta).

-o todos sus principales menores son positivos (criterio de Sylvester)

– O tiene una descomposición única de Cholesky.

-K es una matriz representativa de un producto escalar

Bueno, estos métodos claramente no son baratos, pero no siempre se verifica la primera desigualdad (en realidad, nadie está verificando la primera desigualdad de manera exhaustiva para todas las x).