Linear Convergence of a Proximal Alternating Minimization Method with Extrapolation for $\ell_1$-Norm Principal Component Analysis

Introduction

Many of the earlier algorithms for L1-PCA, such as , are heuristic in nature. In particular, there is no guarantee that the outputs of these algorithms satisfy any optimality condition of Problem (2). Among the first algorithms for L1-PCA that come with theoretical guarantees are those proposed by Kwak and Nie et al. , which are based on fixed-point (FP) iterations. The former applies to Problem (2) with $K=1$, while the latter can handle general $K\geq 1$. The per-iteration computational costs of these two algorithms are bounded by $\mathcal{O}(ndK+dK^{2})$, which is cheap in the practically relevant case where $K\ll\min\{n,d\}$. Moreover, it is shown that for both algorithms, the iterates generated have a limit point (i.e., subsequential convergence of the iterates) and every limit point satisfies certain first-order optimality condition of the problem. However, the convergence rates of the two algorithms remain unknown. Around the same time, McCoy and Tropp studied a semidefinite relaxation (SDR) approach (see for an overview) to solving Problem (2) when $K=1$. It is shown that with high probability, the solution obtained via this approach will have an objective value that is at least $c\cdot\sqrt{2/\pi}$ times the optimal value for any fixed $c\in(0,1)$. However, standard interior-point method-based implementations of the SDR approach have a computational complexity of roughly $\mathcal{O}(n^{3.5})$, which renders the approach impractical when the dataset is large. Later, Markopoulos et al. proposed an exact algorithm for solving Problem (2) that runs in $\mathcal{O}(n^{dK-K+1})$ time. Although this algorithm is impractical due to its high computational cost, it shows that Problem (2) is actually polynomial-time solvable when both $d$ and $K$ are fixed. Moreover, it can be used to benchmark the solution quality of different L1-PCA algorithms. In a follow-up work, Markopoulos et al. developed an algorithm based on bit-flipping (BF) iterations for tackling Problem (2). On one hand, the computational cost of each BF iteration is $\mathcal{O}(ndK+nK^{3}))$, which is inferior to that of the FP iteration developed in when $n\geq d$. On the other hand, the algorithm based on BF iterations is guaranteed to converge in a finite number of steps, while that based on FP iterations is not known to possess such a property. Nevertheless, the number of BF iterations needed can be exponential in $n$ and $K$ in the worst case. Moreover, it is not clear whether the solution obtained from the BF iterations satisfies any optimality condition of Problem (2). Recently, Kim and Klabjan revisited Problem (2) under the setting where $K=1$ and proposed an algorithm similar to those in for tackling it. It is shown that the sequence of iterates generated by the algorithm will converge in a finite number of steps. This qualitatively improves upon the subsequential convergence results in . Moreover, by pretending that the objective function of (2) is smooth, it is claimed that the limit of the sequence is a local maximum of the problem. However, a rigorous proof of this claim is still missing.

To shed light on the numerical performance of and obtain strong theoretical convergence guarantees for our proposed method PAMe, a key step is to characterize the growth behavior of the objective function of (3) around the limiting critical points (see Subsection 1.2 for the definition) of the problem. Towards that end, we first show that the Kurdyka-Łojasiewicz (KŁ) exponent at any limiting critical point of certain orthogonality constrained linear optimization (LO-OC) problem is $1/2$. This result is new and complements that in for (homogeneous) quadratic optimization with orthogonality constraint. Moreover, it implies, through a calculus rule established in , that the KŁ exponent at any limiting critical point of the original L1-PCA formulation (2) is $1/2$. Then, we relate the limiting critical points of (3) to those of a particular instance of the LO-OC problem and show that the KŁ exponent at any of the former is also $1/2$. With this characterization, we can utilize the analysis framework in to establish the linear convergence of PAMe to a limit $(\bm{P}^{*},\bm{Q}^{*})$, which is a limiting critical point of Problem (3). Moreover, we show that the limit $\bm{Q}^{*}$ is a critical point (see Subsection 1.2 for the definition) of Problem (2) under certain conditions on the step sizes of PAMe. To the best of our knowledge, our work is the first to determine the KŁ exponent at the limiting critical points of both (2) and (3) and to present a first-order method that provably converges to a limiting critical point of (3) at a linear rate.

The rest of this paper is organized as follows. In Section 2, we introduce our proposed method PAMe and present the main results of this paper. We then prove the main results in Section 3 (concerning the KŁ exponent at the limiting critical points of Problems (2) and ,(3)) and Section 4 (concerning the convergence behavior of PAMe). In Section 5, we report the numerical performance of PAMe and other existing methods on both synthetic and real-world datasets. We end with some closing remarks in Section 6.

2 Notation and Definitions

denote (a variant of) the sign function that will be used to express the subdifferential of $x\mapsto-|x|$. Given a matrix $\bm{A}$, let $\operatorname{sgn}(\bm{A})$ denote the matrix obtained by applying $\operatorname{sgn}(\cdot)$ to each entry of $\bm{A}$; $\|\bm{A}\|_{F}$ and $\|\bm{A}\|$ denote the Frobenius norm and spectral norm of $\bm{A}$, respectively; $\lambda_{k}(\bm{A})$ denote the $k$-th largest eigenvalue of $\bm{A}$ if $\bm{A}$ is symmetric. Given a vector $\bm{x}$, let $\operatorname{Diag}(\bm{x})$ denote the diagonal matrix with $\bm{x}$ as its diagonal. Given square matrices $\bm{Y}_{1},\dots,\bm{Y}_{n}$, let $\operatorname{BlkDiag}(\bm{Y}_{1},\dots,\bm{Y}_{n})$ denote the block diagonal matrix with $\bm{Y}_{1},\dots,\bm{Y}_{n}$ as its diagonal blocks.

for any $\bm{x}\in\mathcal{S}$, where $\mathcal{N}_{\mathcal{S}}(\bm{x})$ is the normal cone to $\mathcal{S}$ at $\bm{x}$.

whenever $\|\bm{x}-\bar{\bm{x}}\|_{F}\leq\epsilon$ and $f(\bar{\bm{x}})<f(\bm{x})<f(\bar{\bm{x}})+\nu$.

