Argmax y vectores propios

Question

Estoy leyendo un artículo (en biología) que realiza un algoritmo de agrupación.

En un punto del documento se afirma que:

$$ \arg \max_{\lVert X\rVert=1} X^T S\, X $$

puede calcularse como el vector propio normalizado de $S$ con el mayor valor propio...

¿Cómo es posible? Supongo que se trata de un problema de componentes principales, pero no soy un experto en este tipo de técnicas.

Answer 1

Si $S$ tuvo la descomposición $S = A^H A$ entonces el cuadrado de la norma espectral de $A$ sería $$ \lVert A\rVert_2^2 = \max_{\lVert x\rVert_2 = 1} \lVert A x\rVert_2^2 = \max_{\lVert x\rVert_2 = 1} Ax \cdot Ax = \max_{\lVert x\rVert_2 = 1} A^H Ax \cdot x = \max_{\lVert x\rVert_2 = 1} x^T A^H Ax = \lambda_1 $$ donde $\lambda_1$ es el mayor valor propio de $S$ .

En ese caso teníamos $$ \arg \max_{\lVert x\rVert_2 = 1} x^T A^H Ax = e_{\lambda_1} $$ con $e_{\lambda_1}$ siendo el vector propio normalizado para $\lambda_1$ .

$S$ sin embargo, tendría que ser semidefinida positiva y ser una matriz de Gram (véase aquí ), que podría ser el caso en su escenario biológico.

Answer 2

Reescribiendo tu expresión de esta manera:

$$\arg \max_{\| X \| = 1} \frac{X^T S X}{X^T X}$$

lo que tienes se llama cociente de Rayleigh. (Inserto la división por $X^T X = 1$ para aclarar por qué se llama cociente). Es evidente que cualquier valor propio de $S$ es un posible cociente de Rayleigh: basta con evaluar la función con un vector propio. Si $S$ es simétrica, entonces una descomposición ortogonal de $X$ en vectores propios muestra que el mayor valor posible de este cociente es exactamente el mayor valor propio de $S$ .

Explícitamente, tenemos $X=\sum_{i=1}^n c_i q_i$ con $S q_i = \lambda_i q_i$ donde el $q_i$ son ortonormales. Entonces

$$\frac{X^T S X}{X^T X} = \frac{\left ( \sum_{i=1}^n c_i q_i \right )^T S \left ( \sum_{j=1}^n c_j q_i \right )}{\left ( \sum_{i=1}^n c_i q_i \right )^T \left (\sum_{j=1}^n c_i q_i \right )} \\ = \frac{\sum_{i=1}^n \sum_{j=1}^n c_i c_j \lambda_j q_i^T q_j}{\sum_{i=1}^n \sum_{j=1}^n c_i c_j q_i^T q_j} \\ = \frac{\sum_{j=1}^n c_j^2 \lambda_j q_j^T q_j}{\sum_{j=1}^n c_j^2 q_j^T q_j} \\ = \frac{\sum_{j=1}^n c_j^2 \lambda_j}{\sum_{j=1}^n c_j^2}$$

Si dejamos que $d_k=\frac{c_k^2}{\sum_{j=1}^n c_j^2}$ vemos que $\sum_{k=1}^n d_k = 1$ así que por la desigualdad del triángulo, el cociente de Rayleigh no puede ser mayor que el mayor valor propio. Como ya hemos establecido que puede sea el mayor valor propio, obtenemos el resultado.