Proximal Support Matrix Machine

Wan Zhang, Yulan Liu

School of Mathematics and Statistics, Guangdong University of Technology, Guangzhou, China.

DOI: 10.4236/jamp.2022.107155                

Abstract

In this paper, we have proposed a novel model called proximal support matrix machine (PSMM), which is mainly based on the models of proximal support vector machine (PSVM) and low rank support matrix machine (LRSMM). In design, the PSMM model has comprehensively considered both the relationship between samples of the same class and the structure of rows or columns of matrix data. To a certain extent, our novel model can be regarded as a synthesis of the PSVM model and the LRSMM model. Since the PSMM model is an unconstrained convex problem in essence, we have established an alternating direction method of multipliers algorithm to deal with the proposed model. Finally, since a great deal of experiments on the minst digital database show that the PSMM classifier has a good ability to distinguish two digits with little difference, it encourages us to conduct more complex experiments on MIT face database, INRIA person database, the students face database and Japan female facial expression database. Meanwhile, the final experimental results show that PSMM performs better than PSVM, twin support vector machine, LRSMM and linear twin multiple rank support matrix machine in the demanding image classification tasks.

Keywords

PSMM, PSVM, LRSMM, The Alternating Direction Method of Multipliers Al-gorithm, Image Classification Tasks

1. Introduction

Classification is an important research field of machine learning, in which the support vector classifier is a common and important tool. There are many excellent designs of support vector classifiers. For example, the proximal support vector machine (PSVM) [1] has considered the relationship between samples within a class, which makes congener samples have aggregation effect. Subsequently, a great deal of vector classifiers were developed on the basis of PSVM classifier, see [2] [3] [4] [5] [6]. Moreover, deferent from PSVM with single model, the twin support vector machine (TSVM) [7] has designed two relatively small SVM-type models, which makes samples can be quickly classified by a pair of nonparallel separating planes. Inspired by TSVM, there also have developed a lot of twin-type vector classifiers, see [8] [9] [10] [11]. For more innovative designs of support vector classifiers, see [12] [13] [14] [15]. However, with the progress of modern science and technology, data to be processed is often expressed as matrices rather than vectors in application. When using vector classifiers on matrix data, the input matrices have to be reshaped into vectors, which will destroy the structure of rows or columns and thus lose important classification information unique to matrix data. Additionally, the reconstruction of matrix will inevitably lead to the superposition of rows or columns, resulting in a high-dimensional vector. It is not conducive to conduct large-scale testing in matrix classification tasks.

Realizing the above problems, many works have been proposed to extend the classification strategy of support vector machines to matrix space, which can get the eminent results in matrix classification problems. For example, L. Luo et al. have proposed low rank support matrix machine (LRSMM) [16] on the basis of the soft-margin support vector machine (Soft-SVM) [17], which has considered the correlation of rows and columns of matrix samples by using nuclear norm as the convex approximation of matrix rank. X. Gao et al. have proposed linear twin multiple rank support matrix machine (LTMRSMM) [18] on the basis of TSVM [7], which has considered the practical situation that matrix data are multiple rank. Q. Zheng et al. have proposed the robust support matrix machine [19] on the basis of the bilinear support vector machine [20], which has considered the spatial-temporal structural information of the input matrices and thus can eliminate non-standard noises of samples. For more cutting-edge works, see [21] [22] [23] [24] [25]. The designs of these SMM-type models provide us a new idea to solve matrix classification problems.

In this paper, to generalize the classification method of PSVM [1] to matrix space, we propose the proximal support matrix machine (PSMM) on the basis of PSVM [1] and LRSMM [16], and we give the novel model as follows:

$\underset{\left(W\mathrm{,}b\right)\in {ℝ}^{l\times m}\times ℝ}{\min }\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\tau {\Vert W\Vert }_{\ast }+\frac{C}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2$

where $X_i\in {ℝ}^{l\times m}\mathrm{,}{y}_i\in ℝ$ are given matrix sample and category label for each i and $C\mathrm{,}\tau$ are two given penalty parameter. In design, our model has absorbed the advantages of PSVM and LRSMM, which has comprehensively considered the relationship between samples within a class and the structure of rows or columns of matrix samples. Meanwhile, since the novel model is essentially a convex problem, it encourages us to establish an alternating direction method of multipliers (ADMM) algorithm [26] to deal with the PSMM model. Finally, we mainly focus on image classification, which is a very significant problem of matrix classification. We conduct a series of comparative experiments on minst digital database [27], MIT face database, INRIA person database [28], the students face database [29] and Japan female facial expression database [30]. The final experimental results show that our method performs better than PSVM [1], TSVM [7], LRSMM [16] and LTMRSMM [18] in demanding image classification tasks.

The remainder of this paper is arranged as follows. In Section 2, we give the notations and lemma used in our paper. In Section 3, we recall the models of PSVM [1] and LRSMM [16] related to our novel model. In Section 4, the PSMM model is proposed and then an ADMM algorithm is established to solve it. In Section 5, some experimental analyses are presented to verify the performance of the PSMM classifier. In Section 6, our work is summarized.

2. Preliminaries

As a matter of convenience, we give the notations and lemma in this section, which will be used in this paper.

For a given matrix $A\in {ℝ}^{l\times m}$ with $\text{rank}\left(A\right)=r_A$ and the singular values ${\sigma }_1\left(A\right)\ge \cdots \ge {\sigma }_{r_A}\left(A\right)>0$, we define the singular value decomposition of the matrix $A$ by

$A=U_A{\Sigma }_A{V}_A^{\text{T}}\in {ℝ}^{l\times m}\mathrm{,}$ (1)