and invoking the subdifferential calculus rules in [34, Chapter 10B], we see that every locally optimal solution $\bm{Q}\in{\rm St}(d,K)$ to Problem (2) satisfies

Main Results

As mentioned in Subsection 1.1, our strategy for tackling Problem (2) is to apply a proximal alternating minimization scheme to its two-block reformulation (3). Let us now formalize this strategy and introduce our proposed method PAMe.

To begin, observe that Problem (3) can be written as

which is in a form that is amenable to the PAM method developed in (see also ). Given the current iterate $(\bm{P}^{k},\bm{Q}^{k})\in\mathcal{B}(n,K)\times{\rm St}(d,K)$, the method generates the next iterate $(\bm{P}^{k+1},\bm{Q}^{k+1})\in\mathcal{B}(n,K)\times{\rm St}(d,K)$ via

where $\alpha_{k},\beta_{k}>0$ are the step sizes. Motivated by the desire to accelerate the PAM iterations, we incorporate an extrapolation step when updating the block variable $\bm{P}$. Specifically, we replace (8) by

On the other hand, the update (9) is an instance of the orthogonal Procrustes problem , whose solution is given by

Here, $\bm{U}^{k+1}\in{\rm St}(d,K)$ and $\bm{V}^{k+1}\in\mathcal{O}^{K}$ are obtained from a thin SVD $\bm{U}^{k+1}\bm{\Sigma}^{k+1}{\bm{V}^{k+1}}^{T}$ of $\bm{Q}^{k}+\bm{X}\bm{P}^{k+1}/\beta_{k}$. The above development leads to our proposed method PAMe, whose complete description can be found in (1). Since the costs of implementing (11) and (12) are $\mathcal{O}(ndK)$ and $\mathcal{O}(dK^{2})$, respectively, the per-iteration cost of (1) is $\mathcal{O}(ndK+dK^{2})$, which is cheap when $K\ll\min\{n,d\}$.

Moreover, let $\bm{Z}^{*}\in\mathcal{B}(n,K)\times{\rm St}(d,K)$ be a limiting critical point of Problem (7). Then, there exist $\epsilon_{h}\in(0,1)$ and $\eta_{h}>0$ such that for all $\bm{Z}\in\mathcal{B}(n,K)\times{\rm St}(d,K)$ with $\|\bm{Z}-\bm{Z}^{*}\|_{F}\leq\epsilon_{h}$,

With Theorem 1 at our disposal, we can study the convergence behavior of PAMe (Algorithm (1)). Our second result has two parts. The first part states that with suitable choices of the parameters in PAMe, the iterates $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ generated by the method will converge linearly to a limiting critical point $(\bm{P}^{*},\bm{Q}^{*})$ of Problem (7). Now, since our original problem of interest is Problem (5), a natural question would be whether $\bm{Q}^{*}$ is one of its (limiting) critical points. Unfortunately, we do not yet know the answer to this question. The second part of our result, which provides a partial answer, gives a sufficient condition for $\bm{Q}^{*}$ to be a critical point of Problem (5) (i.e., $\bm{Q}^{*}$ satisfies (6)).

Let $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ be the sequence of iterates generated by Algorithm 1, where the step sizes $\{\alpha_{k}\}_{k\geq 0}$, $\{\beta_{k}\}_{k\geq 0}$ and extrapolation parameters $\{\gamma_{k}\}_{k\geq 0}$ satisfy (i) $\alpha_{*}\leq\alpha_{k}\leq\alpha^{*}$ for some $\alpha_{*},\alpha^{*}\in(0,+\infty)$, (ii) $3\beta_{*}/2\leq\beta_{k}\leq\beta^{*}$ for some $\beta_{*},\beta^{*}\in(0,+\infty)$, and (iii) $0\leq\gamma_{k}<\gamma^{*}=\min\{1,\alpha_{*}\beta_{*}/2\|\bm{X}\|^{2}\}$. Then, the sequence $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ converges at least linearly to a limiting critical point $(\bm{P}^{*},\bm{Q}^{*})$ of Problem (7). Moreover, if $\alpha_{k}=\alpha_{*}$ for $k\geq 0$, then $\bm{Q}^{*}$ is a solution to the following generalized equation:

then $\bm{Q}^{*}$ is a critical point of Problem (5). Conversely, every critical point $\bar{\bm{Q}}$ of Problem (5) satisfying $\bm{0}\in-\bm{X}\bm{P}^{*}+\mathcal{N}_{{\rm St}(d,K)}(\bar{\bm{Q}})$ and $\bm{P}^{*}\in\operatorname{sgn}(\bm{X}^{T}\bar{\bm{Q}})$ is a solution to the generalized equation (15), regardless of whether (16) holds.

It is worth noting that the sufficient condition (16) is efficiently verifiable; i.e., after obtaining the limit point $\bm{Q}^{*}$, one can efficiently verify whether (16) holds. Moreover, condition (16) suggests that PAMe is more likely to return a critical point of Problem (5) if we choose a smaller step size $\alpha_{*}$. In fact, we observe from our numerical experiments that a small $\alpha_{*}$ often leads to favorable performance of PAMe on the L1-PCA problem; see Section 5 for details.

Characterizing the KŁ exponent for Problems (5) and (7)

Our goal in this section is to prove Theorem 1. This is achieved in three steps. First, we invoke a calculus rule established in to show that the task of estimating the KŁ exponent at a limiting critical point of Problem (5) reduces to that of estimating the KŁ exponent at a limiting critical point of an LO-OC problem. Then, we establish a local error bound for the LO-OC problem and use it to characterize the KŁ exponent for that problem. Lastly, we utilize the result obtained for the LO-OC problem and the structures of Problems (5) and (7) to complete the proof.

By [20, Lemma 2.1], for any $\theta\in[0,1)$, the function $g$ has a KŁ exponent of $\theta$ at any of its non-limiting critical point. Thus, we shall focus on determining the KŁ exponents of $g$ at its limiting critical points.

2 Estimating the KŁ Exponent for Problem (LO-OC)

denote the set of limiting critical points of Problem (LO-OC). Based on the development in the previous subsection, our next step is to prove the following result, which can be of independent interest.

