  Given a convex and differentiable objective $Q(\M)$ for a real symmetric
matrix $\M$ in the positive definite (PD) cone -- used to compute Mahalanobis
distances -- we propose a fast general metric learning framework that is
entirely projection-free. We first assume that $\M$ resides in a space $\cS$ of
generalized graph Laplacian matrices corresponding to balanced signed graphs.
$\M \in \cS$ that is also PD is called a graph metric matrix. Unlike low-rank
metric matrices common in the literature, $\cS$ includes the important
diagonal-only matrices as a special case. The key theorem to circumvent full
eigen-decomposition and enable fast metric matrix optimization is Gershgorin
disc perfect alignment (GDPA): given $\M \in \cS$ and diagonal matrix $\S$,
where $S_{ii} = 1/v_i$ and $\v$ is $\M$'s first eigenvector, we prove that
Gershgorin disc left-ends of similarity transform $\B = \S \M \S^{-1}$ are
perfectly aligned at the smallest eigenvalue $\lambda_{\min}$. Using this
theorem, we replace the PD cone constraint in the metric learning problem with
tightest possible linear constraints per iteration, so that the alternating
optimization of the diagonal / off-diagonal terms in $\M$ can be solved
efficiently as linear programs via the Frank-Wolfe method. We update $\v$ using
Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm
start as entries in $\M$ are optimized successively. Experiments show that our
graph metric optimization is significantly faster than cone-projection schemes,
and produces competitive binary classification performance.
