Argmax and eigenvectors 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.
 A: 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.
A: 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. 
