Leading eigenvector value problem as an optimisation problem for asymmetric matrices

Question

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$.

Answer 1

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.