There exist $\epsilon_{g}\in(0,1)$, $\eta_{g}>0$ such that for all $\bm{Q}\in{\rm St}(d,K)$ and $\bm{Q}^{*}\in\mathcal{Q}$ with $\|\bm{Q}-\bm{Q}^{*}\|_{F}\leq\epsilon_{g}$,

Theorem 3 implies that the KŁ exponent at any limiting critical point of Problem (LO-OC) is $1/2$ with $\epsilon=\epsilon_{g}$, $\eta=\eta_{g}$, and $\nu=+\infty$. It is worth noting that the constants $\epsilon,\eta,\nu$ are uniform over all limiting critical points in $\mathcal{Q}$.

The proof of Theorem 3 can be divided into three parts. As it is quite long and technical, readers who are interested in how Theorem 3 is used to complete the proof of Theorem 1 can skip ahead to Subsection 3.3.

We begin with the following result, which provides, among other things, a characterization of $\mathcal{Q}$.

In particular, we have $\bm{Q}\in\mathcal{Q}$ if and only if

Now, observe that $\bm{I}_{d}-\bm{Q}\bm{Q}^{T}/2$ is invertible and the eigenvalues of $\bm{Q}\bm{Q}^{T}$ are or $1$. It follows that

Putting the above pieces together, we obtain

where $\widetilde{\bm{A}}=\operatorname{Diag}(a_{1},\dots,a_{r})$ with $a_{1}\geq\dots\geq a_{r}>0$. Suppose that $\bm{A}$ has $p\geq 1$ distinct positive singular values. In other words, there exist indices $s_{0},s_{1},\ldots,s_{p}$ such that $0=s_{0}<s_{1}<\cdots<s_{p}=r$ and

Let $h_{i}=s_{i}-s_{i-1}$ be the multiplicity of the $i$-th largest positive singular value, where $i=1,\dots,p$. Then, we clearly have $\sum_{i=1}^{p}h_{i}=r$ and

where $\bm{U}=\operatorname{BlkDiag}(\bm{U}_{1},\dots,\bm{U}_{p})$ with $\bm{U}_{i}\in\mathcal{O}^{h_{i}}$ for $i=1,\dots,p$, $\bm{q}\in\{\pm 1\}^{r}$, and $\bm{V}\in{\rm St}(d-r,K-r)$.

If $\bm{Q}$ is of the form given in (25), then using the block structure of $\bm{A}$ in (21), it is straightforward to verify that $\bm{Q}\in{\rm St}(d,K)$ and $\bm{A}-\bm{Q}\bm{A}^{T}\bm{Q}=\bm{0}$. By Proposition 1, we conclude that $\bm{Q}\in\mathcal{Q}$.

Conversely, suppose that $\bm{Q}\in\mathcal{Q}$. By Proposition 1, we have $\bm{A}-\bm{Q}\bm{A}^{T}\bm{Q}=\bm{0}$. Since $\bm{Q}\in{\rm St}(d,K)$, this implies that

which, together with $\bm{A}-\bm{Q}\bm{A}^{T}\bm{Q}=\bm{0}$, yields

Using the block structures of $\bm{A}$ in (21) and $\bm{Q}$ in (24), we have

It then follows from (26) that $\bm{Q}_{1}^{T}\widetilde{\bm{A}}=\widetilde{\bm{A}}^{T}\bm{Q}_{1}$ and $\bm{Q}_{2}^{T}\widetilde{\bm{A}}=\bm{0}$. Since $\widetilde{\bm{A}}$ has full rank, the latter implies that $\bm{Q}_{2}=\bm{0}$, which in turn implies that $\bm{Q}_{4}^{T}\bm{Q}_{4}=\bm{I}_{K-r}$ because we have $\bm{Q}\in{\rm St}(d,K)$. Using $\bm{Q}_{2}=\bm{0}$ and (27), we obtain

i.e., $(\bm{I}_{r}-\bm{Q}_{1}\bm{Q}_{1}^{T})\widetilde{\bm{A}}=\bm{0}$ and $\bm{Q}_{3}\bm{Q}_{1}^{T}\widetilde{\bm{A}}=\bm{0}$. These, together with the fact that $\widetilde{\bm{A}}$ has full rank, imply that $\bm{Q}_{1}\in\mathcal{O}^{r}$ and $\bm{Q}_{3}=\bm{0}$.

Now, using the block structures of $\widetilde{\bm{A}}$ in (23) and $\bm{Q}_{1}$ in (24), we get

Since $\bm{Q}_{1}^{T}\widetilde{\bm{A}}=\widetilde{\bm{A}}^{T}\bm{Q}_{1}$, we have

Moreover, the fact that $\bm{Q}_{1}\in\mathcal{O}^{r}$ implies

By rewriting (29) as $\bm{Q}_{h_{j}h_{i}}^{T}=\tfrac{a_{s_{i}}}{a_{s_{j}}}\bm{Q}_{h_{i}h_{j}}$ for $i,j\in\{1,\ldots,p\}$ and repeating the above argument, we get

Since $a_{s_{1}}>\dots>a_{s_{p}}>0$ by (22), the identities in (32) and (33) imply that

This, together with (29) and (31), yields

Let $\bm{Q}_{h_{i}h_{i}}=\bm{U}_{i}\bm{\Lambda}_{i}\bm{U}_{i}^{T}$ ($i=1,\ldots,p$) be an eigen-decomposition of $\bm{Q}_{h_{i}h_{i}}$, where $\bm{U}_{i}\in\mathcal{O}^{h_{i}}$ and $\bm{\Lambda}_{i}=\operatorname{Diag}(\lambda_{s_{i-1}+1},\dots,\lambda_{s_{i}})$. Then, we have $\bm{Q}_{h_{i}h_{i}}^{T}\bm{Q}_{h_{i}h_{i}}=\bm{U}_{i}\bm{\Lambda}^{2}_{i}\bm{U}_{i}^{T}=\bm{I}_{h_{i}}$ from (34), which implies that $\bm{\Lambda}^{2}_{i}=\bm{I}_{h_{i}}$. It follows that $\lambda_{s_{i-1}+1},\ldots,\lambda_{s_{i}}\in\{\pm 1\}$.

Putting all the pieces together, we see that $\bm{Q}_{1}$ takes the form