where $U_A\in {ℝ}^{l\times r_A}\mathrm{,}{V}_A\in {ℝ}^{m\times r_A}$ and ${\Sigma }_A$ is a diagonal matrix with diagonal entries ${\sigma }_1\left(A\right)\mathrm{,}\cdots \mathrm{,}{\sigma }_{r_A}\left(A\right)$. And, the Frobenius norm of the matrix $A$ is denoted as

${\Vert A\Vert }_F={\left({\displaystyle \underset{i\mathrm{,}j}{\sum }}{\left[A\right]}_{ij}^2\right)}^{\frac{1}{2}}={\left({\displaystyle \underset{i=1}{\overset{r_A}{\sum }}}{\sigma }_i{\left(A\right)}^2\right)}^{\frac{1}{2}}$

and the nuclear norm of $A$ is denoted as

${\Vert A\Vert }_{\ast }={\displaystyle \underset{i=1}{\overset{r_A}{\sum }}}{\sigma }_i(\; A\; )$

whose subdifferential is denoted by $\partial {\Vert A\Vert }_{\ast }$. We reshape $A$ into a vector $a\in {ℝ}^{lm}$ with a traditional and common matrix reconstruction approach:

$a\mathrm{<mo>\; :\; </mo>}=\text{vec}\left(A\right)\mathrm{<mo>\; :\; </mo>}={\left({\left[A\right]}_{11}\mathrm{,}\cdots \mathrm{,}{\left[A\right]}_{1l}\mathrm{,}{\left[A\right]}_{21}\mathrm{,}\cdots \mathrm{,}{\left[A\right]}_{lm}\right)}^{\text{T}}$

and define the Frobenius norm $\Vert a\Vert ={\left({\displaystyle \underset{i\mathrm{,}j}{\sum }}{\left[A\right]}_{ij}^2\right)}^{\frac{1}{2}}={\Vert A\Vert }_F$.

Lemma 1. (see [31], Theorem 2.1) Given a matrix $A\in {ℝ}^{l\times m}$ with $\text{rank}\left(A\right)=r_A$ and the singular value decomposition as defined in (1). For $\gamma >0$, the following problem

$\underset{Q\in {ℝ}^{l\times m}}{\min }\gamma {\Vert Q\Vert }_{\ast }+\frac{1}{2}{\Vert Q-A\Vert }_F^2$

has unique closed-form solution, denoted by $Q^{\mathrm{<mo>\; *\; </mo>}}$, as follows:

$Q^{\mathrm{<mo>\; *\; </mo>}}={\mathcal{D}}_{\gamma }\left(A\right)\mathrm{<mo>\; :\; </mo>}=U_A{D}_{\gamma }{V}_A^{\text{T}}$

where $D_{\gamma }$ is a diagonal matrix with ${\left[{\sigma }_1\left(A\right)-\gamma \right]}_{+}\mathrm{,}\cdots \mathrm{,}{\left[{\sigma }_{r_A}\left(A\right)-\gamma \right]}_{+}$ as diagonal entries and ${\left[t\right]}_{+}=\max \left\{t\mathrm{,0}\right\}$ for any $t\in ℝ$.

In this paper, we give a matrix data set $T_m={\left\{\left(X_i\mathrm{,}{y}_i\right)\right\}}_{i=1}^n$ with $X_i\in {ℝ}^{l\times m}$ and $y_i\in \left\{-\mathrm{1,1}\right\}$, and denote the label vector as $y={\left(y_1\mathrm{,}\cdots \mathrm{,}{y}_n\right)}^{\text{T}}\in {ℝ}^n$. For the convenience of calculation, we define a linear mapping $\mathcal{A}\mathrm{<mo>\; :\; </mo>}{ℝ}^{l\times m}\to {ℝ}^n$ by

$\mathcal{A}\left(A\right)={\left(\begin{array}{c}\langle A\mathrm{,}{X}_1\rangle \mathrm{,}\cdots \mathrm{,}\langle A\mathrm{,}{X}_n\rangle \end{array}\right)}^{\text{T}}\in {ℝ}^n$

and denote $\circ$ as the Hadamard product between two matrices. Additionally, we also denote the n-order identity matrix as $I$ and define an all one vector $e={\left(\mathrm{1,}\cdots \mathrm{,1}\right)}^{\text{T}}\in {ℝ}^n$.

3. Related Work

The design inspiration of PSMM proposed in this paper mainly comes from PSVM [1] and LRSMM [16]. In order to show the rationality and advantages of the PSMM model in design, we review and analyze the models of PSVM [1] and LRSMM [16] in this section.

3.1. Proximal Support Vector Machine (PSVM)

Different from Soft-SVM model [17], the PSVM model is described in $\left(w\mathrm{,}b\right)$ space of ${ℝ}^{lm}\times ℝ$. Additionally, PSVM defines a pair of proximal hyperplanes $\langle w\mathrm{,}x\rangle +b=\pm 1$ and constrains samples of the same class to be as close to the same proximal plane as possible. This is because the higher the fitting degree of proximal planes to the samples, the more obvious the boundary between the two types of samples, and then the better the classification effect of classification hyperplane. The strategy of PSVM can be presented as the following model, for details, see [1]:

$\underset{\left(w\mathrm{,}b\right)}{\min }\frac{1}{2}\left({\Vert w\Vert }^2+b^2\right)+\frac{c}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle w\mathrm{,}{x}_i\rangle +b\right)\right]}^2$ (2)

where $x_i\mathrm{<mo>\; :\; </mo>}=\text{vec}\left(X_i\right)\in {ℝ}^{lm}$ for each i is the reconstructed vector sample, $\left(w\mathrm{,}b\right)\in {ℝ}^{lm}\times ℝ$ is the decision variable and $c\in ℝ$ is a given penalty parameter. A new input $X\in {ℝ}^{l\times m}$ has to be reshaped into a vector $x\in {ℝ}^{lm}$, and then it can be assigned by the decision function: $y_v\left(x\right)=\text{sign}\left(\langle w\mathrm{,}x\rangle +b\right)$, where $\text{sign}(\cdot )$ is the symbolic function.

