Kyle A. Gallivan

Zhifeng Deng, P. -A. Absil, Kyle A. Gallivan et al.

The matrix exponential restricted to skew-symmetric matrices has numerous applications, notably in view of its interpretation as the Lie group exponential and Riemannian exponential for the special orthogonal group. We characterize the invertibility of the derivative of the skew-restricted exponential, thereby providing a simple expression of the tangent conjugate locus of the orthogonal group. In view of the skew restriction, this characterization differs from the classic result on the invertibility of the derivative of the exponential of real matrices. Based on this characterization, for every skew-symmetric matrix $A$ outside the (zero-measure) tangent conjugate locus, we explicitly construct the domain and image of a smooth inverse -- which we term \emph{nearby logarithm} -- of the skew-restricted exponential around $A$. This nearby logarithm reduces to the classic principal logarithm of special orthogonal matrices when $A=\mathbf{0}$. The symbolic formulae for the differentiation and its inverse are derived and implemented efficiently. The extensive numerical experiments show that the proposed formulae are up to $3.9$-times and $3.6$-times faster than the current state-of-the-art robust formulae for the differentiation and its inversion, respectively.

Yijia Zhou, Kyle A. Gallivan, Adrian Barbu

Clustering is a widely used technique with a long and rich history in a variety of areas. However, most existing algorithms do not scale well to large datasets, or are missing theoretical guarantees of convergence. This paper introduces a provably robust clustering algorithm based on loss minimization that performs well on Gaussian mixture models with outliers. It provides theoretical guarantees that the algorithm obtains high accuracy with high probability under certain assumptions. Moreover, it can also be used as an initialization strategy for $k$-means clustering. Experiments on real-world large-scale datasets demonstrate the effectiveness of the algorithm when clustering a large number of clusters, and a $k$-means algorithm initialized by the algorithm outperforms many of the classic clustering methods in both speed and accuracy, while scaling well to large datasets such as ImageNet.

Guillaume Olikier, Kyle A. Gallivan, P. -A. Absil

This paper considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the algebraic variety of real matrices of upper-bounded rank. This problem is known to enable the formulation of various machine learning or signal processing tasks such as dimensionality reduction, collaborative filtering, and signal recovery. Several definitions of stationarity exist for this nonconvex problem. Among them, Bouligand stationarity is the strongest necessary condition for local optimality. This paper proposes two first-order methods that generate a sequence in the variety whose accumulation points are Bouligand stationary. The first method combines the well-known projected projected-gradient descent map with a rank reduction mechanism. The second method is a hybrid of projected gradient descent and projected projected-gradient descent. Both methods stand out in the field of low-rank optimization methods when considering their convergence properties, their streamlined design, their typical computational cost per iteration, and their empirically observed numerical performance. The theoretical framework used to analyze the proposed methods is of independent interest.

Simon Mataigne, Kyle A. Gallivan

We propose a new method for computing the eigenvalue decomposition of a dense real normal matrix $A$ through the decomposition of its skew-symmetric part. The method relies on algorithms that are known to be efficiently implemented, such as the bidiagonal singular value decomposition and the symmetric eigenvalue decomposition. The advantages of this method stand for normal matrices with few real eigenvalues, such as random orthogonal matrices. We provide a stability and a complexity analysis of the method. The numerical performance is compared with existing algorithms. In most cases, the method has the same operation count as the Hessenberg factorization of a dense matrix. Finally, we provide experiments for the application of computing a Riemannian barycenter on the special orthogonal group.