2
$\begingroup$

As noted in 1806.05647, given a symmetric matrix $A$, the leading eigenvector value problem (LEVP)

$$Av = \lambda v,$$

where $A = A^T \in \mathbb{R}^{n \times n}$, $\lambda$ is the largest eigenvalue of $A$ and $v$ is the corresponding eigenvector, can be written as an unconstrained optimisation problem

$$\min_{x \in \mathbb{R}^n} f(x) \equiv \min_{x \in \mathbb{R}^n} \| A - xx^T\|^2_F,$$

where $\| \cdot \|_F$ denotes the Frobenius norm.

When the matrix $A$ is symmetric, the gradient of the function $f(x)$ is

$$\nabla f(x) = -4Ax + 4(x^Tx)x$$

and the optimal solution to the aforementioned optimisation problem can be shown to be $\pm \sqrt{\lambda}v$. All the coordinate-wise descent algorithms represented in the paper for computing the leading eigenvector depend on this result and the matrix $A$ being symmetric.

Is it possible to generalise this to the case when the matrix $A$ is not symmetric? In that case, the gradient is: $$\nabla f(x) = -2Ax -2A^Tx + 4(x^Tx)x$$

and the solution that was optimal for the symmetric matrix $A$ ( $\pm \sqrt{\lambda}v$) now is the optimal solution for $\frac{1}{2}(A^T + A)$ rather than $A$.

$\endgroup$
1
$\begingroup$

I believe so. Here is one way to show the claim. The function being minimized can be written in terms of the standard (Euclidean) norm on $\mathbb{R}^n$ as \begin{equation} f(x) = || A - xx^T||_F^2 = tr\left[(A^T-xx^T)(A-xx^T)\right] = tr(A^TA)+ x^2\left[x^2-2 R(M,x)\right] = tr(A^TA)+ [x^2-R(M,x)]^2 - R(M,x)^2, \end{equation} where $x^2=x^Tx$, $M=\frac{A^T+A}{2}$ and $R(M,x)=\frac{x^TMx}{x^2}$ is the Rayleigh quotient of $M$. To minimize $f(x)$, we thus need to make the second term vanish and find the largest value for the square of the Rayleigh quotient.

Since $M$ is real-symmetric, it can be diagonalized with real eigen-values $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n \in \mathbb{R}$ (spectral theorem). Furthermore, the min-max theorem says that $\lambda_1 \leq R(M,x) \leq \lambda_n$, $\forall x\in \mathbb{R}^n\setminus \{0\}$ and so $R(M,x)^2 \leq max(\lambda_1^2,\lambda_n^2)$.

The Rayleigh quotient evaluated at the eigen-vector $v_k$ exactly returns the eigen-value $\lambda_k$, i.e. $R(M,v_k)=\lambda_k$. So $x =\pm \sqrt{\lambda_k} v_k$ (with care if $\lambda_k<0$) will make the second term of $f(x)$ vanish (and will in fact be a critical point). Therefore, the optimal solution is either $\pm\sqrt{\lambda_1}v_1$ or $\pm\sqrt{\lambda_n}v_n$ (depending on which of $\lambda_1^2$ or $\lambda_n^2$ is greater).

If $M=(A^T+A)/2$ symmetric positive-definite, then $0<\lambda_1\leq \ldots\leq \lambda_n$ and $\pm\sqrt{\lambda_n}v_n$ is optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.