Compared with Soft-SVM [17], PSVM [1] has considered the relationship between samples within a class, that samples of the same class are required to be close together, so that congener samples have aggregation effect. The advantage of this consideration is that the distribution trend of congener samples can be grasped, which makes PSVM have a good performance in prediction. Meanwhile, the PSVM model (2) is an unconstrained quadratic programming problem in essence, so that the cost of PSVM classifier is lower than that of Soft-SVM classifier. Thus, PSVM has more advantage than Soft-SVM in large database classification, for details, see [1].

3.2. Low Rank Support Matrix Machine (LRSMM)

Different from vector data, each matrix data has an identifying intrinsic structure, which reveals significant category information in matrix classification. As an important structural information, the correlation of rows or columns of matrix is closely related to the rank of the regression matrix $W$. Meanwhile, it is an effective measure for filtering the redundant information of samples to impose the low rank constraint on $W$ in application. However, matrix rank minimization problem is a typical NP-hard problem. Realizing this difficulty, inspired by the idea that the nuclear norm is the best convex approximation of matrix rank, LRSMM was developed on the basis of Soft-SVM [17], which has achieved the low-rank target of samples by minimizing the nuclear norm of $W$. The LRSMM model is presented as follows, for details, see [16]:

$\underset{W\mathrm{,}b}{\min }\frac{1}{2}{\Vert W\Vert }_F^2+\tau {\Vert W\Vert }_{\ast }+C{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}_{+}$ (3)

where $W\in {ℝ}^{l\times m}\mathrm{,}b\in ℝ$ are decision variables, $C\in ℝ$ and $\tau \in {ℝ}_{++}$ are two given penalty parameters. A new input $X\in {ℝ}^{l\times m}$ can be assigned by the decision function: $y_m\left(X\right)=\text{sign}\left(\langle W\mathrm{,}X\rangle +b\right)$.

4. Proximal Support Matrix Machine (PSMM)

In this section, we propose a novel matrix classification method PSMM on the basis of PSVM [1] and LRSMM [16], which has generalized the classification method of PSVM to matrix space and also has inherited the design in LRSMM of constraining matrix samples to be low-rank. The formulation of our novel model is given as follows:

$\underset{\left(W\mathrm{,}b\right)}{\min }\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\tau {\Vert W\Vert }_{\ast }+\frac{C}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2$ (4)

where $\left(W\mathrm{,}b\right)\in {ℝ}^{l\times m}\times ℝ$ is the decision variable, $C\in ℝ$ and $\tau \in {ℝ}_{++}$ are two given penalty parameters. In order to take into consideration the relationship between congener samples, PSMM also defines a pair of proximal hyperplanes $\langle W\mathrm{,}X\rangle +b=\pm 1$. And, the formula ${\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2$ is used to calculate the Euclidean distance between the ith sample and the proximal hyperplane. In (4), we can achieve the target that samples of the same class should gather near the same proximal plane by minimizing the sum of these Euclidean distances. Additionally, to meet the need that matrix samples should be low-rank in application, the nuclear norm of the regression matrix $W$ is introduced into our objective function in the inspiration of LRSMM [16].

The design of the PSMM model (4) has many advantages. On the one hand, since the nuclear norm of $W$ is the only nonsmooth part in the PSMM model, PSMM algorithm presented below will be simpler than LRSMM algorithm [16] in framework design. And, in the following experiments, it can be found that the cost of PSMM classifier is much lower than that of LRSMM classifier. On the other hand, compared with PSVM [1], PSMM has taken into account the intrinsic structure of matrix data, so that the performance of PSMM classifier is better than that of PSVM classifier in the following matrix classification tasks. Thus, to a certain degree, the novel model (4) is a synthesis of PSVM model (2) and LRSMM model (3).

4.1. Model Solution

Since the PSMM model (4) is a convex problem, we can devise an ADMM-type algorithm [26] to solve the proposed novel model. Firstly, the PSMM model (4) can be equivalently written in the following form:

$\begin{array}{l}\underset{\left(W\mathrm{,}b\right)\mathrm{,}S}{\min }\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\tau {\Vert S\Vert }_{\ast }+\frac{C}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2\\ \text{s}\mathrm{.}\text{t}\mathrm{.}W=S\mathrm{.}\end{array}$ (5)

And, its corresponding augmented Lagrangian function is given as follows:

$\begin{array}{c}{L}_{\rho }\left(\left(W\mathrm{,}b\right)\mathrm{,}S\mathrm{<mo>\; ;\; </mo>}\Lambda \right)=\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\tau {\Vert S\Vert }_{\ast }+\frac{C}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2\\ +\langle \Lambda \mathrm{,}S-W\rangle +\frac{\rho }{2}{\Vert S-W\Vert }_F^2\end{array}$ (6)

where $\Lambda \in {ℝ}^{l\times m}$ is the Lagrangian multiplier of the problem (5) and $\rho >0$ is a given parameter of the penalty term. Consequently, we can take advantage of the augmented Lagrangian function (6) to establish the iterative framework of PSMM algorithm, which is based on the framework of ADMM. Given the state variables $\left(\left(W^k\mathrm{,}{b}^k\right)\mathrm{,}{S}^k\mathrm{<mo>\; ;\; </mo>}{\Lambda }^k\right)$ at iteration k, the proposed framework for updating variable status is given as follows:

$\begin{array}{c}\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)=\underset{W\mathrm{,}b}{\arg \min }\{\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\frac{C}{2}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)\right]}^2\\ +\langle {\Lambda }^k\mathrm{,}{S}^k-W\rangle +\frac{\rho }{2}{\Vert S^k-W\Vert }_F^2\}\end{array}$ (7)