with $\bm{U}_{i}\in\mathcal{O}^{h_{i}}$ for $i=1,\ldots,p$ and $\bm{q}\in\{\pm 1\}^{r}$, $\bm{Q}_{2}=\bm{0}$, $\bm{Q}_{3}=\bm{0}$, and $\bm{Q}_{4}\in{\rm St}(d-r,K-r)$. This completes the proof. ∎

The following result shows that the collection $\{\mathcal{Q}_{\bm{q}}\}_{\bm{q}\in\{\pm 1\}^{r}}$ essentially forms a well-separated partition of the set $\mathcal{Q}$.

Let $\bm{q}=(\bm{q}_{1},\ldots,\bm{q}_{p})$ and $\bm{q}^{\prime}=(\bm{q}_{1}^{\prime},\ldots,\bm{q}_{p}^{\prime})$, where $\bm{q}_{i},\bm{q}_{i}^{\prime}\in\{\pm 1\}^{h_{i}}$ for $i=1,\ldots,p$. Suppose that $\bm{Q}=\begin{bmatrix}\bm{Q}_{1}&\bm{0}\\ \bm{0}&\bm{V}\end{bmatrix}\in\mathcal{Q}_{\bm{q}}$. By definition of $\mathcal{Q}_{\bm{q}}$ in (35), for $i=1,\ldots,p$, the eigenvalues of the $i$-th diagonal block of $\bm{Q}_{1}$ are given by the entries of $\bm{q}_{i}$. Thus, if $\bm{Q}\in\mathcal{Q}_{\bm{q}}\cap\mathcal{Q}_{\bm{q}^{\prime}}$, then both $\bm{q}_{i}$ and $\bm{q}_{i}^{\prime}$ are vectors of eigenvalues of the $i$-th diagonal block of $\bm{Q}_{1}$, which implies that $\bm{q}_{i}$ and $\bm{q}_{i}^{\prime}$ are equal up to a permutation for $i=1,\ldots,p$. It follows that whenever $\mathcal{Q}_{\bm{q}}\cap\mathcal{Q}_{\bm{q}^{\prime}}\not=\emptyset$, we have $\mathcal{Q}_{\bm{q}}=\mathcal{Q}_{\bm{q}^{\prime}}$.

Now, suppose that $\mathcal{Q}_{\bm{q}}\cap\mathcal{Q}_{\bm{q}^{\prime}}=\emptyset$. Let

be arbitrary, where $\bm{U}=\operatorname{BlkDiag}(\bm{U}_{1},\dots,\bm{U}_{p})$, $\bm{U}^{\prime}=\operatorname{BlkDiag}(\bm{U}_{1}^{\prime},\dots,\bm{U}_{p}^{\prime})$ with $\bm{U}_{i},\bm{U}_{i}^{\prime}\in\mathcal{O}^{h_{i}}$ for $i=1,\ldots,p$ and $\bm{V},\bm{V}^{\prime}\in{\rm St}(d-r,K-r)$. Then, we have

where the last equality follows from the fact that $\bm{V}^{\prime}\in{\rm St}(d-r,K-r)$. For $i=1,\ldots,p$, let $t_{i}$ and $t_{i}^{\prime}$ denote the number of 1’s in $\bm{q}_{i}$ and $\bm{q}_{i}^{\prime}$, respectively. If there exists a $j\in\{1,\dots,p\}$ such that $t_{j}\neq t_{j}^{\prime}$, then we can find a $k\in\{1,\dots,h_{j}\}$ such that for any $\bm{U}_{j}\in\mathcal{O}^{h_{j}}$,

where the second inequality follows from classic perturbation results for eigenvalues of symmetric matrices (see, e.g., [37, Corollary 4.10]) and the last equality is due to the fact that $\bm{q}_{j},\bm{q}_{j}^{\prime}\in\{\pm 1\}^{h_{j}}$ and $t_{j}\not=t_{j}^{\prime}$. Since $\bm{Q}\in\mathcal{Q}_{\bm{q}}$, $\bm{Q}^{\prime}\in\mathcal{Q}_{\bm{q}^{\prime}}$ are arbitrary, we conclude from (3.2.1) and (37) that

Otherwise, we have $t_{i}=t_{i}^{\prime}$ for $i=1,\ldots,p$, which implies that $\bm{q}_{i}$ and $\bm{q}_{i}^{\prime}$ are equal up to a permutation for $i=1,\ldots,p$. In this case, we have $\mathcal{Q}_{\bm{q}}=\mathcal{Q}_{\bm{q}^{\prime}}$, which contradicts our assumption that $\mathcal{Q}_{\bm{q}}\cap\mathcal{Q}_{\bm{q}^{\prime}}=\emptyset$. This completes the proof. ∎

2.2 Local Error Bound

Equipped with the results in the previous section, our next task is to establish the following local error bound for Problem (LO-OC), which provides an estimate of the distance between any point from a certain subset of ${\rm St}(d,K)$ to the set of limiting critical points of Problem (LO-OC) using the map $R$ introduced in (17). As we shall see, such an error bound plays a crucial role in determining the KŁ exponent at the limiting critical points of Problem (LO-OC).

where $\bar{\mathcal{Q}}_{\bm{q}}=\bm{U}_{\bm{A}}\mathcal{Q}_{\bm{q}}\bm{V}_{\bm{A}}^{T}=\{\bm{U}_{\bm{A}}\bm{W}\bm{V}_{\bm{A}}^{T}:\bm{W}\in\mathcal{Q}_{\bm{q}}\}$ and

It is worth noting that error bounds of similar nature have been extensively used to study the convergence behavior of various iterative methods; see, e.g., for some recent developments. Thus, Theorem 4 can be of independent interest.

it suffices to establish (38) for the case where $\bm{A}$ has the block structure given in (21) (in particular, we have $\bm{U}_{\bm{A}}=\bm{I}_{d}$, $\bm{V}_{\bm{A}}=\bm{I}_{K}$, and $\bar{\mathcal{Q}}_{\bm{q}}=\mathcal{Q}_{\bm{q}}$). In view of the structure of $\mathcal{Q}_{\bm{q}}$ given in (35), a natural idea is to first consider the partition $\bm{Q}=\begin{bmatrix}\bm{Q}_{1}&\bm{Q}_{2}\\ \bm{Q}_{3}&\bm{Q}_{4}\end{bmatrix}\in{\rm St}(d,K)$ as in (24) and observe that

