Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning

Dual principal component pursuit and orthogonal dictionary learning are two fundamental tools in data analysis, and both of them can be formulated as a manifold optimization problem with nonsmooth objective. Algorithms with convergence guarantees for solving this kind of problems have been very limited in the literature. In this paper, we propose a novel manifold proximal point algorithm for solving this nonsmooth manifold optimization problem. Numerical results are reported to demonstrate the effectiveness of the proposed algorithm.

I. Introduction

In this paper, we focus on the nonsmooth and nonconvex optimization problem \begin{equation*}\mathop {\min }\limits_{{\mathbf{x}} \in {\mathbb{R}^n}} f({\mathbf{x}}): = {\left\| {{Y^ \top }{\mathbf{x}}} \right\|_1},{\text{ s}}{\text{.t}}{\text{., }}{\left\| {\mathbf{x}} \right\|_2} = 1,\tag{1}\end{equation*} where Y ∈ ℝ^n×p is a given matrix and ||•||₁ denotes the ℓ₁ norm of a vector. The set is known as a sphere constraint and is a special case of the Stiefel manifold. Note that (1) has a nonconvex constraint and a nonsmooth objective, which make it very challenging to solve. Though manifold optimization has been a very active area [1], most existing algorithms require computing the derivative of the objective function and are therefore not applicable to (1). The problem (1), which should be contrasted with the ℓ₁-PCA problem considered in [2], has recently received much attention because of its many interesting applications, among which are two representative ones: orthogonal dictionary learning (ODL) and dual principal component pursuit (DPCP). In the following we briefly survey the literature on these two problems.