$S^{k+1}=\underset{S}{\arg \min }\left\{\tau {\Vert S\Vert }_{\ast }+\langle {\Lambda }^k\mathrm{,}S-W^{k+1}\rangle +\frac{\rho }{2}{\Vert S-W^{k+1}\Vert }_F^2\right\}$ (8)

${\Lambda }^{k+1}={\Lambda }^k+\rho \left(S^{k+1}-W^{k+1}\right)$ (9)

Note that we have to solve the two optimization problems (7) and (8) on each update. Thus, it is necessary to determine their explicit solutions, which can reduce the cost of our algorithm to a great extent.

Solving (7) can be transformed into solving the following model:

$\begin{array}{l}\underset{W\mathrm{,}b\mathrm{,}x}{{\displaystyle \min }}\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\frac{C}{2}{\Vert x\Vert }^2-\langle {\Lambda }^k\mathrm{,}W\rangle +\frac{\rho }{2}{\Vert S^k-W\Vert }_F^2\\ \text{s}\text{.t}\text{.}1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)={\xi }_i\mathrm{,}i=\mathrm{1,}\cdots \mathrm{,}n\mathrm{.}\end{array}$ (10)

That is because the optimal partial variable of (10), uniformly denoted by $\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)$, is actually the optimal solution of the problem (7). Since the model (10) is essentially a smooth convex optimization problem only with equality constraints, we can solve this problem by its dual problem. The Lagrange function of (10) is given as follows:

$\begin{array}{c}L\left(W\mathrm{,}b\mathrm{,}\xi \mathrm{<mo>\; ;\; </mo>}\lambda \right)=\frac{1}{2}\left({\Vert W\Vert }_F^2+b^2\right)+\frac{C}{2}{\Vert \xi \Vert }^2-\langle {\Lambda }^k\mathrm{,}W\rangle +\frac{\rho }{2}{\Vert S^k-W\Vert }_F^2\\ +{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{\lambda }_i\left[1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)-{\xi }_i\right]\end{array}$

where $\lambda ={\left({\lambda }_1\mathrm{,}\cdots \mathrm{,}{\lambda }_n\right)}^{\text{T}}\in {ℝ}^n$ is the Lagrange multiplier of (10). For each k, we define the following matrices:

$\tilde{Y}=y{y}^{\text{T}}\mathrm{,}\tilde{X}=\tilde{Y}\circ \left[\mathcal{A}\left(X_1\right)\mathrm{,}\cdots \mathrm{,}\mathcal{A}\left(X_n\right)\right]$

${\tilde{S}}^k=y\circ \mathcal{A}\left(S^k\right)\mathrm{,}{\tilde{\Lambda }}^k=y\circ \mathcal{A}(\; \Lambda \; k\; )$

Consequently, the Karush-Kuhn-Tucher (KKT) conditions for the model (10) are given as follows:

$(\begin{array}{l}W=\frac{1}{1+\rho }\left(\rho S^k+{\Lambda }^k+{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i{X}_i\right)\\ b={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i,{\xi }_i=\frac{1}{C}{\lambda }_i,i=1,\cdots ,n\\ 1-y_i\left(\langle W\mathrm{,}{X}_i\rangle +b\right)-{\xi }_i=\mathrm{0,}i=\mathrm{1,}\cdots \mathrm{,}n\end{array}$ (11)

According to duality theory and (11), after simple calculation, we can get the dual problem of (10) as follows:

$\underset{\lambda \in {ℝ}^n}{\max }d\left(\lambda \right)$ (12)

where $d\left(\lambda \right)$ has the following expression:

$\begin{array}{c}d\left(\lambda \right)=\langle \lambda \mathrm{,}e\rangle -\frac{\rho }{1+\rho }\langle \lambda \mathrm{,}{\tilde{S}}^k\rangle -\frac{1}{1+\rho }\langle \lambda \mathrm{,}{\tilde{\Lambda }}^k\rangle -\frac{1}{C}{\Vert \lambda \Vert }^2\\ -\frac{1}{2}\langle \lambda \mathrm{,}\tilde{Y}\lambda \rangle -\frac{1}{2\left(1+\rho \right)}\langle \lambda \mathrm{,}\tilde{X}\lambda \rangle \end{array}$

and the optimal solution of (12) is denoted by ${\lambda }^k$. Since the dual problem (12) is essentially an unconstrained quadratic programming problem, by the optimality theorem, we find that solving (12) is equivalent to solve the following system:

${\nabla }_{\lambda }d=e-\frac{\rho }{1+\rho }{\tilde{S}}^k-\frac{1}{1+\rho }{\tilde{\Lambda }}^k-\frac{2}{C}\lambda -\tilde{Y}\lambda -\frac{1}{1+\rho }\tilde{X}\lambda =\mathrm{0,}$

i.e.,

$\left(\frac{2}{C}I+\tilde{Y}+\frac{1}{1+\rho }\tilde{X}\right)\lambda =e-\frac{\rho }{1+\rho }{\tilde{S}}^k-\frac{1}{1+\rho }{\tilde{\Lambda }}^k\mathrm{.}$ (13)

If the coefficient matrix of (13) is invertible, then the optimal solution ${\lambda }^k$ of (12) has the explicit exact expression as follows:

${\lambda }^k={\left(\frac{2}{C}I+\tilde{Y}+\frac{1}{1+\rho }\tilde{X}\right)}^{-1}\left(e-\frac{\rho }{1+\rho }{\tilde{S}}^k-\frac{1}{1+\rho }{\tilde{\Lambda }}^k\right)\mathrm{.}$

Therefore, by the KKT system (11), the optimal partial variable of (10) $\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)$ has the following explicit exact expression:

$(\begin{array}{l}{W}^{k+1}=\frac{1}{1+\rho }\left(\rho S^k+{\Lambda }^k+{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i^k{X}_i\right)\\ b^{k+1}={\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i^k\end{array}$

which means that the iterative format (7) can be written in a more concise form:

$\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)=\left(\frac{1}{1+\rho }\left(\rho S^k+{\Lambda }^k+{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i^k{X}_i\right)\mathrm{,}{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{\lambda }_i^k\right)\mathrm{.}$

Additionally, the problem (8) can be equivalently written as follows:

$\underset{S}{\arg \min }\left\{\frac{\tau }{\rho }{\Vert S\Vert }_{\ast }+\frac{1}{2}{\Vert S-\left(W^{k+1}-\frac{1}{\rho }{\Lambda }^k\right)\Vert }_F^2\right\}\mathrm{.}$ (14)

By Lemma 1, we can deduce the closed-form solution of (14), so that the iterative format (8) has more straightforward expression as follows:

$S^{k+1}={\mathcal{D}}_{\frac{\tau }{\rho }}\left(W^{k+1}-\frac{1}{\rho }{\Lambda }^k\right)\mathrm{.}$

4.2. Convergence

Since the model (5) is a convex problem only with equality constraints, then the convergence property of PSMM iterative framework can be guaranteed by [26] [32], so that we can get the following results:

Definition 1. For given parameters $C\in ℝ$ and $\tau \in {ℝ}_{++}$, we say $\left(\left(W^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{b}^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}{S}^{\mathrm{<mo>\; *\; </mo>}}\right)$ is the proximal stationary (P-stationary) point of (5) if there exists a Lagrangian multiplier ${\Lambda }^{\mathrm{<mo>\; *\; </mo>}}\in {ℝ}^{l\times m}$ such that

$0=W^{\mathrm{<mo>\; *\; </mo>}}-C{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{X}_i\left[1-y_i\left(\langle W^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{X}_i\rangle +b^{\mathrm{<mo>\; *\; </mo>}}\right)\right]-{\Lambda }^{\mathrm{<mo>\; *\; </mo>}}$ (15a)

$0=b^{\mathrm{<mo>\; *\; </mo>}}-C{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i\left[1-y_i\left(\langle W^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{X}_i\rangle +b^{\mathrm{<mo>\; *\; </mo>}}\right)\right]$ (15b)

$0\in \tau \partial {\Vert S^{\mathrm{<mo>\; *\; </mo>}}\Vert }_{\ast }+{\Lambda }^{\mathrm{<mo>\; *\; </mo>}}$ (15c)

$0=S^{\mathrm{<mo>\; *\; </mo>}}-W^{\mathrm{<mo>\; *\; </mo>}}$ (15d)

Theorem 2. Suppose $\left(\left(W^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{b}^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}{S}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{\Lambda }^{\mathrm{<mo>\; *\; </mo>}}\right)$ be the limit point of the sequence $\left(\left(W^k\mathrm{,}{b}^k\right)\mathrm{,}{S}^k\mathrm{,}{\Lambda }^k\right)$ generated by the PSMM iterative framework, then $\left(\left(W^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{b}^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{,}{S}^{\mathrm{<mo>\; *\; </mo>}}\right)$ is a P-stationary point and thus a locally optimal solution to the problem (5).

Remark. Since $\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)$ minimizes $L_{\rho }\left(\left(W\mathrm{,}b\right)\mathrm{,}{S}^k\mathrm{,}{\Lambda }^k\right)$, then we have the following relation:

$0=W^{k+1}-C{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{X}_i\left[1-y_i\left(\langle W^{k+1}\mathrm{,}{X}_i\rangle +b^{k+1}\right)\right]-{\Lambda }^k-\rho \left(S^k-W^{k+1}\right)$ (16)

$0=b^{k+1}-{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i\left[1-y_i\left(\langle W^{k+1}\mathrm{,}{X}_i\rangle +b^{k+1}\right)\right]$ (17)

Similarly, since $S^{k+1}$ minimizes $L_{\rho }\left(\left(W^{k+1}\mathrm{,}{b}^{k+1}\right)\mathrm{,}S\mathrm{,}{\Lambda }^k\right)$, then we also have the following relation:

$0\in \tau \partial {\Vert S^{k+1}\Vert }_{\ast }+{\Lambda }^k+\rho \left(S^{k+1}-W^{k+1}\right)$ (18)

1) It is not difficult to find that the iteration formula (9) always produces a gap $\rho \left(S^{k+1}-W^{k+1}\right)$ between the state variables ${\Lambda }^k$ and ${\Lambda }^{k+1}$ at iteration $k+1$, so that there always has a residual between ${\Lambda }^k$ and the locally optimum ${\Lambda }^{\mathrm{<mo>\; *\; </mo>}}$ on each update. Meanwhile, from the perspective of feasibility, the locally optimal point of (5) must meet the feasible condition (15d). Nevertheless, $W^{k+1}$ and $S^{k+1}$ are generally unequal on each update. To this end, we denote $E_p^{k+1}\mathrm{<mo>\; :\; </mo>}=S^{k+1}-W^{k+1}$ as the primal residual at iteration $k+1$. Aditionally, combining (9) and (16), we can obtain the following equality:

$0=W^{k+1}-C{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{y}_i{X}_i\left[1-y_i\left(\langle W^{k+1}\mathrm{,}{X}_i\rangle +b^{k+1}\right)\right]-{\Lambda }^{k+1}+\rho \left(S^{k+1}-S^k\right)$

which means that there always exists a residual $\rho \left(S^{k+1}-S^k\right)$ for the condition (15a) on each iteration. We denote $E_d^{k+1}\mathrm{<mo>\; :\; </mo>}=\rho \left(S^{k+1}-S^k\right)$ as the dual residual at iteration $k+1$.

2) Conversely, by (17), it is easy to know that $b^{k+1}$ always satisfies the condition (15b) at iteration $k+1$. Similarly, combining (9) and (18), we can obtain the following equality:

$0\in \tau \partial {\Vert S^{k+1}\Vert }_{\ast }+{\Lambda }^{k+1}$

which means that $S^{k+1}$ and ${\Lambda }^{k+1}$ also always satisfy the condition (15c) at iteration $k+1$.

4.3. Stopping Criterion

Based on the above analysis, we know that the PSMM algorithm can obtain the locally optimal solution when the following conditions are satisfied:

$E_p^{k+1}\to 0\text{as}k\to \infty \mathrm{,}$

$E_d^{k+1}\to 0\text{as}k\to \infty \mathrm{.}$

Therefore, inspired by [26], we set a stopping criterion that the decision variables stop updating and output when

${\Vert E_p^{k+1}\Vert }_F\le {\epsilon }_p\mathrm{,}{\Vert E_d^{k+1}\Vert }_F\le {\epsilon }_d\mathrm{.}$

The tolerances ${\epsilon }_p,{\epsilon }_d>0$ can be predetermined by the following criterion:

${\epsilon }_p=\sqrt{n}{\epsilon }_{abs}+{\epsilon }_{rel}\max \left\{{\Vert W^{k+1}\Vert }_F\mathrm{,}{\Vert S^{k+1}\Vert }_F\right\}$

${\epsilon }_d=\sqrt{n}{\epsilon }_{abs}+{\epsilon }_{rel}\rho {\Vert {\Lambda }^{k+1}\Vert }_F$

where ${\epsilon }_{abs}$ and ${\epsilon }_{rel}$ are absolute and relative tolerances, respectively, and their settings depend on the application, for details, see [26]. Furthermore, the specific procedure of PSMM algorithm is shown as follows:

5. Experiments

To verify the binary classification effect of our method, we conduct the experimental analysis of PSMM classifier in this section. There are five selected image data sets, including minst digital database [27], MIT face database, INRIA person database [28], the students face database [29] and Japan female facial expression database (JAFFE) [30]. And, we conduct comparative experiments on these data sets with PSVM [1], TSVM [7], LRSMM [16], LTMRSMM [18]. We summarize the main information of the selected data sets in Table 1. Some pictures of these databases are shown in Figures 1-5. All experiments are implemented in Matlab R2019a on a workstation with AMD A10-7300 Radeon R6 1.90 Hz, 10 Computer Cores 4C+6G, 4 GB RAM, and 64 bit Windows Server 2009 system.

Table 1. Summary of five image data sets.

Figure 1. Some pictures from minst digital database.

Figure 2. Some pictures from MIT face database.

Figure 3. Some pictures from the students face database.

5.1. Classification on Minst Digital Database

Minst digital database [27] comes from National Institute of Standards and Technology, which includes handwritten characters from zero to nine. Due to

Figure 4. Some pictures from the INRIA person database.

Figure 5. Some pictures from the JAFFE database.

the differences in writing habits of volunteers, different digits may have similar contours, resulting in wrong judgment. The purpose why we chose this database is to distinguish handwritten numerals with little difference in contour.

Through the observation of a large number of handwritten character samples, we found five digital pairs, and the two numbers of any digital pair are similar in morphology. They are (0, 6), (1, 7), (2, 7), (3, 8) and (5, 6), respectively. And, their comparisons are shown in Figure 6. We conducted binary classification experiments on the two numbers in the specific digital pair. The experimental results show that PSMM performs better than PSVM [1], TSVM [7], LRSMM [16] and LTMRSMM [18] in distinguishing handwritten digits with similar contours, for details, see Table 2.

Figure 6. Comparison pictures of handwritten digits with similar contours.

Table 2. Experimental results on minst digital database.

5.2. Classification on Portrait Database

Through the results on minst digital database, we found that the novel classifier has a good ability to distinguish two categories with little difference. It prompted us to further apply it to more complex portrait classification tasks, such as face recognition, gender judgment, pedestrian detection and emotion recognition, which require classifiers to have the ability to distinguish details. To test the performance of PSMM classifier in these complex tasks, we selected the following four portrait databases.

1) MIT face database is affiliated to Massachusetts Institute of Technology, with a total of 7087 samples, including 2706 face samples and 4381 no face samples. All images are gray images stored in BMP format, with width and height of 20. We chose it for face recognition experiments which is to judge whether there is a face in picture.

2) INRIA person database [28] was collected to detect whether there exist people in the image, including 2416 pedestrian pictures and 12,180 landscape pictures. All images are color images stored in JPG or PNG format, and we have normalized the samples into 61 × 128 gray level matrices to unify the specifications of samples.

3) The students face database [29] contains 400 photos of medical students in Stanford University, which consists of 200 males and 200 females. All images are gray images stored in JPG format, with the width and height of 200. In the process of gender judgment, hair style will be a disturbance, because girls may have short hair and boys may have long hair. Therefore, this database we chose will further test the ability of classifiers to distinguish facial details.

4) Japan female facial expression database [30] has 213 facial expression images, which are composed of 7 facial expression images of 10 women. The seven expressions are afraid, surprised, happy, sad, angry, disgusted, neutral, respectively. All images are gray images stored in TIFF format, with the width and height of 256. We conducted binary classification experiments between each emotion and the rest to observe the sensitivity of PSMM classifier to facial expression differences.

Through a large number of preliminary experiments, we have determined the appropriate training set size of each database. And, the stability and progressiveness of the novel algorithm have been verified by properly increasing the number of test samples and massive repeated experiments, for details, see Tables 3-6.

Table 3. Experimental results on MIT face database.

Table 4. Experimental results on INRIA person database.

Table 5. Experimental results on the students face database.

5.3. Parameters Selection

The penalty parameter C affects the fitting degree of the proximal plane to samples. If the value of C is too small, the prediction ability of proximal planes will be lost, resulting in under fitting. Conversely, C with too large value will produce over fitting phenomenon, which will lead to the poor generalization ability of

Table 6. Experimental results on the JAFFE database.

Figure 7. Effects of different C on the performance of PSMM classifier in the task of judging the existence of human face.

Figure 8. Effects of different C on the performance of PSMM classifier in the task of judging the existence of pedestrian.

Figure 9. Effects of different C on the performance of PSMM classifier in the task of judging the gender of students.

Figure 10. Effects of different C on the performance of PSMM classifier in the task of distinguishing afraid expression.

Figure 11. Effects of different C on the performance of PSMM classifier in the task of distinguishing surprised expression.

Figure 12. Effects of different C on the performance of PSMM classifier in the task of distinguishing happy expression.

Figure 13. Effects of different C on the performance of PSMM classifier in the task of distinguishing sad expression.

Figure 14. Effects of different C on the performance of PSMM classifier in the task of distinguishing angry expression.

Figure 15. Effects of different C on the performance of PSMM classifier in the task of distinguishing disgusted expression.

Figure 16. Effects of different C on the performance of PSMM classifier in the task of distinguishing neutral expression.

our model. Thus, predetermining the value of C is of vital importance for PSMM classifier. To observe the influence of different C on the classification accuracy of the novel model, we select C from {1 × 10⁻³, 2.5 × 10⁻³, 5 × 10⁻³, 1 × 10⁻², 2.5 × 10⁻², 5 × 10⁻², ∙∙∙, 1 × 10¹, 2.5 × 10¹, 5 × 10¹} and fix the values of other parameters, i.e., $\tau =2,\rho =1$. The results of different data sets are shown in Figures 7-16.

6. Conclusion

In this paper, a novel SMM-type method called PSMM is proposed for the matrix classification problems, which has absorbed the advantages of PSVM and LRSMM. In design, the novel method has considered both the relationship between samples within a class and the structure of rows or columns of matrix data, which makes PSMM have good properties to meet the challenges of complex image classification problems. Finally, to verify the performance of our design, we conduct a large number of comparative experiments. It can be seen from the experimental results that PSMM performs better than PSVM, TSVM, LRSMM, LTMRSMM in the demanding image classification tasks. Moreover, since we only considered the linearly binary classification situation and the selection of penalty parameter C in this paper, there still have some relevant topics worthy of in-depth study in the future. For example, how to extend the PSMM algorithm to multiple classification situation, how to introduce appropriate kernel function to create the nonlinear version of PSMM and how to select a stable parameter combination. We will take these topics as our future directions.

Acknowledgements

Sincerely thank Professor Yulan Liu for the support and guidance to this research, and gratefully acknowledge Guangdong University of Technology for providing a good learning platform.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Fung, G. and Mangasarian, O.L. (2001) Proximal Support Vector Machine Classifiers. Proceedings of Seventh International Conference on Knowledge and Data Discovery, San Francisco, 26-29 August 2001, 77-86. https://doi.org/10.1145/502512.502527
[2]	Mangasarian, O.L. and Wild, E.W. (2006) Multisurface Proximal Support Vector Machine Classification via Generalized Eigenvalues. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28, 69-74. https://doi.org/10.1109/TPAMI.2006.17
[3]	Chen, W.J. and Tian, Y.J. (2010) Lp-Norm Proximal Support Vector Machine and Its Applications. Procedia Computer Science, 1, 2417-2423. https://doi.org/10.1016/j.procs.2010.04.272
[4]	Zhu, Z.F., Zhu, X.Q., Guo, Y.F., Ye, Y.D. and Xue, X.Y. (2012) Inverse Matrix-free Incremental Proximal Support Vector Machine. Decision Support Systems, 53, 395-405. https://doi.org/10.1016/j.dss.2012.02.007
[5]	Shao, Y.H., Deng, N.Y., Chen, W.J. and Wang, Z. (2013) Improved Generalized Eigenvalue Proximal Support Vector Machine. IEEE Signal Processing Letters, 20, 213-216. https://doi.org/10.1109/LSP.2012.2216874
[6]	Li, G.Q., Yang, L.X., Wu, Z.Y. and Wu, C.Z. (2021) D.C. Programming for Sparse Proximal Support Vector Machines. Information Sciences, 547, 187-201. https://doi.org/10.1016/j.ins.2020.08.038
[7]	Jayadeva, Khemchandani, R. and Chandra, S. (2007) Twin Support Vector Machines for Pattern Classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29, 905-910. https://doi.org/10.1109/TPAMI.2007.1068
[8]	Qi, Z.Q., Tiana, Y.J. and Shi, Y. (2012) Laplacian Twin Support Vector Machine for Semi-Supervised Classification. Neural Networks, 35, 46-53. https://doi.org/10.1016/j.neunet.2012.07.011
[9]	Guo, J.H., Yi, P., Wang, R.L., Ye, Q.L. and Zhao, C.X. (2014) Feature Selection for Least Squares Projection Twin Support Vector Machine. Neurocomputing, 144, 174-183. https://doi.org/10.1016/j.neucom.2014.05.040
[10]	Chen, S.G., Wu, X.J. and Yin, H.F. (2019) A Novel Projection Twin Support Vector Machine for Binary Classification. Soft Computing, 23, 655-668. https://doi.org/10.1007/s00500-017-2974-z
[11]	An, Y.X. and Xue, H. (2022) Indefinite Twin Support Vector Machine with DC Functions Programming. Pattern Recognition, 121, Article ID: 108195. https://doi.org/10.1016/j.patcog.2021.108195
[12]	Mehrkanoon, S., Huang, X.L. and Suykens, J.A.K. (2014) Non-Parallel Support Vector Classifiers with Different Loss Functions. Neurocomputing, 143, 294-301. https://doi.org/10.1016/j.neucom.2014.05.063
[13]	Huang, X.L., Shi, L. and Suykens, J.A.K. (2014) Asymmetric Least Squares Support Vector Machine Classifiers. Computational Statistics and Data Analysis, 70, 395-405. https://doi.org/10.1016/j.csda.2013.09.015
[14]	Sun, J., Fujita, H., Chen, P. and Li, H. (2016) Dynamic Financial Distress Prediction with Concept Drift Based on Time Weighting Combined with Adaboost Support Vector Machine Ensemble. Knowledge-Based Systems, 120, 4-14. https://doi.org/10.1016/j.knosys.2016.12.019
[15]	Wang, H.J., Shao, Y.H., Zhou, S.L., Zhang, C. and Xiu, N.H. (2021) Support Vector Machine Classifier via L0/1 Soft-Margin Loss. IEEE Transactions on Pattern Analysis and Machine Intelligence (Early Access). https://doi.org/10.1109/TPAMI.2021.3092177
[16]	Luo, L., Xie, Y.B., Zhang, Z.H. and Li, W.J. (2015) Support Matrix Machines. Proceedings of the 32nd International Conference on Machine Learning, Vol. 37, Lille, 6-11 July 2015, 938-947.
[17]	Cortes, C. and Vapnik, V. (1995) Support-Vector Networks. Machine Learning, 20, 273-297. https://doi.org/10.1007/BF00994018
[18]	Gao, X.Z., Fan, L.Y. and Xu, H.T. (2016) A Novel Method for Classification of Matrix Data Using Twin Multiple Rank SMMs. Applied Soft Computing, 48, 546-562. https://doi.org/10.1016/j.asoc.2016.07.003
[19]	Zheng, Q.Q., Zhu, F.Y. and Heng, P.A. (2018) Robust Support Matrix Machine for Single Trial EEG Classification. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 26, 551-562. https://doi.org/10.1109/TNSRE.2018.2794534
[20]	Kobayashi, T. and Otsu, N. (2012) Efficient Optimization for Low-Rank Integrated Bilinear Classifiers. Proceedings of the 12th European Conference on Computer Vision, Vol. 7573, Florence, 7-13 October 2012, 474-487. https://doi.org/10.1007/978-3-642-33709-3_34
[21]	Xu, H.T., Fan, L.Y. and Gao, X.Z. (2015) Projection Twin SMMs for 2D Image Data Classification. Neural Computing and Applications, 26, 91-100. https://doi.org/10.1007/s00521-014-1700-3
[22]	Zheng, Q.Q., Zhu, F.Y., Qin, J., Chen, B.D. and Heng, P.A. (2017) Sparse Support Matrix Machine. Pattern Recognition, 1-12.
[23]	Jiang, R. and Yang, Z.X. (2018) Multiple Rank Multi-Linear Twin Support Matrix Classification Machine. Journal of Intelligent and Fuzzy Systems, 35, 5741-5754. https://doi.org/10.3233/JIFS-17414
[24]	Pan, H.Y., Yang, Y., Zheng, J.D., Li, X. and Cheng, J.S. (2020) Symplectic Interactive Support Matrix Machine and Its Application in Roller Bearing Condition Monitoring. Neurocomputing, 398, 1-10. https://doi.org/10.1016/j.neucom.2020.01.074
[25]	Li, X., Yang, Y., Pan, H.Y., Cheng J. and Cheng, J.S. (2020) Non-Parallel Least Squares Support Matrix Machine for Rolling Bearing Fault Diagnosis. Mechanism and Machine Theory, 145, Article ID: 103676. https://doi.org/10.1016/j.mechmachtheory.2019.103676
[26]	Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2011) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 3, 1-122. https://doi.org/10.1561/2200000016
[27]	Lecun, Y., Bottou, L., Bengio, Y. and Haffner, P. (1998) Gradient-Based Learning Applied to Document Recognition. Proceedings of the IEEE, 86, 2278-2324. https://doi.org/10.1109/5.726791
[28]	Dalal, N. and Triggs, B. (2005) Histograms of Oriented Gradients for Human Detection. IEEE Conference on Computer Vision and Pattern Recognition, Vol. 1, San Diego, 20-25 June 2005, 886-893. https://doi.org/10.1109/CVPR.2005.177
[29]	Nazir, M., Ishtiaq, M., Batool, A., Jaffar, M.A. and Mirza, A.M. (2010) Feature Selection for Efficient Gender Classification. Proceedings of the 11th WSEAS International Conference on Nural Networks, Evolutionary Computing and Fuzzy Systems, Iasi, 13-15 June 2010, 70-75.
[30]	Lyonsa, M., Akamatsu, S., Kamachia, M. and Gyoba, J. (1998) Coding Facial Expressionswith Gabor Wavelets. 3rd IEEE International Conference on Automatic Face and Gesture Recognition, Nara, 14-16 April 1998, 200-205. https://doi.org/10.1109/AFGR.1998.670949
[31]	Cai, J.F., Candes, E.J. and Shen, Z.W. (2010) A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 20, 1956-1982. https://doi.org/10.1137/080738970
[32]	Chen, L., Sun, D.F. and Toh, K.C. (2015) A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems. Computational Optimization and Applications, 66, 327-343. https://doi.org/10.1007/s10589-016-9864-7