Then, it suffices to bound each of the terms on the right-hand side of (39) separately. Let us begin by dispensing with the easy cases.

We first prove (41). Using the block structures of $\bm{A}$ in (21) and $\bm{Q}$ in (24) and the fact that $\bm{Q}_{1}^{T}\bm{Q}_{1}+\bm{Q}_{3}^{T}\bm{Q}_{3}=\bm{I}_{r}$, we compute

This, together with the definition of $\widetilde{\bm{A}}$, implies that

Using the fact that $\bm{Q}_{1}^{T}\bm{Q}_{1}+\bm{Q}_{3}^{T}\bm{Q}_{3}=\bm{I}_{r}$ and invoking (44), (45), we obtain

Next, we prove (42). Let $\bm{Q}_{4}=\bm{U}_{4}\bm{\Sigma}_{4}\bm{V}_{4}^{T}$ be a thin SVD of $\bm{Q}_{4}$, where $\bm{\Sigma}_{4}=\operatorname{Diag}(\sigma_{1},\dots,\sigma_{K-r})$ with $\sigma_{1}\geq\cdots\geq\sigma_{K-r}\geq 0$ being the singular values of $\bm{Q}_{4}$, $\bm{U}_{4}\in{\rm St}(d-r,K-r)$, and $\bm{V}_{4}\in\mathcal{O}^{K-r}$. Noting that the left-hand side of (42) is an instance of the orthogonal Procrustes problem , we have

Using the facts that (i) $(1-x)^{2}\leq(1-x)^{2}(1+x)^{2}$ for any $x\geq 0$, (ii) $\bm{Q}_{2}^{T}\bm{Q}_{2}+\bm{Q}_{4}^{T}\bm{Q}_{4}=\bm{I}_{K-r}$, and (iii) $\|\bm{Q}_{2}\|\leq\|\bm{Q}\|\leq 1$, we obtain

Now, it remains to bound $\operatorname{dist}^{2}(\bm{Q}_{1},\mathcal{Q}_{\bm{q}}^{1})$. The following technical lemma, whose proof can be found in Appendix A, will be useful for that purpose. Recall that $\delta_{ij}=\tfrac{a_{s_{i}}}{a_{s_{j}}}-\tfrac{a_{s_{j}}}{a_{s_{i}}}$ for $i,j\in\{1,\ldots,p\}$; $i\not=j$.

Based on the block structure of $\bm{Q}_{1}$ in (24) and the definition of $\mathcal{Q}_{\bm{q}}^{1}$ in (40), we have

where the second inequality follows from classic perturbation results for eigenvalues of symmetric matrices (see, e.g., [37, Corollary 4.10]) and the third follows the fact that the sign of $\lambda_{k}(\bm{U}_{i}\operatorname{Diag}(\bm{q}_{i})\bm{U}_{i}^{T})$ with $\bm{q}_{i}\in\{\pm 1\}^{h_{i}}$ is different from that of $\lambda_{k}^{(h_{i})}$. This implies that $\operatorname{dist}(\bm{Q},\mathcal{Q}_{\bm{q}})\geq 1$, which contradicts our assumption that $\operatorname{dist}(\bm{Q},\mathcal{Q}_{\bm{q}})<1$.

for $i=1,\ldots,p$. Let us turn to bound $\sum_{i=1}^{p}\|\bm{I}_{h_{i}}-\widetilde{\bm{Q}}_{h_{i}h_{i}}^{T}\widetilde{\bm{Q}}_{h_{i}h_{i}}\|_{F}^{2}$. Observe that with $\Delta_{h_{i}h_{i}}=\bm{Q}_{h_{i}h_{i}}-\bm{Q}_{h_{i}h_{i}}^{T}$ for $i=1,\ldots,p$, we have

where the second-to-last inequality follows from the fact that $\|\bm{Q}_{h_{i}h_{i}}\|\leq 1$ and $\|\Delta_{h_{i}h_{i}}\|\leq 2\|\bm{Q}_{h_{i}h_{i}}\|\leq 2$, and the last inequality follows from (46). Continuing, we bound

where the second inequality follows from the fact that $\{\bm{I}_{h_{j}}-\sum_{i=1}^{p}\bm{Q}_{h_{i}h_{j}}^{T}\bm{Q}_{h_{i}h_{j}}\}_{j=1}^{p}$ are the diagonal blocks of $\bm{I}_{r}-\bm{Q}_{1}^{T}\bm{Q}_{1}$ and the last is due to $\bm{Q}_{1}^{T}\bm{Q}_{1}+\bm{Q}_{3}^{T}\bm{Q}_{3}=\bm{I}_{r}$, $\|\bm{Q}_{3}\|\leq 1$, and $\|\bm{Q}_{h_{i}h_{j}}\|\leq 1$ for $i,j\in\{1,\ldots,p\}$.

Upon putting (49)–(53) together and invoking (41) and (47), we obtain (48). This completes the proof. ∎

We now have all the ingredients to finish the proof of Theorem 4.

Let $\bm{q}\in\{\pm 1\}^{r}$ be given. Using (39) and the results in Propositions 4 and 5, we get

for any $\bm{Q}\in{\rm St}(d,K)$ satisfying $\operatorname{dist}(\bm{Q},\mathcal{Q}_{\bm{q}})<1$. This implies (38), as desired. ∎

2.3 From Error Bound to KŁ Exponent

Once we have the local error bound (38), it is rather straightforward to determine the KŁ exponent at the limiting critical points of Problem (LO-OC). We remark that although there are works showing how various error bounds can be used to determine the KŁ exponent for a host of optimization problems (see, e.g., ), they do not cover our problem setting and hence the results therein cannot be applied directly.

Next, we claim that $g$ is constant on $\bar{\mathcal{Q}}_{\bm{q}}$. Indeed, for any $\bm{W}\in\bar{\mathcal{Q}}_{\bm{q}}$, we have

