  It has been reported repeatedly that discriminative learning of distance
metric boosts the pattern recognition performance. A weak point of ITML-based
methods is that the distance threshold for similarity/dissimilarity constraints
must be determined manually and it is sensitive to generalization performance,
although the ITML-based methods enjoy an advantage that the Bregman projection
framework can be applied for optimization of distance metric. In this paper, we
present a new formulation of metric learning algorithm in which the distance
threshold is optimized together. Since the optimization is still in the Bregman
projection framework, the Dykstra algorithm can be applied for optimization. A
nonlinear equation has to be solved to project the solution onto a half-space
in each iteration. Na\"{i}ve method takes $O(LMn^{3})$ computational time to
solve the nonlinear equation. In this study, an efficient technique that can
solve the nonlinear equation in $O(Mn^{3})$ has been discovered. We have proved
that the root exists and is unique. We empirically show that the accuracy of
pattern recognition for the proposed metric learning algorithm is comparable to
the existing metric learning methods, yet the distance threshold is
automatically tuned for the proposed metric learning algorithm.
