Argmax and eigenvectors

Question

I am reading a paper (in biology) which performs a clustering algorithm.

At one point in the paper, it is stated that:

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

can be computed as the normalized eigenvector of $S$ with largest eigenvalue...

How is this possible? I am guessing that there is a principal component issue, but I am not an expert in such techniques.

Answer 1

If $S$ had the decomposition $S = A^H A$, then the square of the spectral norm of $A$ would be $$ \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 $$ where $\lambda_1$ is the largest eigenvalue of $S$.

In that case we had $$ \arg \max_{\lVert x\rVert_2 = 1} x^T A^H Ax = e_{\lambda_1} $$ with $e_{\lambda_1}$ being the normalized eigenvector for $\lambda_1$.

$S$ would have to be positive-semidefinite however and to be a Gram Matrix (see here), which might be the case in your biological scenario.

Answer 2

Rewriting your expression this way:

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

what you have is called a Rayleigh quotient. (I insert the division by $X^T X = 1$ to clarify why it is called a quotient.) It is clear that any eigenvalue of $S$ is a possible Rayleigh quotient: just evaluate the function with an eigenvector. If $S$ is symmetric, then an orthogonal decomposition of $X$ into eigenvectors shows that the largest possible value of this quotient is exactly the largest eigenvalue of $S$.

Explicitly, we have $X=\sum_{i=1}^n c_i q_i$ with $S q_i = \lambda_i q_i$, where the $q_i$ are orthonormal. Then

$$\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}$$

If we let $d_k=\frac{c_k^2}{\sum_{j=1}^n c_j^2}$ we see that $\sum_{k=1}^n d_k = 1$, so by the triangle inequality, the Rayleigh quotient can be no larger than the largest eigenvalue. Since we already established that it can be the largest eigenvalue, we get the result.