where the first equality is due to the fact that $\bm{W}\in{\rm St}(d,K)$; the second inequality uses the SVD of $\bm{A}$ in (20); the third inequality follows from the definition of $\bm{\Sigma}_{\bm{A}}$ (cf. (21) and (23)), the fact that $\bm{U}_{\bm{A}}^{T}\bm{W}\bm{V}_{\bm{A}}\in\mathcal{Q}_{\bm{q}}$, and the definition of $\mathcal{Q}_{\bm{q}}$ in (35). Upon noting that the rightmost expression does not depend on $\bm{W}$, the claim is established. In particular, we obtain $g(\bm{Q}^{*})=g(\widetilde{\bm{Q}}^{*})$.

Since $\widetilde{\bm{Q}}^{*}\in\mathcal{Q}$, we have $\bm{A}=\widetilde{\bm{Q}}^{*}\bm{A}^{T}\widetilde{\bm{Q}}^{*}$ by Proposition 1, which implies that $\bm{A}=\widetilde{\bm{Q}}^{*}(\widetilde{\bm{Q}}^{*})^{T}\bm{A}$ (see (27)). It follows that

where the first inequality follows from the Cauchy-Schwarz inequality and the fact that $\|\widetilde{\bm{Q}}^{*}\|\leq 1$; the second inequality follows from the assumption that $\operatorname{dist}(\bm{Q},\bar{\mathcal{Q}}_{\bm{q}})=\|\bm{Q}-\widetilde{\bm{Q}}^{*}\|_{F}$ and Theorem 4; the last inequality follows from Proposition 1. Recalling that $g(\bm{Q}^{*})=g(\widetilde{\bm{Q}}^{*})$, we establish Theorem 3 with $\eta_{g}=(2\kappa^{2}\|\bm{A}\|)^{-1/2}$ and $\epsilon_{g}<1$. ∎

3 Completing the Proof

We are now ready to achieve our original goal of characterizing the KŁ exponent for Problems (5) and (7).

Next, recall that the objective function $h$ of Problem (7) takes the form $h(\bm{P},\bm{Q})=-\langle\bm{P},\bm{X}^{T}\bm{Q}\rangle+\delta_{\mathcal{B}(n,K)}(\bm{P})+\delta_{{\rm St}(d,K)}(\bm{Q})$. Let $\bm{Z}^{*}=(\bm{P}^{*},\bm{Q}^{*})\in\mathcal{B}(n,K)\times{\rm St}(d,K)$ be a limiting critical point of $h$. Furthermore, let $\bm{Z}=(\bm{P},\bm{Q})\in\mathcal{B}(n,K)\times{\rm St}(d,K)$ be such that $\|\bm{Z}-\bm{Z}^{*}\|_{F}\leq\epsilon_{h}$ with $\epsilon_{h}<1$. Since $\|\bm{P}-\bm{P}^{*}\|_{F}\leq\|\bm{Z}-\bm{Z}^{*}\|_{F}<1$ and $\bm{P},\bm{P}^{*}\in\mathcal{B}(n,K)$, we have $\bm{P}=\bm{P}^{*}$. Moreover, we have

by [2, Proposition 2.1]. This, together with the fact that $(\bm{0},\bm{0})\in\partial h(\bm{P}^{*},\bm{Q}^{*})$, implies that $\bm{0}\in-\bm{X}\bm{P}^{*}+\mathcal{N}_{{\rm St}(d,K)}(\bm{Q}^{*})$; i.e., $\bm{Q}^{*}$ is a limiting critical point of the function $\bm{Q}\mapsto h(\bm{P}^{*},\bm{Q})$. Hence, by Theorem 3, there exists an $\eta_{h}>0$ such that

Convergence Analysis of PAMe

Our goal in this section is to prove Theorem 2, which concerns the convergence behavior of our proposed method PAMe (Algorithm 1). Towards that end, we first combine the characterization of the KŁ exponent for Problem (7) in Theorem 1 with the abstract convergence results for descent methods in to establish the linear convergence of PAMe to a limiting critical point $(\bm{P}^{*},\bm{Q}^{*})$ of Problem (7). Then, by noting that $(\bm{P}^{*},\bm{Q}^{*})$ is a solution to certain generalized equation, we obtain a sufficient condition for $\bm{Q}^{*}$ to be a critical point of Problem (5).

We note that similar potential functions have previously been used in the convergence analysis of iterative methods with inertial terms/extrapolation steps; see, e.g., . The following result shows that if the step sizes and extrapolation parameters in PAMe are suitably chosen, then there exists a $\beta>0$ such that the sequence $\{\Psi_{\beta}(\bm{P}^{k},\bm{Q}^{k},\bm{Q}^{k-1})\}_{k\geq 0}$ satisfies the two conditions mentioned earlier.

Consider the setting of Theorem 2. Let $\bm{C}^{k}=(\bm{P}^{k},\bm{Q}^{k},\bm{Q}^{k-1})$ for $k\geq 0$. Then, the following hold (recall that $\beta_{*}$ is given in Theorem 2):

The sequence $\{\bm{C}^{k}\}_{k\geq 0}$ is bounded.

There exists a constant $\kappa_{1}>0$ such that for $k\geq 0$,

There exists a constant $\kappa_{2}>0$ such that for $k\geq 0$,

The proof of (a) is immediate, as $\bm{C}^{k}\in\mathcal{B}(n,K)\times{\rm St}(d,K)\times{\rm St}(d,K)$ for $k\geq 0$ and both $\mathcal{B}(n,K)$ and ${\rm St}(d,K)$ are bounded.

To prove (b), we first observe from the updates (10) and (9) that

Let $\bm{\Delta}_{\bm{P}}^{k+1}=\bm{P}^{k+1}-\bm{P}^{k}$ and $\bm{\Delta}_{\bm{Q}}^{k+1}=\bm{Q}^{k+1}-\bm{Q}^{k}$ for $k\geq 0$. Since $\bm{E}^{k}=\bm{Q}^{k}+\gamma_{k}(\bm{Q}^{k}-\bm{Q}^{k-1})$, it follows that

where the second inequality uses the fact that $2\langle\bm{A},\bm{B}\rangle\leq\rho\|\bm{A}\|_{F}^{2}+\|\bm{B}\|_{F}^{2}/\rho$ for any $\rho>0$. Now, by letting $\kappa_{1}=\min\left\{\alpha_{*}(1-\gamma^{*})/2,\beta_{*}/4\right\}>0$, we obtain

