Abstract
We introduce a partial proximal point algorithm for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints. The inner subproblems, reformulated as a system of semismooth equations, are solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint non-degeneracy condition, together with the strong semi-smoothness property of the singular value thresholding operator. Numerical experiments on a variety of problems including those arising from low-rank approximations of transition matrices show that our algorithm is efficient and robust.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Let \(\mathfrak {R}^{p\times q}\) be the space of all \(p\times q\) matrices equipped with the standard trace inner product \(\langle X, Y \rangle = \text{ Tr }(X^TY)\) and its induced Frobenius norm \(\Vert \cdot \Vert \). Without loss of generality, we assume \(p\le q\) throughout this paper. For a given \(X\in \mathfrak {R}^{p\times q}\), its nuclear norm \(\Vert X\Vert _{*}\) is defined as the sum of all its singular values and its operator norm \(\Vert X\Vert _2\) is the largest singular value. Let \(\mathcal{S}^n\) be the space of all \(n\times n\) symmetric matrices and \(\mathcal{S}^n_+\) be the cone of symmetric positive semidefinite matrices. We use the notation \(X\succeq 0\) to denote that \(X\) is a symmetric positive semidefinite matrix.
In this paper, we are interested in solving the following nuclear norm regularized matrix least squares problem with linear equality and inequality constraints:
where \(\mathcal {A}:\mathfrak {R}^{p\times q}\rightarrow \mathfrak {R}^m\) and \(\mathcal {B} :\mathfrak {R}^{p\times q}\rightarrow \mathfrak {R}^s\) are linear maps, \(C\in \mathfrak {R}^{p\times q}, b\in \mathfrak {R}^m, d\in \mathfrak {R}^{s}\), \(\rho \) is a given positive parameter, and \(\mathcal {Q} = {\{0\}}^{s_1}\times \mathfrak {R}_{+}^{s_2}\) is a polyhedral convex cone with \(s= s_1 + s_2\). In many applications, we need to find a low rank approximation of a given target matrix while preserving certain structures. The nuclear norm function has been widely used as a regularizer which favors a low rank solution of (1). Chu et al. [12] addressed some theoretical and numerical issues concerning structured low rank approximation problems. In many data analysis problems, the collected empirical data, possibly contaminated by noise, usually do not have the specified structure or the desired low rank. So it is important to find the nearest low rank approximation of the given matrix while maintaining the underlying structure of the original system. In practice, the data to be analyzed is very often nonnegative such as those corresponding to concentrations or intensity values, and it would be preferable to take into account such structural constraints.
Our nuclear norm regularized matrix least squares problem (1) arises from the recent intensive studies of the following affine rank minimization problem:
The problem (2) has many applications in diverse fields, see, e.g., [1, 2, 10, 47]. However, this affine rank minimization problem is generally an NP-hard nonconvex optimization problem. A tractable heuristic introduced in [20, 21] is to minimize the nuclear norm over the same constraints as in (2):
The nuclear norm function is the greatest convex function majorized by the rank function over the unit ball of matrices with operator norm at most one, and it has been widely used as a surrogate for promoting the low rank structure. A frequently used alternative to (3) for accommodating problems with noisy data is the following matrix least squares problem with nuclear norm regularization (see [38, 55]):
It is known that (3) can be equivalently reformulated as a semidefinite programming (SDP) problem (see [47]), which has one \((p+q)\times (p+q)\) semidefinite constraint and \(m\) linear equality constraints. One can use standard interior-point method based semidefinite programming solvers such as SeDuMi [52] and SDPT\(3\) [54] to solve this SDP problem. However, these solvers are not suitable for problems with large \(p+q\) or \(m\) since in each iteration of these solvers, a large and dense Schur complement equation must be solved even when the data is sparse.
To overcome the difficulties faced by interior-point methods, several algorithms have been proposed to solve (3) or (4) directly. In [9], a singular value thresholding (SVT) algorithm is proposed for solving the following Tikhonov regularized version of (3):
where \(\tau \) is a given positive regularization parameter. The SVT algorithm is a gradient method applied to the dual problem of (5). In [38], a fixed point continuation (FPC) algorithm is proposed for solving (4), together with a Bregman iterative algorithm for solving (3). Their numerical results on randomly generated matrix completion problems demonstrated that the FPC algorithm is much more efficient than the semidefinite programming solver SDPT3 when low accuracy solutions are sought. Toh and Yun [55] proposed an accelerated proximal gradient algorithm (APG), which terminates in \(O(1/\sqrt{\varepsilon })\) iterations for achieving \(\varepsilon \)-optimality, to solve the unconstrained matrix least squares problem (4). Their numerical results show that the APG algorithm is highly efficient and robust in solving large-scale random matrix completion problems. Liu et al. [35] considered the following nuclear norm minimization problem with linear and second order cone constraints:
where \(\mathcal {K} = \{0\}^{m_1} \times \mathcal {K}^{m_2}\), and \(\mathcal {K}^{m_2}\) stands for the \(m_2\)-dimensional second order cone. They developed three inexact proximal point algorithms (PPA) in primal, dual and primal-dual forms with comprehensive convergence analysis, built upon the classic results of the general PPA established by Rockafellar [49]. Their numerical results demonstrated the efficiency and robustness of these PPAs in solving randomly generated and real matrix completion problems. Moreover, they showed that the SVT algorithm [9] is just one outer iteration of the exact primal PPA, and the Bregman iterative method [38] is a special case of the exact dual PPA. However, all the above mentioned models and related algorithms cannot address the following goal: given an observed data matrix (possibly contaminated by noise), find the nearest low rank approximation of the target matrix while maintaining certain prescribed structures. In particular, the APG method considered in [55] cannot be applied directly to solve the problem (1).
A strong motivation for proposing the model (1) arises from finding the nearest low rank approximation of transition matrices. For a given data matrix \(P\) which describes the full distribution of a random walk through the entire data set, the problem of finding the low rank approximation of \(P\) can be stated as follows:
where \(e\in \mathfrak {R}^n\) is the vector of all ones and \(X\ge 0\) denotes the condition that all entries of \(X\) are nonnegative. Lin [34] proposed the Latent Markov Analysis (LMA) approach for finding the reduced rank approximations of transition matrices. The LMA is applied to clustering such that the inferred cluster relationships can be described probabilistically by the reduced-rank transition matrix. Chennubhotla [11] exploited the spectral properties of the Markov transition matrix to obtain low rank approximation of the original transition matrix in order to develop a fast eigen-solver for spectral clustering. Furthermore, in many applications, since only partial information of the original transition matrix is available, it is also important to estimate the missing entries of \(P\). For example, transition probabilities between different credit ratings play a crucial role in credit portfolio management. If our primary interest is in a specific group, then the number of observed rating transitions might be very small. Due to the lack of rating data, it is important to estimate the rating transition matrix in the presence of missing data [4].
In this paper, we study a partial proximal point algorithm (PPA) proposed by Ha [30] for solving (1), in which only some of the variables appear in the quadratic proximal term. The partial PPA was further analyzed by Bertsekas and Tseng [6], in which the close relation between the partial PPA and some parallel algorithms in convex programming was revealed. Given a sequence of parameters \(\sigma _k\) such that
and an initial point \(X^0\in \mathfrak {R}^{p\times q}\), a sequence \(\{(u^k, X^k)\}\subseteq \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\) is generated by the partial PPA for solving (1) via the following scheme:
where \(\displaystyle f_\rho (u, X) := \frac{1}{2}\Vert u\Vert ^2 + \rho \Vert X\Vert _{*} + \langle C, X \rangle \). Since the nuclear norm \(\Vert \cdot \Vert _{*}\) is a nonsmooth function, an important issue we must address is how to solve (9) efficiently. The strong convexity of the objective function suggests to us to apply an indirect method for solving (9) based on the duality theory for convex programming. We note that the proposed partial PPA requires solving an inner subproblem with linear inequality constraints at each iteration. To handle the inequality constraints, Gao and Sun [24] recently designed a quadratically convergent inexact smoothing Newton method to solve semidefinite least squares problems with equality and inequality constraints but with simple quadratic objective functions of the form \(\frac{1}{2}\Vert X-G\Vert ^2\). Their numerical results demonstrated the high efficiency of the inexact smoothing Newton method. This strongly motivated us to use an inexact smoothing Newton method to solve our inner subproblems for achieving fast convergence. For the inner subproblem, due to the presence of inequality constraints, we reformulate the problem as a system of semismooth equations. By defining a smoothing function of the soft thresholding operator, we introduce an inexact smoothing Newton method to solve the semismooth system. The quadratic convergence of the inexact smoothing Newton method is proved under a constraint nondegeneracy condition, together with the strong semismoothness property of the soft thresholding operator.
The remaining parts of this paper are organized as follows. In Sect. 2, we present some preliminaries about semismooth functions. We show that the soft thresholding operator is strongly semismooth everywhere, and define a smoothing function of the soft thresholding operator. In Sect. 3, we design a partial PPA for solving the nuclear norm regularized matrix least squares problem (1), and establish its global and local convergence. Section 4 follows with the design of an inexact smoothing Newton method for solving the inner subproblems. The quadratic convergence of the method is established under a constraint nondegeneracy condition, which we also characterized. We report the numerical implementation and performance of our algorithm in Sect. 5 and give the conclusion in Sect. 6.
2 Preliminaries
In this section, we give a brief introduction on some basic concepts such as semismooth functions, the B-subdifferential and Clarke’s generalized Jacobian of Lipschitz functions. We shall show that the soft thresholding operator is strongly semismooth everywhere. These concepts and properties will be critical for us to develop an inexact smoothing Newton method for solving the inner subproblems in our partial PPA.
Let \(F:\mathfrak {R}^m \longrightarrow \mathfrak {R}^l\) be a locally Lipschitz function. By Rademacher’s theorem, \(F\) is Fréchet differentiable almost everywhere. Let \(D_F\) denote the set of points in \(\mathfrak {R}^m\) where \(F\) is differentiable. The B-subdifferential of \(F\) at \(x\in \mathfrak {R}^m\) is defined by
where \(F^{\prime }(x)\) denotes the Jacobian of \(F\) at \(x\in D_F\). Then Clarke’s [14] generalized Jacobian of \(F\) at \(x\in \mathfrak {R}^m\) is defined as the convex hull of \(\partial _B F(x)\), i.e.,
From [46, Lemma 2.2 ], we know that if \(F\) is directionally differentiable in a neighborhood of \(x\in \mathfrak {R}^m\), then for any \(h\in \mathfrak {R}^m\), there exists \(\mathcal {V} \in \partial F(x)\) such that \(F^{\prime }(x; h) = \mathcal {V}h\). The following concept of semismoothness was first introduced by Mifflin [40] for functionals and was extended by Qi and Sun [46] to vector-valued functions.
Definition 2.1
We say that a locally Lipschitz function \(F:\mathfrak {R}^m \longrightarrow \mathfrak {R}^l\) is semismooth at \(x\) if
-
1.
\(F\) is directionally differentiable at \(x\); and
-
2.
for any \(h\in \mathfrak {R}^m\) and \(V\in \partial F(x+h)\) with \(h\rightarrow 0\), \(F(x+h)- F(x) - Vh = o(\Vert h\Vert ).\)
Furthermore, F is said to be strongly semismooth at \(x\) if \(F\) is semismooth at \(x\) and for any \(h\in \mathfrak {R}^m\) and \(V\in \partial F(x+h)\) with \(h\rightarrow 0\), \( F(x+h)- F(x) - Vh = O(\Vert h\Vert ^2). \)
Let \(K\) be a closed convex cone in a finite dimensional real Euclidean space \(\mathcal {X}\) equipped with a scalar inner product \(\langle \cdot , \cdot \rangle \) and its induced norm \(\Vert \cdot \Vert \). Let \(\Pi _K: \mathcal {X}\rightarrow \mathcal {X}\) denote the metric projector over \(K\), i.e., for any \(y\in \mathcal {X}\), \(\Pi _K(y)\) is the unique optimal solution to the following convex optimization problem:
It is well known [60] that the metric projector \(\Pi _K(\cdot )\) is Lipschitz continuous with modulus \(1\) and \(\Vert \Pi _K(\cdot )\Vert ^2\) is continuously differentiable. Hence, \(\Pi _K(\cdot )\) is almost everywhere Fréchet differentiable in \(\mathcal {X}\) and for every \(y\in \mathcal {X}\), \(\partial \Pi _K(y)\) is well defined. For any \(X \in \mathcal{S}^n\), let \(X_+ = \Pi _{S_{+}^n}(X)\) be the metric projection of \(X\) onto \(S_+^n\) under the standard trace inner product. Assume that \(X\) has the following spectral decomposition
where \(\Lambda \) is the diagonal matrix of eigenvalues and \(P\) is a corresponding orthogonal matrix of eigenvectors. Then
where \(\Lambda _{+}\) is a diagonal matrix whose diagonal entries are the nonnegative parts of the respective diagonal entries of \(\Lambda \). The strong semismoothness of \(\Pi _{S_{+}^n}(\cdot )\) has been proved by Sun and Sun in [53].
Next, we shall show that the soft thresholding operator [9, 35] is strongly semismooth everywhere. Let \(Y\in \mathfrak {R}^{p\times q}\) admit the following singular value decomposition (SVD):
where \(U\in \mathfrak {R}^{p\times p}\) and \(V \in \mathfrak {R}^{q\times q}\) are orthogonal matrices, \(\Sigma =\mathrm{Diag} (\sigma _1, \ldots , \sigma _p)\) is the diagonal matrix of singular values of \(Y\), with \(\sigma _1 \ge \sigma _2 \ge \cdots \ge \sigma _p\ge 0\). Define \(s: \mathfrak {R}\rightarrow \mathfrak {R}\) by
For each threshold \(\rho >0\), the soft thresholding operator \(D_\rho \) is defined as follows:
where \(\Sigma _\rho =\mathrm{Diag} (s(\sigma _1), \ldots , s(\sigma _p))\). Decompose \(V\in \mathfrak {R}^{q\times q}\) as \( V \, =\, [V_1 \ \ V_2 ]\, , \) where \(V_1\in R^{q\times p}\) and \(V_2\in {\mathfrak {R}}^{q\times (q-p)}\). Let the orthogonal matrix \(Q\in {\mathfrak {R}}^{(p+q)\times (p+q)}\) be defined by
and \(\Xi : {\mathfrak {R}}^{p\times q} \rightarrow \mathcal{S}^{p+q}\) be defined by
By [28, Section 8.6], we know that \(\Xi (Y)\) has the following spectral decomposition:
i.e., the eigenvalues of \(\Xi (Y)\) are \(\pm \sigma _i , i=1,\ldots , p,\) and \(0\) of multiplicity \(q-p.\)
For any \(W= P\mathrm{Diag}(\lambda _1, \ldots , \lambda _{p+q})P^T\in \mathcal{S}^{p+q}\), define \(\widehat{S}: \mathcal{S}^{p+q} \rightarrow \mathcal{S}^{p+q}\) by
Then, by the strong semismoothness property of \((\cdot )_+ : \mathcal{S}^{p+q} \rightarrow \mathcal{S}^{p+q}\), we have that \(\widehat{S}(\cdot )\) is strongly semismooth everywhere in \(\mathcal{S}^{p+q}\). By direct calculations, we have
Thus we have the following theorem.
Theorem 2.1
The function \(D_{\rho }(\cdot )\) is strongly semismooth everywhere in \(\mathfrak {R}^{p\times q}\).
Proof
Let \(Y\in \mathfrak {R}^{p\times q}\) admit the SVD as in (10). Notice that \(\widehat{S}(\cdot )\) is strongly semismooth in \(\mathcal{S}^{p+q}\). This, together with (16), proves that \(D_{\rho }(\cdot )\) is strongly semismooth at \(Y\). Since \(Y\) is arbitrarily chosen, we have that \(D_{\rho }(\cdot )\) is strongly semismooth everywhere in \(\mathfrak {R}^{p\times q}\).
\(\square \)
For the convenience of later discussion, we define the following three index sets:
For each \(\rho >0\), the index set \(\alpha \) is further decomposed into the following subindex sets:
In the following, we show that all the elements of the generalized Jacobian \(\partial D_\rho (\cdot )\) are self-adjoint and positive semidefinite. First we prove the following lemma.
Lemma 2.1
Let \(Y \in \mathfrak {R}^{p\times q}\) admit the SVD as in (10). Then the unique minimizer of the following problem
is \(X^{*}=\Pi _{B_\rho }(Y) = U [\min (\Sigma , \rho ) \ 0] V^T\), where \(\min (\Sigma , \rho ) = \mathrm{Diag}(\min (\sigma _1,\rho ),\dots ,min(\sigma _p,\rho ))\).
Proof
Obviously problem (19) has an unique optimal solution which is equal to \(\Pi _{B_\rho }(Y)\). For any feasible \(Z\) with the SVD as in (10), we have \(\sigma _i(Z)\le \rho ,\ i=1, \ldots , p\). Since \(\Vert \cdot \Vert \) is unitarily invariant, by [7, Exercise IV.3.5], we have that
Since \(\Vert Y-X^{*}\Vert ^2 = \sum _{i \in \alpha _1} (\sigma _{i}(Y)-\rho )^2,\) we have \(\Vert Y-Z\Vert ^2\ge \Vert Y-X^{*}\Vert ^2 \quad \mathrm for any Z \in B_\rho .\) Thus \(X^{*}= U [\min (\Sigma , \rho ) \ 0] V^T\) is the unique optimal solution. \(\square \)
Note that the above lemma has also been proved in [44] with a different proof. From the above lemma, we have that \(D_\rho (Y) = Y -\Pi _{B_\rho }(Y)\), which implies that \(\Pi _{B_\rho }(\cdot )\) is also strongly semismooth everywhere in \(\mathfrak {R}^{p\times q}\).
Now, we shall show that even though the soft thresholding operator \(D_\rho (\cdot )\) is not differentiable everywhere, \(\Vert D_\rho (\cdot )\Vert ^2\) is continuously differentiable. First we summarize some well-known properties of the Moreau–Yosida [42, 59] regularization. Assume that \(\mathcal {Y}\) is a finite-dimensional real Euclidean space. Let \(f: \mathcal {Y} \rightarrow (-\infty , +\infty ]\) be a proper lower semicontinuous convex function. For a given \(\sigma >0\), the Moreau–Yosida regularization of \(f\) is defined by
It is well known that \(F_{\sigma }\) is a continuously differentiable convex function on \(\mathcal {Y}\) and
where \(x(y)\) denotes the unique optimal solution of (20). It is well known that \(x(\cdot )\) is globally Lipschitz continuous with modulus \(1\) and \(\nabla F_{\sigma }\) is globally Lipschitz continuous with modulus \(1/\sigma \).
Proposition 2.1
Let \(\displaystyle \Theta (Y) = \frac{1}{2}\Vert D_\rho (Y)\Vert ^2\), where \(Y\in \mathfrak {R}^{p\times q}\). Then \(\Theta (Y)\) is continuously differentiable and
Proof
It is already known that the following minimization problem
has the unique optimal solution \(X= D_\rho (Y)\) (see, [9, 38]). From the properties of the Moreau–Yosida regularization, we know that \(D_\rho (\cdot )\) is globally Lipschitz continuous with modulus \(1\) and \(F(Y)\) is continuously differentiable with
Since \(D_\rho (Y)\) is the unique optimal solution, we have that
This, together with (22), implies that \( \Theta (\cdot )\) is continuously differentiable with \(\nabla \Theta (Y) = D_\rho (Y)\). \(\square \)
Next, we shall discuss the smoothing counterpart of the soft thresholding operator \(D_{\rho }(\cdot )\). Let \(\chi (\varepsilon , t): \mathfrak {R}\times \mathfrak {R}\rightarrow \mathfrak {R}\) be the following Huber smoothing function for \((t)_{+}\):
Then the smoothing function for \(s(\cdot )\) in (11) is defined as follows:
Note that \(\overline{s}(\varepsilon , \cdot )\) is an odd function with respect to \(t\in \mathfrak {R}\). Let \(Y\in \mathfrak {R}^{p\times q}\) admit the SVD as in (10). For any \(\varepsilon \in \mathfrak {R}\), the smoothing function for \(S(Y)\) in (16) is defined as follows:
where \(\overline{\Sigma }_{\rho } = \mathrm{Diag}(\overline{s}(\varepsilon , \sigma _1), \ldots , \overline{s}(\varepsilon , \sigma _p))\). By direct calculations, we have
where
is a smoothing function for \(D_{\rho }(Y)\). Note that when \(\varepsilon = 0\), \(\overline{S}(0, Y) = S(Y)\) and \(\overline{D}_{\rho }(0, Y)= D_{\rho }(Y)\). For any \(\lambda = (\lambda _1, \ldots , \lambda _{p+q})^T \in \mathfrak {R}^{p+q}\), let \(\lambda _i = \sigma _i\) for \(i\in \alpha \), \(\lambda _i = -\sigma _{i-p}\) for \(i\in \gamma \), and \(\lambda _i = 0\) for \(i\in \beta \). When \(\varepsilon \ne 0\) or \(\sigma _i \ne \rho , i= 1, \ldots , p\), we use \(\Lambda (\varepsilon , \lambda )\in \mathcal {S}^{p+q}\) to denote the following first divided difference symmetric matrix for \(\overline{s}(\varepsilon , \cdot )\) at \(\lambda \)
whose \((i,j)\)-th entry is given by
Since \(\overline{s}(\varepsilon , \cdot )\) is an odd function, we have the following results:
and \((\Lambda (\varepsilon , \lambda ))_{ij}\in [0, 1]\) for all \(i,j= 1,\ldots , p+q\).
Proposition 2.2
Let \(Y\) admit the SVD in (10). If \(\varepsilon \ne 0\) or \(\sigma _i \ne \rho , i= 1, \ldots , p\), then \(\overline{D}(\cdot ,\cdot )\) is continuously differentiable around \((\varepsilon ,Y)\), and for any \((\tau , H)\in \mathfrak {R}\times \mathfrak {R}^{p\times q}\), it holds that
where \(H_1=U^T H V_1\), \(H_2=U^T H V_2\), with \(H_1^s = (H_1 + H_1^T)/{2}\), \(H_1^a = (H_1 - H_1^T)/{2}\), and
Furthermore, by [37], \(\overline{D}_{\rho }(\cdot , \cdot )\) is globally Lipschitz continuous and strongly semismooth at any \((0, Y)\in \mathfrak {R}\times \mathfrak {R}^{p\times q}\).
Proof
By the well known result of Löwner [36], we know that for any \(H\in \mathfrak {R}^{p\times q}\),
where “\(\circ \)” denotes the Hadamard product. Since
by simple algebraic calculations, we have that
where \( A_{12} = U\left( \Lambda _{\alpha \alpha }\circ H_1^s + \Lambda _{\alpha \gamma }\circ H_1^a \right) V_1^T + U(\Lambda _{\alpha \beta } \ \circ H_2) V_2^T. \) When \(\varepsilon \ne 0\) or \(\sigma _i \ne \rho , i= 1, \ldots , p\), the partial derivative of \(\overline{S}(\cdot , \cdot )\) with respect to \(\varepsilon \) can be computed by
Since for any \((\tau , H) \in \mathfrak {R}\times \mathfrak {R}^{p\times q}\),
we have the required result in (29). Thus, \(\overline{D}_{\rho }(\cdot , \cdot )\) is continuously differentiable around \((\varepsilon , Y)\in \mathfrak {R}\times \mathfrak {R}^{p\times q}\) if \(\varepsilon \ne 0\) or \(\sigma _i \ne \rho , i= 1, \ldots , p\). \(\square \)
Next, we will give a characterization of the generalized Jacobian \(\partial \overline{D}_\rho (0, Y)\) for \((0, Y)\in \mathfrak {R}\times \mathfrak {R}^{p\times q}\). Let \(\mathcal {D}\) be the set of points in \(\mathfrak {R}\times \mathfrak {R}^{p\times q}\) at which \(\overline{D}_\rho \) is differentiable. Suppose that \(\mathcal {N}\) is any set of Lebesgue measure zero in \(\mathfrak {R}\times \mathfrak {R}^{p\times q}\). Then
Note that \(\partial \overline{D}_\rho (0, Y)\) does not depend on the choice of the null set \(\mathcal {N}\) [57, Theorem 4].
Before characterizing \(\partial \overline{D}_\rho (0, Y)\) in the next proposition, we need to introduce a “submap” of \(\overline{D}_\rho \) as follows. Define \((\overline{D}_{\rho })_{|\alpha _2|}: \mathfrak {R}\times \mathfrak {R}^{|\alpha _2|\times |\alpha _2|} \rightarrow \mathfrak {R}^{|\alpha _2|\times |\alpha _2|}\) by replacing the dimension \(p\) and \(q\) in the definition of \(\overline{D}_\rho : \mathfrak {R}\times \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^{p\times q}\) with \(|\alpha _2|\), respectively, where the index set \(\alpha _2\) is defined as in (18). As in the case for \(\overline{D}_\rho (\cdot , \cdot )\), the mapping \((\overline{D}_{\rho })_{|\alpha _2|}(\cdot , \cdot )\) is also Lipschitz continuous. Thus Clarke’s generalized Jacobian \(\partial (\overline{D}_\rho )_{|\alpha _2|}(0, Z)\) for \((0,Z) \in \mathfrak {R}\times \mathfrak {R}^{|\alpha _2|\times |\alpha _2|}\) is well defined. We let \(I_{|\alpha _2|}\) be the identity matrix of size \(|\alpha _2|\).
Proposition 2.3
Let \(Y\in \mathfrak {R}^{p\times q}\) admit the SVD as in (10). Then, for any \(\mathcal {V} \in \partial \overline{D}_\rho (0, Y)\), there exists \(\mathcal {V}_{|\alpha _2|}\in \partial (\overline{D}_\rho )_{|\alpha _2|}(0, \rho I_{|\alpha _2|})\) such that
for all \((\tau , H)\in \mathfrak {R}\times \mathfrak {R}^{p\times q}\), where \(\Omega _{\alpha _1 \alpha _3}, \Gamma _{\alpha \gamma }\) and \(\Gamma _{\alpha \beta }\) are defined as follows,
\(H_1 = U^T H V_1, H_2 = U^T H V_2\), and \(H_1^s = (H_1 + H_1^T)/2\), \(H_1^a = (H_1-H_1^T)/2\).
Proof
Please refer to [33, Proposition 2.9]. \(\square \)
3 A partial proximal point algorithm for matrix least squares problems
In this section, we will describe how to design a partial proximal point algorithm (PPA) to solve the problem (1).
Let \(\mathcal {Z}\) be a finite dimensional real Euclidean space with an inner product \(\langle \cdot , \cdot \rangle \) and its induced norm \(\Vert \cdot \Vert \). Let \(\mathcal {T}: \mathcal {Z} \rightarrow \mathcal {Z}\) be a maximal monotone operator. We define its domain and image, respectively, as follows: \(\mathrm{Dom}\, (\mathcal {T}) : = \{z\in \mathcal {Z} \;|\; \mathcal {T}(z) \ne \emptyset \}\) and \(\mathrm{Im} \, (\mathcal {T}) := \bigcup _{z\in \mathcal {Z}} \mathcal {T}(z).\) Let \(\mathcal {Z} = \mathcal {X}\times \mathcal {Y}\), where \(\mathcal {X}\) and \(\mathcal {Y}\) are two finite dimensional real Euclidean spaces each equipped with a scalar product \(\langle \cdot , \, \cdot \rangle \) and its induced norm \(\Vert \cdot \Vert \). Suppose now that \(z\in \mathcal {Z}\) is partitioned into two components \(z = (x,y)\), where \(x\in \mathcal {X}\) and \(y \in \mathcal {Y}\). Ha [30] proposed a partial PPA to solve the inclusion problem in two variables \(0 \in \mathcal {T}(x,y)\), in which only one of the variables is involved in the proposed iterative procedure. Below we give a brief review of the partial PPA proposed by Ha [30]. Let \(\Pi : \mathcal {X}\times \mathcal {Y} \rightarrow \mathcal {X}\times \mathcal {Y}\) be the orthogonal projection of \( \mathcal {X}\times \mathcal {Y}\) onto \(\{0\}\times \mathcal {Y}\), i.e., \(\Pi (x,y) = (0,y)\). To solve the inclusion problem \(0\in \mathcal {T}(x,y)\), from a given initial point \((x^0, y^0)\in \mathcal {X}\times \mathcal {Y}\), the exact partial PPA generates a sequence \(\{(x^k, y^k)\}\) by the following scheme:
where \(P_{\sigma _k} := (\Pi + \sigma _k \mathcal {T})^{-1}\Pi \) and the sequence \(\{\sigma _k\}\) satisfies (8). In general, the mapping \(P_{\sigma _k}\) is neither single-valued nor nonexpansive. However, by [30, Proposition 2], we know that the second component of \(P_{\sigma _k}(x^k, y^k)\) is uniquely determined and nonexpansive. For practical purpose, the following general approximation criteria were introduced in [30]:
where \((u^{k+1}, v^{k+1}) \in P_{\sigma _k}(x^k, y^k)\). In [30], Ha showed that under mild assumptions, any cluster point of the sequence \(\{(x^k, y^k)\}\) generated by the partial PPA under criterion (40a) is a solution to \(0 \in \mathcal {T}(x,y)\). Moreover, the sequence \(\{y^k\}\) converges weakly to \(\bar{y}\), which is the second component of a solution to \(0 \in \mathcal {T}(x,y)\). If, in addition, (40b) and (40c) are also satisfied and \(\mathcal {T}^{-1}\) is Lipschitz continuous at the origin, then the sequence \(\{(x^k, y^k)\}\) converges locally at least at a linear rate which tends to zero as \(\sigma _k \rightarrow +\infty \). For more discussions of the convergence analysis of the partial PPA, see [30, Theorem 1 and 2].
Next, we shall show how to use the partial PPA to solve (1). It is easy to see that (1) can be rewritten as follows:
Note that the objective function \(f_\rho (u,X)\) is strongly convex in \(u\) for all \(X\in \mathfrak {R}^{p\times q}\). For the convergence analysis, we assume that the following Slater condition holds:
Let \(l(u,X;\zeta ,\xi ): \mathfrak {R}^m \times \mathfrak {R}^{p\times q} \times \mathfrak {R}^m \times \mathfrak {R}^s \rightarrow \mathfrak {R}\) be the ordinary Lagrangian function for (41) in the extended form:
where \(\mathcal {Q}^{*} = \mathfrak {R}^{s_1} \times \mathfrak {R}_{+}^{s_2}\) is the dual cone of \(\mathcal {Q}\). The essential objective function in (41) is
where \(\mathcal {F}_P=\{(u, X)\in \mathfrak {R}^m \times \mathfrak {R}^{p\times q} \ |\ \mathcal {A} (X) + u = b, \mathcal {B}(X) \in d + \mathcal {Q}\}\) is the feasible set of (41). The dual problem of (41) is given by:
where \(g_\rho (\zeta ,\xi ) := - \frac{1}{2}\Vert \zeta \Vert ^2 + \langle b, \zeta \rangle + \langle d, \xi \rangle \). As in Rockafellar [50], we define the following two maximal monotone operators
where \(u\in \mathfrak {R}^m, X\in \mathfrak {R}^{p\times q}, \zeta \in \mathfrak {R}^m,\) and \(\xi \in \mathfrak {R}^s\). Note that since \(f(u,X)\) is strongly convex in \(u\) with modulus \(1\) for all \(X\in \mathfrak {R}^{p\times q}\), \(\mathcal {T}_f\) is strongly monotone with modulus \(1\) with respect to the variable \(u\) [49, Proposition 6], i.e.,
for all \((v, Y)\in \mathcal {T}_f(u,X)\) and \((v^{\prime }, Y^{\prime }) \in \mathcal {T}_f(u^{\prime }, X^{\prime })\). From the definition of \(\mathcal {T}_f\), we know that for any \((v,Y)\in \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\),
Similarly, for any \((v, Y, y, z) \in \mathfrak {R}^{m}\times \mathfrak {R}^{p\times q} \times \mathfrak {R}^{m} \times \mathfrak {R}^{s}\),
Since \(f(u,X)\) is strongly convex in \(u\) for all \(X\in \mathfrak {R}^{p\times q}\), we apply the partial PPA proposed by Ha [30] to the maximal monotone operator \(\mathcal {T}_f\), in which only the variable \(X\) appears in the quadratic proximal term. Given a starting point \((u^0, X^0) \in \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\), the inexact partial PPA generates a sequence \(\{(u^k, X^k)\}\) by approximately solving the following problem
We can easily see that any minimizer \((u,X)\) of problem (47) satisfies
Let \(\Pi : \mathfrak {R}^m \times \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\) be the orthogonal projector of \( \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\) onto \(\{0\}\times \mathfrak {R}^{p\times q}\), i.e., \(\Pi (u,X) = (0,X)\). Then (48) can be equivalently written as
It follows that the set of minimizers of (47) can be expressed as \((\Pi + \sigma _k \mathcal {T}_f)^{-1} \Pi (u^k,X^k)\).
Next, for any parameter \(\sigma >0\), we show some properties of the mappings \(Q_\sigma := (\Pi + \sigma \mathcal {T}_f)^{-1}\) and \(P_\sigma := Q_\sigma \Pi = (\Pi + \sigma \mathcal {T}_f)^{-1} \Pi \). The proofs essentially follow the ideas in [32, Proposition 2 and 3] together with [16, Theorem 2.7], and we shall omit them.
Proposition 3.1
For any given parameter \(\sigma >0\), let \(Q_\sigma = (\Pi + \sigma \mathcal {T}_f)^{-1}\), and \(P_\sigma = Q_\sigma \Pi = (\Pi + \sigma \mathcal {T}_f)^{-1} \Pi \). Suppose that \(\mathrm{Dom}\, (\mathcal {T}_f) \ne \emptyset \). Then we have the following properties:
-
(i)
The mapping \(Q_\sigma \) and \(P_\sigma \) are single-valued in \(\mathfrak {R}^m \times \mathfrak {R}^{p\times q}\).
-
(ii)
Let \(\beta = \min \{1, \sigma \}\). For any \((u,X), (u^{\prime }, X^{\prime }) \in \mathfrak {R}^m \times \mathfrak {R}^{p\times q}\),
$$\begin{aligned} \Vert Q_\sigma (u,X) - Q_\sigma (u^{\prime }, X^{\prime })\Vert&\le \frac{1}{\beta } \Vert (u,X) - (u^{\prime }, X^{\prime })\Vert , \\ \Vert P_\sigma (u,X) - P_\sigma (u^{\prime }, X^{\prime })\Vert&\le \frac{1}{\beta } \Vert X - X^{\prime }\Vert . \end{aligned}$$
Since the operator \(P_{\sigma _k}\) is single-valued, the approximate rule of the partial PPA for solving problem (41) can be expressed as
where \(P_{\sigma _k}(u^k, X^k)\) is defined by
Now we calculate the partial quadratic regularization of \(f\) in (50), which plays a key role in the study of the partial PPA for solving (41). For a given parameter \(\sigma >0\), the partial quadratic regularization of \(f\) in (44) associated with \(\sigma \) is given by
From (44), we have
where the interchange of \(\min _{u, Y}\) and \(\sup _{\zeta , \xi }\) follows from the growth properties in \((u, Y)\) [48, Theorem 37.3] and the third equality follows from (43). Thus we have
where
In the above,
and the last equality follows from (23). By the saddle point theorem [48, Theorem 28.3] and (52), we have that for any \((\zeta (X), \xi (X))\) such that
\((\zeta (X), D_{\rho \sigma }(W(\zeta (X),\xi (X); X)))\) is the unique solution to (51).
Now we formally present the partial PPA for solving (41).
Suppose that \((\bar{\zeta }(X^k), \bar{\xi }(X^k))\) is an optimal solution of the inner subproblem (55) for each \(X^k\). Let \(P_{\sigma _k}\) be defined as in (50). In order to terminate (55) in the above PPA, we introduce the following stopping criteria:
Note that \(F_{\sigma _k}(X^k) = \sup \theta _{k}(\zeta ,\xi )\) and \( \theta _{k}(\zeta ^{k+1},\xi ^{k+1}) = \Theta _{\sigma _k}(\zeta ^{k+1},\xi ^{k+1}; X^k)\). The following result reveals the relation between the estimation (56) and (40), which enables us to apply the convergence results of the partial PPA in [30, Theorem 1 & 2] to our partial PPA. The proof essentially follows the idea in [50, Proposition 6].
Proposition 3.2
Suppose that \((\bar{\zeta }(X^k), \bar{\xi }(X^k))\) is an optimal solution of (55). Let \((\bar{u}^{k+1}, \overline{X}^{k+1}) = (\bar{\zeta }(X^k), D_{\rho \sigma _k}(W(\bar{\zeta }(X^k),\bar{\xi }(X^k); X^k)))\) and \(X^{k+1}= D_{\rho \sigma _k}(W(\zeta ^{k+1}, \xi ^{k+1}; X^k))\). Then one has
Proof
Since \(\Theta _{\sigma }(\zeta ,\xi ; X)\) is convex in \(X\) and \(\nabla _X \Theta _{\sigma _k}(\zeta ^{k+1},\xi ^{k+1}; X^k) = (X^k - X^{k+1})/{\sigma _k}, \) the following inequality holds for any \(Y \in \mathfrak {R}^{p\times q}\):
We also know that
which together with (58) and the fact that \( \theta _{k}(\zeta ^{k+1},\xi ^{k+1}) = \Theta _{\sigma _k}(\zeta ^{k+1},\xi ^{k+1}; X^k)\), implies that
Since this inequality holds for all \(Y \in \mathfrak {R}^{p\times q}\), by taking the maximum of (60) in \(Y\), we have
which proves our assertion. \(\square \)
3.1 Convergence analysis of the partial PPA
In this subsection, we show the global convergence and local convergence of the partial PPA for solving (41), mainly based upon the convergence results of Ha [30, Theorem 1 & 2], which require the condition (62) in the following proposition. The purpose of this proposition is to give a sufficient condition for (62) to hold.
Proposition 3.3
Consider the function \(f(u,X)\) defined in (44). Suppose that for some \(\lambda >0\), the following parameterized problem perturbed by \((v, Y)\in \mathfrak {R}^m\times \mathfrak {R}^{p\times q}\)
has an optimal solution whenever \(\max \{\Vert v\Vert , \Vert Y\Vert \}\le \lambda \). Then we have
Proof
Since for each \((v, Y)\in \mathfrak {R}^m\times \mathfrak {R}^{p\times q}\) such that \(\max \{\Vert v\Vert , \Vert Y\Vert \}\le \lambda \), the parameterized problem (61) has an optimal solution \((\bar{u}, \overline{X})\), we have that
which implies that \((v, Y) \in \partial f(\bar{u}, \overline{X})\subseteq \; \mathrm{Im}\, (\mathcal {T}_f)\). Therefore, we have \(0 \in \mathrm{int \, Im}\, (\mathcal {T}_f)\).
\(\square \)
Remark 3.1
In many applications, we have \(C=0\) in the objective function \(f_{\rho }(u, X)\) (see the examples in Sect. 5). In this case, the function \(f_\rho (u, X)\) perturbed by \((v, Y)\in \mathfrak {R}^m\times \mathfrak {R}^{p\times q}\) with \(\Vert Y\Vert _2 < \rho \), is coercive. This is because we have
Therefore, if \(C = 0\), the parameterized problem (61) has an optimal solution for any \((v, Y)\in \mathfrak {R}^m\times \mathfrak {R}^{p\times q}\) such that \(\max \{\Vert v\Vert , \Vert Y\Vert \} \le \lambda \) for some \(0 < \lambda < \rho \).
Theorem 3.1
(Global convergence) Suppose that the condition in Proposition 3.3 is satisfied. Let the partial PPA be executed with the stopping criterion (56a) and (56b). Then the generated sequence \(\{(u^k, X^k)\}\) is bounded and converges to an optimal solution \((\bar{u}, \overline{X})\) of (41), and \(\{(\zeta ^k, \xi ^k)\}\) is asymptotically minimizing for the dual problem (45) with
where \(\mathrm{asym}\, \sup (D)\) is the asymptotic supremum of (45). If the problem (41) satisfies the Slater condition (42), then the sequence \(\{(\zeta ^k, \xi ^k)\}\) is also bounded, and all of its accumulation points are optimal solutions for the problem (45).
Proof
Under the given assumption, we have from Proposition 3.3 that \(0 \in \mathrm{int \, Im}\, (\mathcal {T}_f)\). Moreover, we know from Proposition 3.2 that (56a) and (56b) implies the general stopping criterion (40a) for \(\mathcal {T}_f\). It follows from [30, Theorem 1] that the sequence \(\{(u^k, X^k)\}\) is bounded and any of its weak cluster point is an optimal solution to (41) and \(X^k \rightarrow \overline{X}\). Since \(f_{\rho }(u, X)\) is strongly convex with respect to \(u\), the \(u\)-component of the optimal solution is uniquely determined, which implies that \(\{u^k\} \rightarrow \bar{u}\). Thus the sequence \(\{(u^k, X^k)\}\) converges to an optimal solution \((\bar{u}, \overline{X})\) of (41). The rest of the proof follows the arguments as in [49, Theorem 4] and we omit it here. \(\square \)
Theorem 3.2
(Local convergence) Suppose that the hypotheses in Proposition 3.3 are satisfied. Let the partial PPA be executed with the stopping criterion (56a), (56b), (56c) and (56d). If \(\mathcal {T}_f^{-1}\) is Lipschitz continuous at the origin with modulus \(a_f\), then \(\{(u^k, X^k)\}\) converges to the unique optimal solution \((\bar{u}, \overline{X})\) of (41), and
where
Moreover, the conclusions of Theorem 3.1 about \(\{(\zeta ^k, \xi ^k)\}\) are valid.
If in addition to (56c), (56d) and the condition on \(\mathcal {T}_{f}^{-1}\), one has (56e) and \(\mathcal {T}_{l}^{-1}\) is Lipschitz continuous at the origin with modulus \(a_{l}\, (\ge a_f)\), then \((\zeta ^k, \xi ^k) \rightarrow (\bar{\zeta }, \bar{\xi })\), where \((\bar{\zeta }, \bar{\xi })\) is the unique optimal solution for (45), and one has
where \(\eta ^{\prime }_k = a_l (1+ \delta _k^{\prime })/\sigma _k \rightarrow \eta ^{\prime }_{\infty } = a_l/\sigma _\infty \).
Proof
Since it follows from Proposition 3.2 that (56c) and (56d) implies the general stopping criterion (40b) and (40c), we can easily obtain the first part of the theorem from Theorem 3.1 and the general results in [30, Theorem 2]. The second part of the theorem can similarly be obtained by following the argument in [50, Theorem 5]. We omit it here. \(\square \)
4 An inexact smoothing Newton method for solving inner subproblems
In this section, we design an inexact smoothing Newton method for solving the inner subproblem (55), which is the most expensive step in each iteration of the partial PPA. Here we assume that there are inequality constraints in (41). If there are only equality constraints, then (55) is an unconstrained problem, and a semismooth Newton-CG method similar to the one proposed in [61] can be designed to solve (55); we refer the reader to [33] for the details.
For later convenience, we let
In our partial PPA, for some fixed \(X\in \mathfrak {R}^{p\times q}\) and \(\sigma >0\), we need to solve the following form of the inner subproblem:
where \(T = [I_m, 0; 0, 0] \in \mathfrak {R}^{(m+s)\times (m+s)}, W(y;X) = X-\sigma (C- \widehat{\mathcal {A}}^{*}y)\) and \(\widehat{\mathcal {A}}^{*} = (\mathcal {A}^{*},\, \mathcal {B}^{*})\) is the adjoint of \(\widehat{\mathcal {A}}\). Note that \(-\varphi (\cdot )\) is the objective function of the inner subproblem (55). The function \(\varphi (\cdot )\) in (68) is continuously differentiable with
Since \(\varphi (\cdot )\) is a convex function, \(\bar{y}= (\bar{\zeta }; \bar{\xi })\in \mathcal {K}\) solves problem (68) if and only if it satisfies the following variational inequality
Define \(F: \mathfrak {R}^{m+s} \rightarrow \mathfrak {R}^{m+s}\) by
Then one can easily prove that \(\bar{y}\in \mathcal {K}\) solves (69) if and only if \(F(\bar{y}) = 0\) [17]. Thus, solving the inner problem (68) is equivalent to solving the following equation
Since both \(\Pi _{\mathcal {K}}(\cdot )\) and \(D_{\rho \sigma }(\cdot )\) are globally Lipschitz continuous, \(F\) is globally Lipschitz continuous. For the purpose of introducing an inexact smoothing Newton method, we need to define a smoothing function for \(F(\cdot )\).
The smoothing function for the soft thresholding operator \(D_{\rho \sigma }(\cdot )\) has been defined by (27) where the threshold value is equal to \(\rho \sigma \). Next, we need to define the smoothing function for \(\Pi _\mathcal {K}(\cdot )\). For simplicity, we shall use the Huber smoothing function \(\chi \) defined in (24). Let \(\pi :\mathfrak {R}\times \mathfrak {R}^{m+s} \rightarrow \mathfrak {R}^{m+s}\) be defined by
The function \(\pi \) is obviously continuously differentiable around any \((\varepsilon , z)\in \mathfrak {R}\times \mathfrak {R}^{m+s}\) as long as \(\varepsilon \ne 0\) and is strongly semismooth everywhere.
Now, we are ready to define a smoothing function for \(F(\cdot )\). Let
From the definitions of \(\Upsilon , \pi ,\) and \(\overline{D}_{\rho \sigma }\), we have that \(F(y)= \Upsilon (0,y)\) for any \(y\in \mathfrak {R}^{m+s}\).
Proposition 4.1
The mapping \(\Upsilon \) be defined by (73) has the following properties:
-
(i)
\(\Upsilon \) is globally Lipschitz continuous on \(\mathfrak {R}\times \mathfrak {R}^{m+s}\).
-
(ii)
\(\Upsilon \) is continuously differentiable around \((\varepsilon , y)\) when \(\varepsilon \ne 0\). For any fixed \(\varepsilon \in \mathfrak {R}\), \(\Upsilon (\varepsilon , \cdot )\) is a \(P_0\)-function, i.e., for any \((y,z)\in \mathfrak {R}^{m+s}\times \mathfrak {R}^{m+s}\) with \(y\ne z\),
$$\begin{aligned} \max _{y_i\ne z_i} (y_i - z_i)(\Upsilon _i(\varepsilon , y) - \Upsilon _i(\varepsilon , z))\ge 0, \end{aligned}$$(74)and thus for any fixed \(\varepsilon \ne 0\), \(\Upsilon _y^{\prime }(\varepsilon , y)\) is a \(P_0\)-matrix (i.e., all its principal minors are nonnegative).
-
(iii)
\(\Upsilon \) is strongly semismooth at \((0,y)\). In particular, for any \(\varepsilon \downarrow 0\) and \(\mathfrak {R}^{m+s} \ni h \rightarrow 0\) we have
$$\begin{aligned} \Upsilon (\varepsilon , y+h) - \Upsilon (0, y) - \Upsilon ^{\prime }(\varepsilon , y+h)(\varepsilon , h) = O(\Vert (\varepsilon , h)\Vert ^2). \end{aligned}$$ -
(iv)
For any \(h\in \mathfrak {R}^{m+s}\),
$$\begin{aligned} \partial \Upsilon (0, y)(0,h)&\subseteq h - \partial \pi (0, y- \nabla \varphi (y)) (0, h \\&\quad -(Th+ \sigma \widehat{\mathcal {A}} \partial \overline{D}_{\rho \sigma }(0,W(y;X))(0, \widehat{\mathcal {A}}^{*}h))). \end{aligned}$$
Proof
Please refer [33, Proposition 3.9]. \(\square \)
Now we are ready to introduce the inexact smoothing Newton method, which was developed by Gao and Sun in [24], for solving the nonsmooth equation of the form (71). Let \(\kappa \in (0,\infty )\) be a constant. Define \(G:\mathfrak {R}\times \mathfrak {R}^{m+s}\rightarrow \mathfrak {R}^{m+s}\) by
where \(\Upsilon : \mathfrak {R}\times \mathfrak {R}^{m+s}\rightarrow \mathfrak {R}^{m+s}\) is defined by (73). Note that \(G_y^{\prime }(\varepsilon , y)\) is a \(P\)-matrix (i.e., all its principal minors are positive) for any \((\varepsilon \ne 0, y) \in \mathfrak {R}\times \mathfrak {R}^{m+s}\), and hence it is nonsingular, while by part \((ii)\) of Proposition 4.1, \(\Upsilon _y^{\prime }(\varepsilon , y)\) is only a \(P_0\)-matrix which may be singular. Define \(E: \mathfrak {R}\times \mathfrak {R}^{m+s} \rightarrow \mathfrak {R}\times \mathfrak {R}^{m+s}\) by
For any \((\varepsilon \ne 0, y) \in \mathfrak {R}^{m+s}\), \(E^{\prime }(\varepsilon , y)\) is a \(P\)-matrix, and hence it is nonsingular. Then solving the nonsmooth equation \(F(y) = 0\) is equivalent to solving the following smoothed equation
The inexact smoothing Newton method that is used to solve the above equation is described in Fig. 1.
Algorithm 2 (An inexact smoothing Newton method)
Let
where \({\varsigma (\varepsilon , y)} = r\min \{1,\Vert E(\varepsilon ,y)\Vert ^2\}\) and \(\hat{\varepsilon } > 0\) is given. From [24, Theorem 4.1 and Theorem 3.6], we have the following convergence results for the inexact smoothing Newton method. For more details on the inexact smoothing Newton method, see [24].
Theorem 4.1
Algorithm \(2\) is well defined and generates an infinite sequence \(\{(\varepsilon ^k ,y^k)\}\in \mathcal {N}\) with the properties that any accumulation point \((\bar{\varepsilon }, \bar{y})\) of \(\{(\varepsilon ^k ,y^k)\}\) is a solution of \(E(\varepsilon , y) = 0\) and \(\text{ lim } _{k \rightarrow \infty } \Vert E(\varepsilon ^k, y^k)\Vert ^2= 0\). Additionally, if the Slater condition (42) holds, then \(\{(\varepsilon ^k ,y^k)\}\) is bounded.
Theorem 4.2
Let \((\bar{\varepsilon }, \bar{y})\) be an accumulation point of the infinite sequence \(\{(\varepsilon ^k ,y^k)\}\) generated by Algorithm \(2\). Suppose that \(E\) is strongly semismooth at \((\bar{\varepsilon }, \bar{y})\) and that all \(\mathcal {V} \in \partial E(\bar{\varepsilon }, \bar{y})\) are nonsingular. Then the sequence \(\{(\varepsilon ^k ,y^k)\}\) converges to \((\bar{\varepsilon }, \bar{y})\) quadratically, i.e., for \(k\) sufficiently large
Suppose that the Slater condition (42) holds. Let \((\bar{\varepsilon }, \bar{y})\) be an accumulation point of the sequence \(\{(\varepsilon ^k, y^k)\}\) generated by Algorithm \(2\). Then, we know that \(\bar{\varepsilon } = 0\) and \(F(\bar{y}) = 0,\) which means that \(\bar{y} = (\bar{\zeta } ; \bar{\xi }) \in \mathcal {K}\) is an optimal solution to the inner subproblem (68). Let \(\overline{X} := D_{\rho \sigma }(W(\bar{y}; X))\). Then \((\bar{\zeta }, \overline{X})\) is the unique optimal solution to the problem (51).
For the quadratic convergence of Algorithm \(2\), we need the concept of constraint nondegeneracy. For a given closed set \(K \subseteq \mathcal {X}\), we let \(T_K(x)\) be the tangent cone of \(K\) at \(x\in K\) as in convex analysis [48]. The largest linear space contained in \(T_K(x)\) is denoted by \(\mathrm{lin}(T_K(x))\), which is equal to \((-T_K(x))\cap T_K(x)\). Define \(g: \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}\) by \(g(X) = \Vert X\Vert _{*}\). Let \(K_{p,q}\) be the epigraph of \(g\), i.e.,
which is a closed convex cone. Let \(\widehat{\mathcal {B}} := (\mathcal {B}, \, 0)\). Then (1) can be rewritten in the following form:
It is easy to see that \(\overline{X}\) is an optimal solution for (1) if and only if \((\overline{X}, \bar{t})\) is an optimal solution to (79) with \(\bar{t} = \Vert \overline{X}\Vert _{*}\). Let \(\mathcal {I}\) be the identity map from \(\mathfrak {R}^{p\times q} \times \mathfrak {R}\) to \(\mathfrak {R}^{p\times q} \times \mathfrak {R}\). Then the constraint nondegeneracy condition is said to hold at \((\overline{X}, \bar{t})\) if
Note that \(\mathrm{lin}(T_{\mathcal {Q}}(\widehat{\mathcal {B}}(\overline{X}, \bar{t}) - d)) = \mathrm{lin}(T_{\mathcal {Q}}(\mathcal {B}(\overline{X}) - d))\). Let \(\mathcal {E}(\overline{X})\) be the index set of active constraints at \(\overline{X}\):
and \(l : =|\mathcal {E}(\overline{X})|\). Without loss of generality, we assume that
Define \(\widetilde{\mathcal {B}}: \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^{s_1+l}\) by
Let \(\overline{\mathcal {B}} = (\widetilde{\mathcal {B}}, \, 0)\). Since \(\mathrm{lin}(T_{\mathcal {Q}}(\mathcal {B}(X) - d))\) can be computed directly as follows
(80) can be reduced to
which is equivalent to
Next, we shall characterize the linear space \(\mathrm{lin}(T_{K_{p,q}}(\overline{X}, g(\overline{X})))\). Let \(W(\bar{y};X)\) admit the SVD as in (10). Decompose the index set \(\alpha =\{1,\ldots , p\}\) into the following three subsets:
Then \(U = [U_{\alpha _1}\ U_{\alpha _2} \ U_{\alpha _3}], V=[V_{\alpha _{1}} \ V_{\alpha _2}\ V_{\alpha _3} \; V_2]\), and \(\overline{X} = D_{\rho \sigma }(W(\bar{y};X))\) is of rank \(|\alpha _1|\). For any \(H \in \mathfrak {R}^{p\times q}\), by the results of Watson [58, Theorem 1], we have
From [14, Proposition 2.3.6 and Theorem 2.4.9], we have
from which we can readily get
Thus its linearity space is as follows:
Let
which is a subspace of \(\mathfrak {R}^{p\times q}\). The orthogonal complement of \(\mathcal {T}(\overline{X})\) is given by
Since \(\overline{\mathcal {B}} = (\widetilde{\mathcal {B}}, \, 0)\), the constraint nondegeneracy condition (81) can be further reduced to
Lemma 4.1
Let \(W(\bar{y}; X)= X-\sigma (C-\widehat{\mathcal {A}}^{*}\bar{y})\) admit the SVD as in (10). Then the constraint nondegeneracy condition (82) holds at \(\overline{X}=D_{\rho \sigma }(W(\bar{y}; X))\) if and only if for any \(h\in \mathfrak {R}^{s_1+l}\),
Proof
Please refer to [33, Lemma 3.12]. \(\square \)
Lemma 4.2
Let \(\widetilde{\mathcal {A}} = (\mathcal {A}; \widetilde{\mathcal {B}})\) and \(\widetilde{\mathcal {A}}^{*} = (\mathcal {A}^{*}, \, \widetilde{\mathcal {B}}^{*})\) be the adjoint of \(\widetilde{\mathcal {A}}\). Let \(\overline{D}_{\rho \sigma }:\mathfrak {R}\times \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^{p\times q}\) be defined by (27). Assume that the constraint nondegeneracy condition (82) holds at \(\overline{X}\). Then for any \(\mathcal {V} \in \partial \overline{D}_{\rho \sigma }(0, W(\bar{y}; X))\), we have
where \(\widetilde{T} = [I_m, 0; 0, 0]\) is a matrix of size \(m+s_1+l\).
Proof
Please refer to [33, Lemma 3.13]. \(\square \)
Proposition 4.2
Let \(\Upsilon : \mathfrak {R}\times \mathfrak {R}^{m+s} \rightarrow \mathfrak {R}^{m+s}\) be defined by (73). Assume that the constraint nondegeneracy condition (82) holds at \(\overline{X}\). Then for any \(\mathcal {W}\in \partial \Upsilon (0, \bar{y})\), \(\mathcal {W}\) is a \(P\)-matrix, i.e.,
Proof
Let \(\mathcal {W}\in \partial \Upsilon (0, \bar{y})\). Suppose that there exists \(0\ne h \in \mathfrak {R}^{m+s}\) such that (85) does not hold, i.e.,
Then from part \((iv)\) of Proposition 4.1, we know that there exist \(\mathcal {D}\in \partial \pi (0, \bar{z})\) and \(\mathcal {V}\in \partial \overline{D}_{\rho \sigma }(0,W(\bar{y};X))\) such that
where \(\bar{z} = \bar{y}- (T\bar{y} + \widehat{\mathcal {A}}\overline{D}_{\rho \sigma }(0, W(\bar{y};X))-\hat{b})\). By simple calculations, we can find a nonnegative vector \(d\in \mathfrak {R}^{m+s}\) satisfying
such that for any \(y\in \mathfrak {R}^{m+s}\),
Thus we have \( h_i(\mathcal {W}(0,h))_i = h_i\left[ h_i -d_ih_i + d_i\left( Th + \sigma \widehat{\mathcal {A}} \mathcal {V}(0, \widehat{\mathcal {A}}^{*}h)\right) _i\right] , \; i=1,\ldots , m+s. \) This, together with (86), implies that
Hence, \( \langle h, Th + \sigma \widehat{\mathcal {A}} \mathcal {V}(0, \widehat{\mathcal {A}}^{*}h \rangle = \langle \tilde{h}, \widetilde{T}\tilde{h} + \sigma \widetilde{\mathcal {A}} \mathcal {V}(0, \widetilde{\mathcal {A}}^{*}\tilde{h}\rangle \le 0, \) where \(0\ne \tilde{h}\in \mathfrak {R}^{m+s_1+l}\) is defined by \(\tilde{h}_i = h_i, i= 1,\ldots , m+s_1+l\). However, the above inequality contradicts (84) in Lemma 4.2. Hence, we have that (85) holds. \(\square \)
Theorem 4.3
Let \((\bar{\varepsilon }, \bar{y})\) be an accumulation point of the infinite sequence \(\{(\varepsilon ^k ,y^k)\}\) generated by Algorithm \(2\). Assume that the constraint nondegeneracy condition (82) holds at \(\overline{X}\). Then the sequence \(\{(\varepsilon ^k ,y^k)\}\) converges to \((\bar{\varepsilon }, \bar{y})\) quadratically, i.e., for \(k\) sufficiently large
Proof
To prove the quadratic convergence of \(\{(\varepsilon ^k ,y^k)\}\), by Theorem 4.2, it is enough to show that \(E\) is strongly semismooth at \((\bar{\varepsilon }, \bar{y})\) and all \(\mathcal {V}\in \partial E(\bar{\varepsilon }, \bar{y})\) are nonsingular. The strong semismoothness of \(E\) at \((\bar{\varepsilon }, \bar{y})\) follows from part \((iii)\) of Proposition 4.1 and the fact that the modulus function \(|\cdot |\) is strongly semismooth everywhere on \(\mathfrak {R}\).
Next, we show the nonsingularity of all elements in \(\partial E(\bar{\varepsilon }, \bar{y})\). For any \(\mathcal {V}\in \partial E(\bar{\varepsilon }, \bar{y})\), from Proposition 4.2 and the definition of \(E\), we have that for any \(0\ne h \in \mathfrak {R}^{m+s+1}\), \(\max _i h_i (\mathcal {V}d)_i >0\), which implies that \(\mathcal {V}\) is a \(P\)-matrix, and thus nonsingular [15, Theorem 3.3.4]. \(\square \)
4.1 Efficient implementation of the inexact smoothing Newton method
When applying Algorithm \(2\) to solve the inner subproblem (68), the most expensive step is in solving the linear system (77). In our numerical implementation, we first obtain \(\Delta \varepsilon ^k = - \varepsilon ^k + \varsigma _k \hat{\varepsilon }\), and then apply the BiCGStab iterative solver of Van der Vost [56] to the following linear system
to obtain a \(\Delta y^k\) satisfying condition (78). For convenience, we suppress the superscript \(k\) in our subsequent analysis. By noting that \(G(\varepsilon , y)\) and \(\Upsilon (\varepsilon , y)\) are defined by (75) and (73), respectively, we have that
where \(H = \widehat{\mathcal {A}}^{*}\Delta y\), \(z: = y - (Ty + \widehat{\mathcal {A}}\overline{D}_{\rho \sigma }(\varepsilon , W)-\hat{b})\) and \(W: = X-\sigma (C-\widehat{\mathcal {A}}^{*}y)\). Let \(W\) have the SVD as in (10). Then, by (29), we have
where \(\Lambda _{\alpha \alpha }, \Lambda _{\alpha \gamma }\) and \(\Lambda _{\alpha \beta }\) are given by (28), \(H_1 = U^THV_1\), and \(H_2 = U^THV_2\). When implementing the BiCGStab iterative method, one needs to repeatedly compute the matrix-vector multiplication \(G_y^{\prime }(\varepsilon , y) \Delta y\). From (89), it seems that a full SVD of \(W\) is required. But as we shall explain next, it is not necessary to compute \(V_2\) explicitly. Observe that \(\Lambda _{i,j}=d_i\) for all \(i\in \alpha , j\in \beta \) for some \(d\in \mathfrak {R}^p\). Thus
which shows that the computation in (89) can be done without explicitly using \(V_2\).
To achieve fast convergence for the BiCGStab method, we introduce an easy-to-compute diagonal preconditioner for the linear system (87). Since both \(\pi _z^{\prime }(\varepsilon , z)\) and \(T\) are diagonal matrices, we know from (88) that it is enough to find a good diagonal approximation of \(\widehat{\mathcal {A}} (\overline{D}_{\rho \sigma })_W^{\prime }(\varepsilon , W) \widehat{\mathcal {A}}^{*}\). Let
where \(\mathbf {\widehat{A}}\) and \(\mathbf {S}\) denote the matrix representation of the linear map \(\widehat{\mathcal {A}}\) and \((\overline{D}_{\rho \sigma })_W^{\prime }(\varepsilon , W) \) with respect to the standard bases in \(\mathfrak {R}^{p\times q}\) and \(\mathfrak {R}^{m+s}\), respectively. Let the standard basis in \(\mathfrak {R}^{p\times q}\) be \(\{E^{ij}\in \mathfrak {R}^{p\times q}: 1\le i\le p, 1\le j \le q\}\), where for each \(E^{ij}\), its \((i,j)\)-th entry is one and all the others are zero. Then the diagonal element of \(\mathbf {S}\) with respect to the standard basis \(E^{ij}\) is given by
where \( \widetilde{\Lambda } := \left[ \frac{1}{2}(\Lambda _{\alpha \alpha } +\Lambda _{\alpha \gamma }), \Lambda _{\alpha \beta }\right] \) and \(H_1^{ij} = U^T E^{ij}V_1\). Based on the above expression, the total cost of computing all the diagonal elements of \(\mathbf {S}\) is equal to \(2(p+q)pq + 3p^3q \) flops, which is too expensive if \(p^2\gg p+q\). Fortunately, the first term
is usually a very good approximation of \(\mathbf {S}_{(i,j),(i,j)}\), and the cost of computing all the elements \(\mathbf {d}_{(ij)}\), for \(1\le i\le p, 1\le j\le q\), is \(2(p+q)pq\) flops. Thus we propose the following diagonal preconditioner for the coefficient matrix \(G_y^{\prime }(\varepsilon , y)\):
5 Numerical experiments
In this section, we report some numerical results to demonstrate the efficiency of our smoothing-Newton partial PPA. We implemented our algorithm in MATLAB 2011a (version 7.12), and the numerical experiments are run in MATLAB under Windows 7 operating system on an Intel Xeon (quad-core) 2.80GHz CPU with 24GB memory.
In our numerical implementation, we apply the well-known alternating direction method of multipliers (ADMM) proposed by Gabay and Mercier [23], Glowinski and Marrocco [26], and Glowinski [27], for generating a good starting point for our PPA. To use the ADMM, we introduce two auxiliary variables \(Y\) and \(v\), and consider the following equivalent form of (1):
Consider the following augmented Lagrangian function for the problem (91):
where \(Z\in \mathfrak {R}^{p\times q}\) and \(\lambda \in \mathfrak {R}^s\) are the Lagrangian multipliers for the linear equality constraints and \(\beta >0\) is a penalty parameter. Given a starting point \((X^0, Y^0, v^0,Z^0,\lambda ^0)\), the ADMM generates new iterates according to the following procedure:
where \(\gamma \in (0,(1+\sqrt{5})/2)\) is a given constant. Note that the theoretical convergence for the above procedure is guaranteed; see [27]. However, during our numerical implementation, we observe that the performance of the ADMM is very sensitive to the choice of the penalty parameter \(\beta \). In order to achieve faster convergence, it is essential to adaptively adjust \(\beta \) so as to balance the progress of the primal and dual infeasibilities defined in (92). Let \(\beta _k, R_P^k, R_D^k\) be the value of \(\beta \), and the primal and dual infeasibilities at the \(k\) iteration of the ADMM. In our implementation, we adjust \(\beta \) according to the following rule:
where \(N_k = 3\) if \(k\le 30\); \(N_k=6\) if \(30<k\le 60\); \(N_k=12\) if \(60<k\le 120\); \(N_k = 25\) if \(120<k\le 250\); \(N_k = 50\) if \(250 < k\). Observe that when the parameter \(\beta \) is modified, we are actually restarting a new cycle of ADMM using the iterate from the last cycle as the starting point for the new cycle.
In order to measure the infeasibilities of the primal problem (41), we define two linear operators \(\mathcal {B}_e:\mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^{s_1}\) and \(\overline{\mathcal {B}}_e: \mathfrak {R}^{p\times q} \rightarrow \mathfrak {R}^{s_2}\), respectively, as follows:
Let \(d = (d_{s_1}; d_{s_2})\) where \(d_{s_1}\in \mathfrak {R}^{s_1}\) and \(d_{s_2}\in \mathfrak {R}^{s_2}\). We measure the infeasibilities and optimality for the primal problem (41) and the dual problem (45) as follows:
where \(y = (\zeta ; \xi ), Z = (D_{\rho \sigma }(W) - W)/\sigma \) with \(W = X-\sigma (C-\mathcal{A}^*\zeta -\mathcal{B}^*\xi )\), and \(f_\rho (u,X)\) and \(g_\rho (\zeta ,\xi )\) are the objective functions of (41) and (45), respectively. The infeasibility of the condition \(\Vert Z\Vert _2 \le \rho \) is not checked since it is satisfied up to machine precision throughout the algorithm. In our numerical experiments, we stop the partial PPA when
We choose the initial iterate \(X^0 =0, y^0 = 0\), and \(\sigma _0 = 1\). The parameter \(\rho \) in (1) is set to be \(\rho = 10^{-3}\Vert \mathcal {A}^{*}b\Vert _2\) if the data is not contaminated by noise; otherwise, the parameter \(\rho \) is set to be \(\rho = 5\times 10^{-3}\Vert \mathcal {A}^{*}b\Vert _2\).
In our numerical experiments, we run the ADMM for at most 30 iterations to generate a good starting point for our proposed PPA. In addition, the ADMM is switched to PPA as soon as \(\max \{R_P,R_D\}\) is less than \(10^{-3}\).
5.1 Example 1
We consider the nearest matrix approximation problem which was discussed by Golub, Hoffman and Stewart in [29], where the classic Eckart–Young [18]–Mirsky[41] theorem was extended to obtain the nearest lower-rank approximation while certain specified columns of the matrix are fixed. The Eckart–Young–Mirsky theorem has the drawback that the approximation generally differs from the original matrix in all its entries. Thus it is not suitable for applications where some columns of the original matrix must be fixed. For example, in statistics the regression matrix for the multiple regression model with a constant term has a column of all ones, and this column should not be perturbed.
For each triplet \((p,q,r)\), where \(r\) is the predetermined rank, we generate a random matrix \(M \in \mathfrak {R}^{p\times q}\) of rank \(r\) by setting \(M = M_1 M_2^T\) where both \(M_1 \in \mathfrak {R}^{p\times r}\) and \(M_2 \in \mathfrak {R}^{q\times r}\) have i.i.d. standard uniform entries in \((0, 1)\). As observed entries in practice are rarely exact, we corrupt the entries of \(M\) by Gaussian noises to simulate the situation where the observed data may be noisy as follows. First we generate a random matrix \(N \in \mathfrak {R}^{p\times q}\) with i.i.d Gaussian entries. Then we assume that the observed data is given by \(\widetilde{M} = M + \tau N \Vert M\Vert /\Vert N\Vert \), where \(\tau \) is the noise factor. In our numerical experiments, we set \(\tau = 0.1\). We assume that the first column of \(M\) should be fixed, and consider the following minimization problem:
where \(e_1\) is the first column of the \(q\times q\) identity matrix. Here we impose the extra constraint \(X\ge 0\) since the original matrix \(M\) is nonnegative. Note that the approximation derived in [29] generally is not nonnegative.
For each \((p,q,r)\) and \(\tau \), we generate \(5\) random instances. In Table 1, we report the total number of constraints \((m+s)\) in (41), the average number of outer iterations, the average total number of inner iterations, the average number of BiCGStab steps taken to solve (87), the average infeasibilities, the average relative gap, the average relative mean square error \(\mathrm{MSE} := \Vert X-M\Vert /\Vert M\Vert \) (where \(M\) is the original matrix), the mean value of the rank (\(\#\)sv) of \(X\), and the average CPU time taken (in the format hours:minutes:seconds). Note that the CPU time includes the cost of running the ADMM to generate a good starting point, and the time spent in the ADMM initialization is given in the parenthesis. We may observe from the table that the partial PPA is very efficient for solving (93). For the problem where \(p\) is moderate but \(q\) is large, e.g., \(p=100\) and \(q= 20,000\), we only compute the economical form of the SVD and use the formula in (90) to avoid the explicit computation of \(V_2\). It takes less than a minute to solve the last instance to achieve the tolerance of \(10^{-6}\) while the MSE is reasonably small.
In the numerical experiments, we observe that when the generated matrix \(M\) is of small rank, e.g., \(r=10\), the singular values of the computed solution \(X\) are separated into two clusters with the first cluster having much larger mean value than that of the second cluster (see, e.g., Fig. 2). We may view the number of singular values in the first cluster as a good estimate of the rank of the true solution, while the smaller positive singular values in the second cluster may be attributed to the presence of noise in the given data. When the matrix \(M\) is of high rank, e.g., \(r=50\), the singular values of \(X\) are usually not well separated into two clusters (see, e.g., Fig. 2), excluding the largest singular value. In Table 1, when the singular values of \(X\) are well separated into two clusters, we also report the number of singular values in the first cluster in parenthesis next to \(\#\)sv. In the table, “\(\mathrm{NA}\)” means that the singular values of \(X\) are not well separated into two clusters.
Distribution of singular values of \(X\) and \(M\)
In order to give the reader an idea on the relative performance of our proposed PPA (without using ADMM to generate a good starting point) and ADMM, we also perform the same experiments for some of the instances in Table 1 for the PPA (without ADMM initialization) and ADMM. We can see that the performance of the PPA with ADMM initialization is more efficient than the one without ADMM initialization. And both are more efficient than the ADMM.
5.2 Example 2
In [34], Lin proposed the Latent Markov Analysis (LMA) approach for finding the reduced rank approximations of transition matrices. The LMA is applied to clustering based on pairwise similarities such that the inferred cluster relationships can be described probabilistically by the reduced-rank transition matrix. Benczúr et al. [5] considered the problem of finding the low rank approximation of the transition matrix for computing the personalized PageRank, which describes the backlink-based page quality around user-selected pages.
In this example, we evaluate the performance of our partial PPA for finding the nearest transition matrix of lower rank. Consider the set of \(n\) web pages as a directed graph whose nodes are the web pages and whose edges are all the links between pages. Let \(\mathrm{deg}(i)\) be the outdegree of the page \(i\), i.e., the number of pages which can be reached by a direct link from page \(i\). Note that all the self-referential links are excluded. Let \(P \in \mathfrak {R}^{n\times n}\) be the matrix which describes the transition probability between pages \(i\) and \(j\), where \(P_{ij} = 1/\mathrm{deg}(i)\) if \(\mathrm{deg}(i)>0\) and there is a link form \(i\) to \(j\). For some page \(i\) having no outlink (dangling pages), we assume \(P_{ij} = 1/n\) for \(j=1,\ldots , n\), i.e., the user will make a random choice with uniform distribution \(1/n\). Since the matrix \(P\) for the web graph generally is reducible, \(P\) may have several eigenvalues on the unit circle, which could cause convergence problems to the power method for computing the PageRank [43]. The standard way of ensuring irreducibility is that we replace \(P\) by the matrix
where \(c \in (0,1), e\in \mathfrak {R}^n\) is a vector of all ones, and \(v\in \mathfrak {R}^n\) is a vector such that \(v\ge 0\) and \(e^T v = 1\). We generate a random matrix \(N \in \mathfrak {R}^{n\times n}\) with i.i.d Gaussian entries. Then we assume that the observed data is given by \(\widetilde{P}_c = P_c + \tau N \Vert P_c\Vert /\Vert N\Vert \), where \(\tau \) is the noise factor. In our numerical experiments, we set \(\tau = 0.1\), \(c = 0.85\) which is a typical value used by Google, and \(v_i = 1/n\;\forall \, i\). The minimization problem which we solve is as follows:
We use the data Harvard500.mat generated by Cleve Moler’s MATLAB program surfer.m Footnote 1 to evaluate the performance of our algorithm. We also use surfer.m to generate three adjacency graphs of a portion of web pages starting at the root page “http://www.nus.edu.sg”. We also apply our algorithm to the data setsFootnote 2 collected by Tsaparas on querying the Google search engine about four topics: automobile industries, computational complexity, computational geometry, and randomized algorithms. Table 2 reports the average numerical results of PPA for solving (94) over \(5\) runs, where \(r\) denotes the rank of \(P_c\). We can observe from the table that the partial PPA (with ADMM initialization) is quite efficient for solving (94) when applied to the real web graph data sets. But the ADMM is surprisingly even more efficient for the two tested instances, automobile industries, computational geometry.
5.3 Example 3
We consider the problem of finding a low rank doubly stochastic matrix with a prescribed entry. A matrix \(M\in \mathfrak {R}^{n\times n}\) is called doubly stochastic if it is nonnegative and all its row and column sums are equal to one. This problem arises from numerical simulation of large circuit networks. In order to reduce the complexity of simulating the whole system, Padé approximation via a Krylov subspace method, such as the Lanczos algorithm, is used to generate a low order approximation to the linear system matrix describing the large network [3]. The tridiagonal matrix \(M \in \mathfrak {R}^{n\times n}\) produced by the Lanczos algorithm is generally not doubly stochastic. But if the original matrix is doubly stochastic, then we need to find a low rank approximation of \(M\), which is doubly stochastic and matches the maximal moments. In our numerical experiments, we will not restrict the matrix \(M\) to be tridiagonal.
For each pair \((n,r)\), we generate a positive matrix \(\overline{M}\in \mathfrak {R}^{n\times n}\) with rank \(r\) by the same method as in Example 1. Then we use the Sinkhorn–Knopp algorithm [51] to find two positive definite diagonal matrices \(D_1, D_2 \in \mathfrak {R}^{n\times n}\) such that \(M = D_1 \overline{M} D_2\) is a doubly stochastic matrix of rank \(r\). We sample a subset \(\mathcal {E}\) of \(m\) entries of \(M\) uniformly at random, and generate a random matrix \(N_{\mathcal {E}} \in \mathfrak {R}^{p\times q}\) with sparsity pattern \(\mathcal {E}\) and i.i.d standard Gaussian random entries. Then we assume that the observed data is given by \(\widetilde{M}_{\mathcal {E}} = M_{\mathcal {E}} + \tau N_{\mathcal {E}} \Vert M_{\mathcal {E}}\Vert /\Vert N_{\mathcal {E}}\Vert \), where \(\tau \) is the noise factor. The problem for matching the first moment of \(M\) can be stated as follows:
In [13], the following relatively simpler version of (95) was studied:
i.e., without the nuclear norm regularization term and all the entries of \(\widetilde{M}\) are assumed to be available. Because of the simplicity, the problem (96) was solved in [13] via its dual by a semismooth Newton-CG method analogous to that in [45].
In our numerical experiments, we set \(\tau = 0, 0.1\), and the number of sampled entries to be \(m = 10dr\), where \(dr = r(2n-r)\) is the degree of freedom in an \(n\times n\) matrix of rank \(r\). In Table 3, we report the average numerical results for solving (95) on randomly generated matrices over \(5\) runs, where \(m\) is the average number of sampled entries, and \(m+s\) is the average number of total constraints in (41). We can observe from the table that the partial PPA can solve (95) very efficiently for all the instances. Note that the partial PPA with ADMM initialization is at least twice more efficient than the one without ADMM initialization. The former is also more efficient than the ADMM, except for the instance with (\(n/\tau = 1{,}000/0.1\), \(r=10\)).
We may also consider the following generalized version of (95), where we want to find a low rank doubly stochastic matrix with \(k\) prescribed entries of \(M\):
where \((i_1,j_1), \ldots , (i_k,j_k)\) are distinct pairs. In our numerical experiments, we set \(k = \lceil 10^{-3}n^2 \rceil \), which is the number of prescribed entries selected uniformly at random. Table 4 presents the average numerical results for solving (97) on randomly generated matrices over \(5\) runs. We can observe that for this problem, partial PPA with ADMM initialization is much more efficient than the ADMM.
5.4 Example 4
We consider the problem of finding a low rank nonnegative approximation which preserves the left and right principal eigenvectors of a square positive matrix. This problem was considered by Ho and van Dooren in [31]. Let \(M\in \mathfrak {R}^{n \times n}\) be a positive matrix. By the Perron–Frobenius theorem, \(M\) has a simple positive eigenvalue \(\lambda \) with the largest magnitude. Moreover, there exist two positive eigenvectors \(v,w\in \mathfrak {R}^n\) such that \( M v = \lambda v\) and \( M^T w = \lambda w\). As suggested by Bonacich [8], the principal eigenvector can be used to measure network centrality, where the \(i\)-th component of the eigenvector gives the centrality of the \(i\)-th node in the network. For example, the Google’s PageRank [43] is a variant of the eigenvector centrality for ranking web pages.
For each pair \((n,r)\), we generate a positive matrix \(M\in \mathfrak {R}^{n\times n}\) of rank \(r\) by the same method as in Example 1. We sample a subset \(\mathcal {E}\) of \(m\) entries of \(M\) that are possibly corrupted by Gaussian noise as in Example 3, and the resulting partially observed matrix is denoted by \(\widetilde{M}_\mathcal{E}\). Given the largest positive eigenvalue \(\lambda \) and the corresponding left and right eigenvectors \(v\) and \(w\) of \(M\), the problem of finding a low rank approximation of \(M\) while preserving the left and right eigenvectors can be stated as follows:
Table 5 reports the average numerical results of the partial PPA for solving (98) over \(5\) runs. Again, we observe that our partial PPA (with ADMM initialization) is very efficient in solving the problem (98).
6 Conclusion
In this paper, we introduced a partial PPA for solving nuclear norm regularized matrix least squares problems with equality and inequality constraints, and presented global and local convergence results based on the classical results for a general partial PPA. The inner subproblems, reformulated as a system of semismooth equations, were solved by an inexact smoothing Newton method, which is proved to be quadratically convergent under a constraint nondegeneracy condition, which we also characterized. Extensive numerical experiments conducted on a variety of large scale nuclear norm regularized matrix least squares problems demonstrated that our proposed algorithm is very efficient and robust.
We view our current work as providing an important tool for solving the very difficult problem of structured approximation with a prescribed rank. Although it is popular to regularize a structured approximation problem by the nuclear norm to promote a low rank solution, it cannot always deliver a solution with a prescribed rank. Thus it would be desirable to design an algorithm (along the line discussed in [25]) to find the best approximation with a prescribed rank efficiently while preserving certain desired structures.
Notes
Available at http://www.mathworks.com/moler/ncmfilelist.html.
References
Alfakih, A.Y., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13–30 (1999)
Ames, B., Vavasis, S.: Nuclear norm minimization for the planted clique and biclique problems. Math. Progr. 129, 69–89 (2011)
Bai, Z., Freund, R.: A partial Padé-via-Lanczos method for reduced-order modeling. Linear Algebra Appl. 332–334, 139–164 (2001)
Bee, M.: Estimating rating transition probabilites with missing data. Stat. Methods Appl. 14, 127–141 (2005)
Benczúr, A.A., Csalogány, K., Sarlós, T.: On the feasibility of low-rank approximation for personalized PageRank. In: Special interest tracks and posters of the 14th international conference on World Wide Web, pp. 972–973. ACM, New York (2005)
Bertsekas, D., Tseng, P.: Partial proximal minimization algorithms for convex programming. SIAM J. Optim. 4, 551–572 (1994)
Bhatia, R.: Matrix Analysis. Springer, New York (1997)
Bonacich, P.: Factoring and weighting approaches to status scores and clique identification. J. Math. Sociol. 2, 113–120 (1972)
Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)
Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)
Chennubhotla, S.: Spectral methods for multi-scale feature extraction and data clustering, PhD thesis, University of Toronto, (2004)
Chu, M., Funderlic, R., Plemmons, R.: Structured low rank approximation. Linear Algebra Appl. 366, 157–172 (2003)
Bai, Z.-J., Chu, D., Tan, R.C.E.: Computing the nearest doubly stochastic matrix with a prescribed entry. SIAM J. Sci. Comput. 29, 635–655 (2007)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Aacdemic Press, Boston (1992)
Dolezal, V.: Monotone operators and applications in Control and Network Theory, vol. 2. Elsevier Scientific Pub. Co., Amsterdam (1979)
Eaves, B.C.: On the basic theorem of complementarity. Math. Progr. 1, 68–75 (1971)
Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218 (1936)
Eckstein, J., Bertsekas, D.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Progr. 55, 293–318 (1992)
Fazel, M.: Matrix Rank Minimization with Applications. PhD thesis, Stanford University (2002)
Fazel, M., Hindi, H., Boyd, S.: A rank minimization heuristic with application to minimum order system approximation. In: Proceedings of the American Control Conference (2001)
Fischer, A.: Solution of monotone complementarity problems with locally Lipschitzian functions. Math. Progr. 76, 513–532 (1997)
Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2, 17–40 (1976)
Gao, Y., Sun, D.F.: Calibrating least squares covariance matrix problems with equality and inequality constraints. SIAM J. Matrix Anal. Appl. 31, 1432–1457 (2009)
Gao, Y., Sun, D.F.: A majorized penalty approach for calibrating rank constrained correlation matrix problems (2010)
Glowinski, R., Marrocco, A.: Sur l’approximation par éléments finis d’ordre un, et la résolution par pénalisation-dualité d’une classe de problèmes de Dirichlet nonlinéaires. Revue Française d’Automatique, Informatique, Recherche Opérationnelle 2, 41–76 (1975)
Glowinski, R.: Numerical Methods for Nonlinear Variational Problems. Springer, New York (1984)
Golub, G.H., van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)
Golub, G.H., Hoffman, A., Stewart, G.W.: A generalization of the Eckart–Young–Mirsky matrix approximation theorem. Linear Algebra Appl. 88, 317–327 (1987)
Ha, C.: A generalization of the proximal point algorithm. SIAM J. Control Optim. 28, 503–512 (1990)
Ho, N.D., Van Dooren, P.: Non-negative matrix factorization with fixed row and column sums. Linear Algebra Appl. 429, 1020–1025 (2008)
Ibaraki, S., Fukushima, M.: Partial proximal method of multipliers for convex programming problems. J Oper. Res. Soc. Japan-Keiei Kagaku 39, 213–229 (1996)
Jiang K.F.: Algorithms for large scale nuclear norm minimization and convex quadratic semidefinite programming problems, PhD thesis, National University of Singapore, August (2011)
Juan, K.: Lin. Reduced rank approximations of transition matrices. In: Proceedings of the Ninth International Workshop on Artificial Intelligence and Statistics (2003)
Liu, Y.J. , Sun, D.F., Toh, K.C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Progr. (2010)
Löwner, K.: Über monotone matrixfunktionen. Mathematische Zeitschrift 38, 177–216 (1934)
Luo, Y.: A smoothing Newton-BICGStab method for least squares matrix nuclear norm problems, Master thesis, National University of Singapore, January (2010)
Ma, S., Goldfarb, D., Chen, L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Progr. 128, 321–353 (2011)
Meng, F., Sun, D., Zhao, G.: Semismoothness of solutions to generalized equations and the Moreau–Yosida regularization. Math. Progr. 104, 561–581 (2005)
Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 959–972 (1977)
Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. Q. J. Math. 11, 50–59 (1960)
Moreau, J.J.: Proximite et dualite dans un espace hilbertien. Bulletin de la Societe Mathematique de France 93, 273–299 (1965)
Page, L., Brin, S., Motwani, R. Winograd, T.: The pagerank citation ranking: Bringing order to the web, Technical report, Stanford Digital Library Technologies Project. Available at http://dbpubs.stanford.edu/pub/1999-66 (1999)
Pong, T.K., Tseng, P., Ji, S., Ye, J.: Trace norm regularization: reformulations, algorithms, and multi-task learning. SIAM J. Optim. 20, 3465–3489 (2010)
Qi, H.D., Sun, D.F.: A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM J. Matrix Anal. Appl. 28, 360–385 (2006)
Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Progr. 58, 353–367 (1993)
Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471–501 (2010)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14, 877–898 (1976)
Rockafellar, R.T.: Augmented Lagrangains and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97–116 (1976)
Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pac. J. Math. 21, 343–348 (1967)
Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11, 625–653 (1999)
Sun, D.F., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002)
Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3—a Matlab software package for semidefinite programming. Optim. Methods Softw. 11, 545–581 (1999)
Toh, K.C., Yun, S.W.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615–640 (2010)
Van der Vorst, H.A.: SIAM J. Sci. Stat. Comput. Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems 13, 631–644 (1992)
Warga, J.: Fat homeomorphisms and unbounded derivate containers. J. Math. Anal. Appl. 81, 545–560 (1981)
Watson, G.A.: Characterization of the subdifferential of some matrix norms. Linear Algebra Appl. 170, 33–45 (1992)
Yosida, K.: Functional Analysis. Springer, Berlin (1964)
Zarantonello E.H.: Projections on convex sets in Hilbert space and spectral theory I and II. In: Zarantonello, E.H. (ed.) Contributions to Nonlinear Functional Analysis, pp. 237–424. Academic Press, New York (1971)
Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Kim-Chuan Toh: Research support in part by Academic Research Fund under grant R-146-000-168-112.
Defeng Sun: Research supported in part by Academic Research Fund under grant R-146-000-149-112.
Rights and permissions
About this article
Cite this article
Jiang, K., Sun, D. & Toh, KC. A partial proximal point algorithm for nuclear norm regularized matrix least squares problems. Math. Prog. Comp. 6, 281–325 (2014). https://doi.org/10.1007/s12532-014-0069-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12532-014-0069-8