# GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT

Abstract:

We propose a general projection-free metric learning framework, where the minimization objective $\min_{\M \in \cS} Q(\M)$ is a convex differentiable function of the metric matrix $\M$, and $\M$ resides in the set $\cS$ of generalized graph Laplacian matrices for connected graphs with positive edge weights and node degrees.
Unlike low-rank metric matrices common in the literature, $\cS$ includes the important positive-diagonal-only matrices as a special case in the limit.
The key idea for fast optimization is to rewrite the positive definite cone constraint in $\cS$ as signal-adaptive linear constraints via Gershgorin disc alignment, so that the alternating optimization of the diagonal and off-diagonal terms in $\M$ can be solved efficiently as linear programs via Frank-Wolfe iterations.
We prove that left-ends of the Gershgorin discs can be aligned perfectly using the first eigenvector $\v$ of $\M$, which we update iteratively using Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) with warm start as diagonal / off-diagonal terms are optimized.
Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.

## icassp2020metric_slides.pdf

### Paper Details

Authors:
Cheng Yang, Gene Cheung, Wei Hu
Submitted On:
15 May 2020 - 4:01pm
Type:
Presentation Slides
Event:
Presenter's Name:
Gene Cheung
Paper Code:
ICASSP 2020 Paper #2062 Paper ID: TU2.PG.2
Document Year:
2020

(13)

### Subscribe

[1] Cheng Yang, Gene Cheung, Wei Hu, "GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5352. Accessed: Jul. 13, 2020.
@article{5352-20,
url = {http://sigport.org/5352},
author = {Cheng Yang; Gene Cheung; Wei Hu },
publisher = {IEEE SigPort},
title = {GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT},
year = {2020} }
TY - EJOUR
T1 - GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT
AU - Cheng Yang; Gene Cheung; Wei Hu
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5352
ER -
Cheng Yang, Gene Cheung, Wei Hu. (2020). GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT. IEEE SigPort. http://sigport.org/5352
Cheng Yang, Gene Cheung, Wei Hu, 2020. GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT. Available at: http://sigport.org/5352.
Cheng Yang, Gene Cheung, Wei Hu. (2020). "GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT." Web.
1. Cheng Yang, Gene Cheung, Wei Hu. GRAPH METRIC LEARNING VIA GERSHGORIN DISC ALIGNMENT [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5352