On the Robust PCA and Weiszfeld’s Algorithm

Abstract

The principal component analysis (PCA) is a powerful standard tool for reducing the dimensionality of data. Unfortunately, it is sensitive to outliers so that various robust PCA variants were proposed in the literature. This paper addresses the robust PCA by successively determining the directions of lines having minimal Euclidean distances from the data points. The corresponding energy functional is non-differentiable at a finite number of directions which we call anchor directions. We derive a Weiszfeld-like algorithm for minimizing the energy functional which has several advantages over existing algorithms. Special attention is paid to carefully handling the anchor directions, where the relation between local minima and one-sided derivatives of Lipschitz continuous functions on submanifolds of $\mathbb {R}^d$ is taken into account. Using ideas for stabilizing the classical Weiszfeld algorithm at anchor points and the Kurdyka–Łojasiewicz property of the energy functional, we prove global convergence of the whole sequence of iterates generated by the algorithm to a critical point of the energy functional. Numerical examples demonstrate the very good performance of our algorithm.

Appendix A: One-Sided Derivatives and Minimizers on Embedded Manifolds

The one-sided directional derivative of a function $f:\mathbb {R}^d \rightarrow \mathbb {R}$, $d \in {\mathbb {N}}$, at a point $x \in \mathbb {R}^d$ in direction $h \in \mathbb {R}^d$ is defined by

$$\begin{aligned} Df(x;h) :=\lim _{\alpha \downarrow 0}\frac{f(x+\alpha h) - f(x)}{\alpha }. \end{aligned}$$

Restricting f to a submanifold ${\mathcal {M}} \subseteq \mathbb {R}^d$, we can restrict our considerations to $h \in T_x {\mathcal {M}}$. Recall that ${\mathcal {M}} \subseteq \mathbb {R}^d$ is an m-dimensional submanifold of $\mathbb {R}^d$ if for each point $x \in {\mathcal {M}}$ there exists an open neighborhood $U \subseteq \mathbb {R}^d$ as well as an open set $\Omega \subseteq \mathbb {R}^m$ and a so-called parametrization $\varphi \in C^1(\Omega , \mathbb {R}^d)$ of ${\mathcal {M}}$ with the properties

• (i) $\varphi (\Omega ) = {\mathcal {M}} \cap U$,

• (ii) $\varphi ^{-1}:{\mathcal {M}} \cap U \rightarrow \Omega$ is surjective and continuous, and

• (iii) $D \varphi (x)$ has full rank m for all $x \in \Omega$.

To establish the relation between one-sided directional derivatives and local minima of functions on manifolds we need the following lemma. A proof can be found in [45, Lemma B.1].

Lemma A.1

Let ${\mathcal {M}}\subset \mathbb {R}^{d}$ be an m-dimensional submanifold of $\mathbb {R}^{d}$. Then the tangent space $T_{x}{\mathcal {M}}$ and the tangent cone

$$\begin{aligned}&{\mathcal {T}}_x{\mathcal {M}} :=\left\{ u\in \mathbb {R}^{d}:\ \exists \text { sequence } (x_k)_{k\in \mathbb {N}}\subset {\mathcal {M}}\setminus \{x\} \text { with } x_k\rightarrow x \text { s.t. } \frac{x_k-x}{\Vert x_k-x\Vert }\right. \\&\qquad \qquad \qquad \quad \left. \rightarrow \frac{u}{\Vert u\Vert }\right\} \cup \{0\} \end{aligned}$$

coincide.

The following theorem gives a general necessary and sufficient condition for local minimizers of Lipschitz continuous functions on embedded manifolds using the notation of one-sided derivatives. For the Euclidean setting ${\mathcal {M}} = \mathbb {R}^d$, the first relation of the proposition is trivially fulfilled for any function $f:\mathbb {R}^d \rightarrow \mathbb {R}$, while a proof of the sufficient minimality condition in the second part was given in [4]. Moreover, the authors of [4] gave an example that Lipschitz continuity in the second part cannot be weakened to just continuity.

Theorem A.2

Let ${\mathcal {M}} \subset \mathbb {R}^d$ be an m-dimensional submanifold of $\mathbb {R}^d$ and $f:\mathbb {R}^d \rightarrow \mathbb {R}$ a locally Lipschitz continuous function. Then the following holds true:

• 1. If ${\hat{x}} \in {\mathcal {M}}$ is a local minimizer of f on ${\mathcal {M}}$, then $Df({\hat{x}};h) \ge 0$ for all $h \in T_{{\hat{x}}}{\mathcal {M}}$.

• 2. If $Df({\hat{x}};h) >0$ for all $h\in T_{{\hat{x}}} {\mathcal {M}} \setminus \{0\}$, then ${\hat{x}}$ is a strict local minimizer of f on ${\mathcal {M}}$.

A proof can be found in [45, Thm. 6.1] along with an example which demonstrates the necessity of the Lipschitz continuity of f in the manifold setting in the first part of the theorem. Furthermore, note that $Df({\hat{x}};h) \ge 0$ for all $h\in T_{{\hat{x}}} {\mathcal {M}} \setminus \{0\}$ does not imply that ${\hat{x}}$ is a local minimizer of f on ${\mathcal {M}}$.