Lastly, let us prove (c). Again, using the updates (10) and (9), we have

By adapting the proof of [2, Proposition 2.1], we obtain

This, together with (56) and (57), implies that

By taking $\kappa_{2}=\left(\max\{3{\alpha^{*}}^{2},(\beta^{*}-\beta_{*})^{2}+\beta_{*}^{2}+3\|\bm{X}\|^{2}\}\right)^{1/2}$, we obtain

2 Linear Convergence of PAMe and Properties of Limit Points

Proposition 6 shows that the sequence $\{\bm{C}^{k}\}_{k\geq 0}$ is bounded and satisfies both the sufficient decrease and relative error conditions with respect to the potential function $\Psi_{\beta}$. Thus, a natural next step is to study the convergence behavior of the sequence $\{\bm{C}^{k}\}_{k\geq 0}$ with respect to the potential function $\Psi_{\beta}$ and then use the result to deduce the convergence behavior of the sequence $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ with respect to the objective function $h$ of Problem (7). To begin, let us prove two technical lemmas. The first establishes a relationship between the limiting critical points of $h$ and $\Psi_{\beta}$.

Thus, if $\beta>0$ and $(\bm{0},\bm{0},\bm{0})\in\partial\Psi_{\beta}(\bm{P},\bm{Q},\bm{Q}^{\prime})$, then we must have $\bm{Q}=\bm{Q}^{\prime}$. Moreover, we have $(\bm{0},\bm{0},\bm{0})\in\partial\Psi_{\beta}(\bm{P},\bm{Q},\bm{Q})$ if and only if

By (54), the latter condition holds if and only if $(\bm{0},\bm{0})\in\partial h(\bm{P},\bm{Q})$. ∎

The second is motivated by the update of the block variable $\bm{P}$ in Algorithm 1 and shows that a limit point of the sequence $\{\bm{P}^{k}\}_{k\geq 0}$ satisfies certain fixed-point inclusion.

Let $\alpha>0$ be given. Suppose that the sequences $\{\bm{P}^{k}\}_{k\geq 0}$ and $\{\bm{Y}^{k}\}_{k\geq 0}$ satisfy

Let $i\in\{1,\ldots,n\}$ and $j\in\{1,\ldots,K\}$ be arbitrary. If $\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha=0$, then $\operatorname{sgn}(\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha)=\{-1,1\}$ by definition. Since $\bm{P}^{*}\in\mathcal{B}(n,K)$, we have $\bm{P}_{ij}^{*}\in\operatorname{sgn}(\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha)$. On the other hand, if $\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha\not=0$, then the assumption that $\bm{P}^{k}\rightarrow\bm{P}^{*}$, $\bm{Y}^{k}\rightarrow\bm{Y}^{*}$ implies $\operatorname{sgn}(\bm{P}_{ij}^{k}+\bm{Y}_{ij}^{k}/\alpha)=\operatorname{sgn}(\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha)$ for all sufficiently large $k\geq 0$. As $\bm{P}^{k+1}\in\operatorname{sgn}(\bm{P}^{k}+\bm{Y}^{k}/\alpha)$ for $k\geq 0$, we conclude that $\bm{P}_{ij}^{*}=\operatorname{sgn}(\bm{P}_{ij}^{*}+\bm{Y}_{ij}^{*}/\alpha)$. This establishes the first claim.

We are now ready to establish the main convergence result for our proposed method PAMe.

Recall from Theorem 1 that the objective function $h$ of Problem (7) has a KŁ exponent of $1/2$ at any of its limiting critical points. Hence, by [20, Theorem 3.6] and Lemma 2, for any $\beta>0$, the potential function $\Psi_{\beta}$ has a KŁ exponent of $1/2$ at any of its limiting critical points. It then follows from [20, Lemma 2.1] that $\Psi_{\beta}$ has a KŁ exponent of $1/2$ at any $(\bm{P},\bm{Q},\bm{Q}^{\prime})\in\operatorname{dom}(\partial\Psi_{\beta})$. This, together with the results in Proposition 6, allows us to invoke [3, Theorem 2.9] to conclude that under the setting of Theorem 2, the sequence $\{\bm{C}^{k}\}_{k\geq 0}$ converges to a limiting critical point $(\bm{P}^{*},\bm{Q}^{*},\bm{Q}^{*})$ of the potential function $\Psi_{\beta_{*}}$. Moreover, by [2, Theorem 3.4], the rate of convergence is at least linear. It follows from Lemma 2 that the sequence $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ converges at least linearly to the limiting critical point $(\bm{P}^{*},\bm{Q}^{*})$ of Problem (7).

Now, suppose that $\alpha_{k}=\alpha_{*}$ for $k\geq 0$ in Algorithm 1. According to the update (11), the sequence $\{(\bm{P}^{k},\bm{Q}^{k})\}_{k\geq 0}$ satisfies $\bm{P}^{k+1}\in\operatorname{sgn}(\bm{P}^{k}+\bm{X}^{T}\bm{E}^{k}/\alpha_{*})$, where $\bm{E}^{k}=\bm{Q}^{k}+\gamma_{k}(\bm{Q}^{k}-\bm{Q}^{k-1})$. Since $(\bm{P}^{k},\bm{Q}^{k})\rightarrow(\bm{P}^{*},\bm{Q}^{*})$ and $(\bm{P}^{*},\bm{Q}^{*})$ is a limiting critical point of $h$, we have $\bm{0}\in-\bm{X}\operatorname{sgn}(\bm{P}^{*}+\bm{X}^{T}\bm{Q}^{*}/\alpha_{*})+\mathcal{N}_{{\rm St}(d,K)}(\bm{Q}^{*})$ by (54) and the result in Lemma 3; i.e., $\bm{Q}^{*}$ is a solution to the generalized equation (15). In particular, noting that $\bm{P}^{*}\in\mathcal{B}(n,K)$, if $\alpha_{*}$ satisfies (16), then $\operatorname{sgn}(\bm{P}^{*}+\bm{X}^{T}\bm{Q}^{*}/\alpha_{*})\subseteq\operatorname{sgn}(\bm{X}^{T}\bm{Q}^{*})$. Consequently, we obtain $\bm{0}\in-\bm{X}\operatorname{sgn}(\bm{X}^{T}\bm{Q}^{*})+\mathcal{N}_{{\rm St}(d,K)}(\bm{Q}^{*})$, which, in view of (6), shows that $\bm{Q}^{*}$ is a critical point of Problem (5). Conversely, let $\bar{\bm{Q}}$ be a critical point of Problem (5) that satisfies $\bm{0}\in-\bm{X}\bm{P}^{*}+\mathcal{N}_{{\rm St}(d,K)}(\bar{\bm{Q}})$ and $\bm{P}^{*}\in\operatorname{sgn}(\bm{X}^{T}\bar{\bm{Q}})$. By Lemma 3, we have $\bm{P}^{*}\in\operatorname{sgn}(\bm{P}^{*}+\bm{X}^{T}\bar{\bm{Q}}/\alpha_{*})$. It then follows that $\bar{\bm{Q}}$ is a solution to the generalized equation (15). ∎

