Stochastic Dykstra Algorithms for Metric Learning on Positive Semi-Definite Cone
This work addresses computational efficiency in pattern recognition tasks using covariance descriptors, though it appears incremental as it builds on existing Dykstra algorithms with a randomization tweak.
The authors tackled the problem of slow convergence in metric learning for covariance descriptors by developing a stochastic Dykstra algorithm that randomizes the order of half-space projections, achieving significant acceleration in convergence to optimal solutions while maintaining O(n^3) time complexity.
Recently, covariance descriptors have received much attention as powerful representations of set of points. In this research, we present a new metric learning algorithm for covariance descriptors based on the Dykstra algorithm, in which the current solution is projected onto a half-space at each iteration, and runs at O(n^3) time. We empirically demonstrate that randomizing the order of half-spaces in our Dykstra-based algorithm significantly accelerates the convergence to the optimal solution. Furthermore, we show that our approach yields promising experimental results on pattern recognition tasks.