We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. By doing so, we can guarantee that our method finds a Stiefel matrix that is globally optimal with respect to the quadratic objective function, while in addition being sparse. As a motivating application we consider the task of permutation synchronisation, which can be understood as a constrained clustering problem that has particular relevance for matching multiple images or 3D shapes in computer vision, computer graphics, and beyond. We demonstrate that the proposed approach outperforms previous methods in this domain.
翻译:我们解决了在Stiefel 元件上找到一个稀薄的矩阵(单位长度的正正方圆柱形)以最大限度地实现(或最大限度地减少)二次目标功能的不光化优化问题。 Stiefel 元件上的优化问题出现在诸如图形匹配、集聚或调和同步等各种组合问题的光谱放松中。虽然在这种环境中,聚集是一种可取的属性,但在光谱配方中却大多被忽略,因为现有溶剂,例如基于eigenvalue分解的溶剂,在同时保持全球最佳性能保障的同时,无法对孔径进行核算。我们填补了这一空白,并提议对Orthococial Iteration 算法进行简单而有效的松动-促进修改,以寻找一个矩阵中占主导地位的静态空间。通过这样做,我们可以保证我们的方法找到一个与二次目标功能功能全球最佳的Stiefel 矩阵,而同时又是稀疏的。作为激励性应用程序,我们考虑的是,在计算机图像组合中,在多重组合中,我们可以理解到一个特定的、多面制成方法。