Numerical Results

The parameters of the various algorithms are set as follows. To be fair, we employ the same step sizes when updating the block variables $\bm{P}$ and $\bm{Q}$ in all the PA(L)M-type methods. Specifically, for the two synthetic instances, we set $(\alpha_{k},\beta_{k})=(10^{-5},10^{3})$ and $(\alpha_{k},\beta_{k})=(10^{-5},10^{2})$ for $k\geq 0$, respectively; for the real-world instance, we set $(\alpha_{k},\beta_{k})=(10^{-6},20)$ for $k\geq 0$. The step size for updating the block variable $\bm{Q}$ in pDCAe is set as $\beta_{k}=1$ for $k\geq 0$. There is no need to choose any step size for FPM. Next, we specify the extrapolation parameters in the PA(L)M-type methods. For PAMe, we set the extrapolation parameter as $1$ for $k\geq 0$. Although such a choice may violate the condition in Theorem 2, it works effectively in our experiments. For iPALM, we set the extrapolation parameters when updating the block variables $\bm{P}$ and $\bm{Q}$ both as $\tfrac{k-1}{k+2}$ for $k\geq 1$. Such a choice is motivated by the numerical results in . For GiPALM, we set the extrapolation parameters when updating the block variables $\bm{P}$ and $\bm{Q}$ as $1/2$ and $1/4$ for $k\geq 0$, respectively. For pDCAe, we set the extrapolation parameter when updating the block variable $\bm{Q}$ using the fixed restart scheme as suggested in with the fixed restart interval $\bar{T}=10$. In each test, we adopt the same starting point for all the algorithms and terminate them when the Frobenius norm of the difference of two consecutive iterates is less than $10^{-8}$.

We plot the function value gap $h(\bm{P}^{k},\bm{Q}^{k})-h(\bm{P}^{*},\bm{Q}^{*})$ and the iterate gap $\|\bm{Q}^{k}-\bm{Q}^{*}\|_{F}$ against the iteration number for each tested method in Figures 1 and (2), respectively, where $(\bm{P}^{*},\bm{Q}^{*})$ is the last iterate of the tested method. It can be observed that for all the tested methods, both the sequence of function value gaps and the sequence of iterate gaps converge linearly. In particular, the convergence performance of PAMe supports our linear convergence result in Theorem 2. Moreover, our numerical results demonstrate that PAMe converges substantially faster than the standard PAM method and also faster than FPM, pDCAe, iPALM, and GiPALM.

To compare the quality of the solution returned by each method, we use the total explained variation (TEV) measure as in , which in our setting is given by

Here, $\bm{q}_{i}$ is the $i$-th column of the solution returned by the tested method and $\bar{\bm{q}}_{i}$ is the $i$-th leading eigenvector of $\bm{X}^{T}\bm{X}$. Table 1 summarizes the TEV of the tested methods. It can be observed that the performance of PAMe is comparable to those of the other methods.

2 Application to Clustering on a Subspace

The step sizes used by the PA(L)M-type methods are listed in Table 2. The step size for updating the block variable $\bm{Q}$ in pDCAe is given by $\beta_{k}$ in Table 2. We use the same extrapolation parameters for PAMe, pDCAe, iPALM, and GiPALM as those in Subsection 5.1. We terminate the tested methods when either the number of iterations reaches 1000 or the Frobenius norm of the difference of two consecutive iterates is less than $10^{-6}$. To compare the computational efficiency and clustering accuracy of the tested methods, we record their CPU times and ratios of correctly clustered points, averaged over 10 randomly chosen initial points, in Tables 3 and 4, respectively. It can be observed that the CPU time consumed by PAMe is generally less than those consumed by the other methods on the tested data sets, especially on rcv1.binary, real-sim, and w8a. Moreover, the clustering accuracy of PAMe is comparable to those of the other methods. These demonstrate the efficiency and efficacy of PAMe when performing clustering on a subspace.

Concluding Remarks

References

Appendix A Proof of Lemma 1

Following the derivation in (45) and using the fact that $\|\bm{Q}_{1}\|\leq\|\bm{Q}\|\leq 1$, we have

Now, the block structures of $\widetilde{\bm{A}}^{T}\bm{Q}_{1}$ and $\bm{Q}_{1}^{T}\widetilde{\bm{A}}$ in (28) and the ordering of the singular values of $\bm{A}$ in (22) imply that

Recalling that $\delta_{ij}=\tfrac{a_{s_{i}}}{a_{s_{j}}}-\tfrac{a_{s_{j}}}{a_{s_{i}}}$ for $i,j\in\{1,\ldots,p\}$; $i\not=j$ and using (A) and (60), we bound

Similar to the derivation of (58), we have

where the second inequality follows from (45) and the fact that $\langle\widetilde{\bm{A}}\bm{Q}_{1}^{T},\bm{Q}_{1}\widetilde{\bm{A}}^{T}\rangle=\langle\bm{Q}_{1}^{T}\widetilde{\bm{A}},\widetilde{\bm{A}}^{T}\bm{Q}_{1}\rangle$. Putting (58), (61), and (62) together, we obtain (47).