Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods

Abstract

A fundamental class of matrix optimization problems that arise in many areas of science and engineering is that of quadratic optimization with orthogonality constraints. Such problems can be solved using line-search methods on the Stiefel manifold, which are known to converge globally under mild conditions. To determine the convergence rate of these methods, we give an explicit estimate of the exponent in a Lojasiewicz inequality for the (non-convex) set of critical points of the aforementioned class of problems. By combining such an estimate with known arguments, we are able to establish the linear convergence of a large class of line-search methods. A key step in our proof is to establish a local error bound for the set of critical points, which may be of independent interest.

References in corpus (2)

• Generalized power method for sparse principal component analysis
• Adaptive Canonical Correlation Analysis Based On Matrix Manifolds

Cited by in corpus (6)

• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• A Cubic Regularized Newton's Method over Riemannian Manifolds
• On the Łojasiewicz Exponent of the Quadratic Sphere Constrained Optimization Problem
• Improved Learning Rates for Stochastic Optimization
• Tensor Canonical Correlation Analysis with Convergence and Statistical Guarantees
• KL property of exponent $1/2$ of quadratic functions under nonnegative zero-norm constraints and applications