Enhanced Acceleration for Generalized Nonconvex Low-Rank Matrix Learning

I.   Introduction

In recent years, the recovery of low-rank matrices has found widespread applications in pattern recognition, machine learning, and computer vision [1]–[6]. This field encompasses various well-established methods, including robust principal component analysis (RPCA) [7], matrix completion (MC) [8], robust matrix completion (RMC) [9], low-rank representation (LRR) [10], and robust matrix regression (RMR) [11]. Additionally, several variants have been explored in recent research [12]–[16]. It is noteworthy that both RMC and LRR can be regarded as extensions of MC and RPCA. These fundamental concepts were originally introduced through rank minimization problems, as follows:

where $\lambda>0$ represents the regularization parameter. In both Problems (1) and (2), the symbol ${\boldsymbol{D}}$ represents the data matrix. We define ${\cal{P}}_{\varOmega}({\boldsymbol{Z}}_{i,j})$ as ${\boldsymbol{Z}}_{i,j}$ if $(i,j)\in\Omega$, and as $0$ otherwise. The rank of ${\boldsymbol{Z}}$ corresponds to the number of non-zero singular values in the matrix. We employ norms such as $\|\cdot\|_{\ell_q}^q$ (e.g., with $q>0$) and $\|\cdot\|_{\ell}$ (e.g., ${\ell}={\ell}_1, {\ell}_2$, or ${\ell}_{21}$-norm) to describe various residual styles, including Laplace, Gaussian, and column-elements, respectively. In Problem (3), ${\boldsymbol{D}}$ represents the testing sample matrix. The expression ${\cal{A}}({\boldsymbol{x}})= {\boldsymbol{x}}_1{\boldsymbol{A}}_1+ {\boldsymbol{x}}_2{\boldsymbol{A}}_2+\cdots +{\boldsymbol{x}}_n{\boldsymbol{A}}_n$ denotes a linear mapping from $\mathbb{R}^n$ to $\mathbb{R}^{p\times q}$ for each ${\boldsymbol{A}}_i$ belonging to $\mathbb{R}^{p\times q}$, respectively. We use ${\cal{A}}^*(\cdot)$ to represent its adjoint operation, and $\|{\boldsymbol{x}}\|_{\ell_q}^q$ signifies the coefficients representation norm, where $\ell_1$-norm and $\ell_2$-norm correspond to setting $q$ as $1$ and $2$, respectively. The convex norms mentioned above have been thoroughly examined in previous studies [14], [17]–[19].

In general, the problems presented in (1)–(3) are non-deterministic polynomial (NP)-hard and challenging to solve due to the nonconvex and nonsmooth nature of the rank function. Notably, this formulation extends several existing low-rank matrix recovery problems by replacing $f_\lambda({\boldsymbol{X}};p)$ with various norms, including the nuclear norm [8], Schatten-$p$ norm ($p>0$) [9], weighted Schatten-$p$ norm ($p>0$) [20], and weighted/truncated nuclear norm [21], [22]. Additionally, we demonstrate that convex and nonconvex ${\ell}_0$-norm relaxations (such as $\ell_p$-norm ($p>0$) [9], exponential-type penalty (ETP) [23], Laplace [24], and Geman [25]), listed in Table 1, can be extended to relax the rank function by acting on the singular values of matrix ${\boldsymbol{Z}}$ [20], [26], [27]. These properties naturally motivate us to develop feasible solutions to efficiently obtain low-rank solutions in a proper way. Moreover, our primary focus in this work centers on the investigation of problem formulations, optimization algorithms, and performance evaluations related to effective and efficient nonconvex low-rank matrix learning.

Table  1.  Several nonconvex $\ell_0$-norm relaxation formulations for low-rank matrix measurements

Function name	Function formula $f_{\lambda}({\boldsymbol{X}};p)$
$\ell_p$-norm [9]	$\sum\limits^r_{i=1} \lambda \sigma_i^p({\boldsymbol{X}})$
ETP [23]	$\sum\limits^r_{i=1} \frac{ \lambda(1-{\rm{exp}}(-p\sigma_i({\boldsymbol{X}})))}{1-{\rm{exp}}(-p)}$
Laplace [24]	$\sum\limits^r_{i=1} \lambda \left(1-{\rm{exp}}\left(- \frac{\sigma_i({\boldsymbol{X}})}{p}\right)\right)$
Geman [25]	$\sum\limits^r_{i=1} \frac{\lambda \sigma_i({\boldsymbol{X}})}{\sigma_i({\boldsymbol{X}})+p}$

 | Show Table

DownLoad: CSV

To optimize the previously mentioned minimization problems, it is necessary to introduce auxiliary variables to transform them into constrained problems rather than solving them directly. Here, on the one hand, building upon the principles established in Problems (1) and (2), we introduce the term $f_\lambda({\boldsymbol{X}};p)$ as a substitute for $\lambda{\rm{rank}}({\boldsymbol{X}})$, while $g({\boldsymbol{D}}-{\cal{A}}({\boldsymbol{Z}}))$ quantifies the loss function for a general nonconvex low-rank matrix learning problem, denoted as follows:

where both ${\boldsymbol{X}}$ and ${\boldsymbol{E}}$ are auxiliary variables. On the other hand, adopting a complementary approach, we replace the rank function with generalized nonconvex relaxations and employ $\|{\boldsymbol{x}}\|_{\ell_q}^q$ with $q=1, 2$ in Problem (3). This leads to the formulation of the following $\ell_q$-norm regularized problems:

where the $f_{\lambda}({\boldsymbol{E}};p)$ is also derived from Table 1. Especially, Problem (5) encompasses a broader scope than the models studied in [28] and [29], as the latter exclusively focus on specific instances involving Schatten-$p$ norms with $p=1, 2/3$, and $1/2$, respectively. In some real-world scenarios marked by significant occlusions and intense illuminations, nonconvex formulations consistently outperform their convex counterparts. This superiority is attributed to the extended matrix variate power exponential distribution [29], [30], which offers a more comprehensive depiction of pixel dependencies. Moreover, it features a heavier-tailed region that captures spatial structural information within residual images. Empirical results consistently validate the superior performance of nonconvex methods in recovering low-rank matrices from incomplete or corrupted data matrices.

It is crucial to highlight that the problems addressed in this work were previously explored in the conference papers [31], [32]. However, this work distinguishes itself by expanding upon these problems and developing a unified nonconvex low-rank matrix learning framework with more in-depth analysis and explanations. To visually illustrate the comparisons and differences, we present plotted curves of four nonconvex functions in Figure 1 and various demonstrations related to different types of noise and two low-rank matrix structures in Figure 2. These visualizations provide additional insights into the regularization term and the residual function for various real-world image applications. Meanwhile, it is noteworthy that we have successfully incorporated preliminary information into the objective terms, encompassing the loss function and coefficient term. This integration proves to be advantageous for enhancing the overall performance. Addressing constrained problems presents a substantial challenge in developing optimization algorithms that are both effective and efficient, particularly when dealing with multiple variables. This challenge is notably prominent in the study of widely utilized alternating direction method of multipliers (ADMM) algorithms [33]–[35].

Figure  1.  (a) Plots depict several convex and nonconvex $\ell_0$-norm functions; (b) Their corresponding supergradients; (c) Proximal operators. In these plots, we have set $\lambda=1.0$, $p\in\{0, 0.5,1.0\}$ for the $\ell_p$-norm, and $p=1.5$ for ETP, Geman, and Laplace, respectively.

DownLoad: Full-Size Img PowerPoint

Figure  2.  Visual comparisons presented for two common types of noise, as measured by both (a) the Frobenius norm and (b) the $\ell_{21}$-norm, and (c) and (d) comparisons made for two common types of low-rank matrix structures in within the term metrics of objective functions.

DownLoad: Full-Size Img PowerPoint

In comparison with [31] and [32], we have introduced an advanced acceleration technique using randomized singular value decomposition (RSVD) to alleviate the computational complexity associated with low-rank matrix computations. This represents a significant departure from our earlier conference papers, which relied on traditional ADMM algorithms with either full or economical singular value decomposition (SVD) [6], [22], [36]. Moreover, the problems under investigation involve two constrained equations, and the concept of low-rankness holds specific significance within the context of the measurements incorporated into the objective function. Additionally, we have provided comprehensive theoretical analyses from two perspectives, including computational complexity and convergence guarantees. Finally, we also conducted extensive experimental comparisons with several closely related works to validate the superiority of our proposed methodologies across various application tasks in terms of computational efficiency and efficacy. In summary, compared to previously published conference works, we have achieved notable improvements in model explanations, efficient algorithm designs, comparison methods, and application tasks, respectively.

Building upon these insights and the existing body of researches, which aims to reduce computational complexity and enlarge real-world image applications, we can distill the primary contributions of this work as follows:

Model formulation We have established a unified nonconvex low-rank matrix relaxation framework by extending RMC, LRR, and RMR. This approach yields nearly unbiased estimators compared to nuclear norm-based regularization problems, thereby elevating the overall solution quality. Our rank relaxation functions are derived from nonconvex relaxations of the $\ell_0$-norm, which we apply to the singular values of the target low-rank matrix. This renders the proposed problem formulation exceptionally robust, versatile, and applicable to a wide range of image processing tasks.

Algorithm design Our algorithm designs involve the development of a nonconvex ADMM method with two dual variables, eliminating the need for linearization strategies. Each subproblem can be solved to obtain a closed-form solution. To further enhance acceleration, we incorporate RSVD in the low-rank matrix updates and also utilize orthogonal factorization techniques and parallel strategies. Additionally, we provide theoretical guarantees, demonstrating that the variable sequence generated by nonconvex ADMM is bounded. Moreover, during local convergence analysis, we show that a subsequence converges to a stationary point. The limiting point satisfies the Karush-Kuhn-Tucker (KKT) conditions under more lenient assumptions.

Experimental validation In our experimental results, we demonstrate the superior recovery performance of our proposed nonconvex methods when compared to convex counterparts and other relevant techniques in the domains of matrix completion, subspace clustering, image classification, and image reconstruction using various real-world datasets. Our evaluations cover a diverse range of low-level and high-level vision tasks within the realms of computer vision and pattern recognition. These experimental tasks serve to reinforce the effectiveness and efficiency of our methods through both quantitative and qualitative comparisons.

The following sections are organized as follows: In Section II, we introduce the generalized nonconvex low-rank matrix learning problems and explore their connections with the related work from various perspectives. Section III delves into the development of the multiple variables ADMM optimization algorithm with some acceleration strategies to enhance the computational efficiency for three distinct low-rank matrix optimization problems. We provide a comprehensive theoretical analysis, covering aspects such as computational complexity and convergence properties. Section IV presents a wide array of experiments designed to validate the performance and computational advantages of our proposed method. Finally, in Section V, we conclude our work, providing a summary and outlining potential future directions.

II.   Further Analysis of Problem Formulations

In the upcoming sections, we will delve into the concrete analysis of the constrained Problems (4) and (5). Our initial focus will be on unveiling the significance of each component within the objective function and investigating their connections to existing low-rank matrix learning problems. Building upon these foundational insights, we will embark on a comprehensive analysis of the generalized nonconvex low-rank matrix learning methods and their various extensions, as represented in Figure 3. This diagram provides a comprehensive overview of the research framework of this work from multiple aspects including problem formulations, algorithm design and analysis, and application tasks.

Figure  3.  Research framework for the generalized nonconvex low-rank matrix learning methods including problem formulations, ADMM algorithms, and various low-level image vision applications.

DownLoad: Full-Size Img PowerPoint

It can be observed that the objective functions in both Problems (4) and (5) are composed of a regularization term and a residual function, each serving a distinct purpose. To illustrate, $f_\lambda({\boldsymbol{X}};p)$ quantifies the regularization term for the low-rank matrix in Problem (4), whereas $f_\lambda({\boldsymbol{E}};p)$ characterizes the residual function for the low-rank matrix in Problem (5). This formulation’s versatility enables us to tailor the low-rank constraints to various generalized learning problems within the realm of low-level image vision tasks. Furthermore, our research highlights the significance of $\|\cdot\|_{\ell}$ and $\|\cdot\|_{\ell_q}^q$ norms and their connection to the formulation of both convex and nonconvex norms. This analysis underscores the diverse roles played by different norms in defining residual and coefficient styles, as mentioned earlier.

To the best of our knowledge, the adoption of the nonconvex $\ell_0$-norm function to relax the rank function is widely recognized as a more effective approach, as supported by prior research. Emphasizing the versatility and broad applicability of Problems (4) and (5), we conduct comparisons and establish connections with various existing works, centering our discussion on three key perspectives, outlined as follows:

• Differences in problem formulations: Existing rank relaxation techniques [9], [26], [37], [38] involve calculating the sum of all singular values associated with specific functions to quantify the second-order sparsity of the low-rank matrix. This further served as establishing generalized nonconvex low-rank matrix learning problems. Notably, our work addresses these minimization problems within a unified framework, eliminating the need for individual case-by-case formulations and providing a versatile solution with proper meanings.

• Optimization using first-order algorithms: To achieve the desired solution, one can employ ADMM [13], [35], [39], [40] for handling constrained minimization problems. Alternatively, accelerated proximal gradient algorithm (APG) [41]–[44] and iteratively reweighed algorithm (IRA) [14], [45] are tailored for unconstrained minimization problems. Importantly, to maintain closed-form solutions without relying on linearization techniques, unlike many existing approaches [26], [46]–[49], we also favor the use of ADMM algorithms to effectively tackle the constrained Problems (4) and (5) while incorporating the acceleration strategy for improving the computational efficiency.

• Applications in image low-level and high-level vision: Depending on the specific application cases [2], [3], Problem (4) can find applications in tasks such as image inpainting (as in matrix completion methods) and image clustering (as in subspace segmentation methods). Additionally, Problem (5) is applicable in image classification and reconstruction (as in matrix regression methods). These various low-level applications are underpinned by the construction of meanings for the objective terms.

III.   Optimization Scheme of ADMM

In this section, we introduce an efficient algorithm that integrates faster low-rank matrix computation to enhance the efficiency of ADMM. Our primary objective is to provide an analysis of the iteration procedures, computational complexity, and convergence properties. Therefore, we will outline the step-by-step solution for Problems (4) and (5) below.

1   Faster low-rank matrix computation

To enhance computational efficiency and reduce the complexity of the optimization algorithm, we introduce a faster proximal operator for low-rank matrices. This approach involves calculating a smaller matrix for the proximal operator, leading to a significant reduction in its size as in [50]–[52]. By offering a closed-form solution for computing the proximal operator related to low-rank matrices, the following proposition greatly improves the algorithm’s computational efficiency and reduces complexity at each iteration. The primary challenge in solving for low-rank matrices is computing the proximal operators, which often involve convex and nonconvex rank relaxations and typically require the computation of the full SVD in most cases.

To enhance the computational efficiency, we propose an acceleration technique known as randomized SVD. This technique reduces computational complexity and enables faster updates, as described below.

Proposition 1 Suppose that ${{\rm{rank}}}({\boldsymbol{X}})=r<d\leq {\rm{min}}(m,n)$, ${\boldsymbol{Q}}\in\mathbb{R}^{m\times d}$ is an orthogonal matrix satisfying ${\boldsymbol{Q}}^{\mathrm{T}}{\boldsymbol{Q}}={\boldsymbol{I}}$, and ${\boldsymbol{Y}}\in\mathbb{R}^{d\times n}$ such that ${\boldsymbol{X}}={\boldsymbol{QY}}$. Then, the proximal operator ${\rm{Prox}}^h_{\lambda}({\boldsymbol{Q}}^{\mathrm{T}}{\boldsymbol{Z}})$ is the solution to

where we have $h_{\lambda}({\boldsymbol{Y}})=\sum^d_{i=1}h_{\lambda}(\sigma_i({\boldsymbol{Y}}))$, $\|{\boldsymbol{X}}-{\boldsymbol{P}}\|_{F}^2 = \|{\boldsymbol{Y}}-{\boldsymbol{Q}}^{\mathrm{T}}{\boldsymbol{P}}\|_{\mathrm{F}}^2$, and the matrices ${\boldsymbol{X}}$ and ${\boldsymbol{Y}}$ have the same singular values. Therefore, by finding the optimal ${\boldsymbol{Y}}^*={\rm{Prox}}^h_{\lambda}({\boldsymbol{Q}}^{\mathrm{T}}{\boldsymbol{P}})$, we have the desired matrix ${\boldsymbol{X}}^*= {\boldsymbol{QY}}^*$.

Based on von Neumann’s theorem [53], which presents a series of transformations, we initially perform the SVD of a matrix, denoted as ${\boldsymbol{U}}{\boldsymbol{\varSigma}}{\boldsymbol{V}}^{\mathrm{T}}$ without loss of generality. Here, ${\boldsymbol{U}}$ and ${\boldsymbol{V}}$ represent the left and right singular vector matrices, and $\boldsymbol{\varSigma}$ is the diagonal singular value matrix with its $i$-th element denoted as $\sigma_{i}$ for $1\leq i\leq l={\rm{min}}(m,n)$. By leveraging Proposition 1, we achieve a significant reduction in computational complexity, especially when $d\leq{\rm{min}}(m,n)$. This reduction implies that fewer singular values need to be calculated, resulting in faster execution time. This underscores the importance of the proximal operator extension from (6) in obtaining the optimal solution and approximating the matrix through the accelerated generalized singular value thresholding (GSVT) [2], [47] for solving the subsequent low-rank matrix-related subproblems, which are not considered in the existing works [31], [32].

2   Detailed optimization procedures

Following the principles of multiple ADMM [33]–[35] for solving constrained optimization problems, we employ an iterative procedure to efficiently address Problems (4) and (5), respectively. This iterative process entails the sequential update of the relevant variables. Our choice is rooted in the constrained nature of the problems in question, where each subproblem can be efficiently computed with a closed-form solution, rendering the ADMM algorithms a fitting choice.

1   Optimization algorithm for Problem (4)

To facilitate the computation of a closed-form solution for each subproblem, one can transform Problem (4) into the following unconstrained problem. Subsequently, we adopt the augmented Lagrange function in the following form:

here, $\mu>0$ is the penalty parameter, and both $\varLambda_1$ and $\varLambda_2$ represent the dual variables. It is important to highlight that (7) functions as the augmented Lagrange function for (4). The terms involving $\|\cdot\|^2_{F}$ represent the differentiable term introduced in [10], [21], and [54]. Note that this iteration process aims to achieve the low-rank matrix solution derived from the RMC and LRR problems.

Building upon the previously introduced augmented Lagrange function and considering the variables at the $k$-th iteration $({\boldsymbol{Z}}_k, {\boldsymbol{E}}_k, {\boldsymbol{X}}_k, \varLambda_{1,k}, \varLambda_{2,k}, \mu_k)$, the iterative process entails sequential updates of the primal variables, dual variables, and the penalty parameter. Consequently, to eliminate the need for linearization techniques, the variables at the $(k+1)$-th iteration can be updated as follows:

where $\widehat{\boldsymbol{X}}^{k}_{\varLambda_{1,k}} = {\boldsymbol{X}}_{k}+\frac{\varLambda_{1,k}}{\mu_k}$, $\widehat{\boldsymbol{E}}^k_{\varLambda_{1,k}} = {\boldsymbol{D}}-{\boldsymbol{E}}_k-\frac{\varLambda_{2,k}}{\mu_k}$, $\widehat{{\boldsymbol{Z}}}^{k+1}_{\varLambda_{2,k}} = {\boldsymbol{D}}-{\cal{A}}({\boldsymbol{Z}}_{k+1})-\frac{\varLambda_{2,k}}{\mu_k}$, and $\widehat{{\boldsymbol{Z}}}^{k+1}_{\varLambda_{1,k}} = {\boldsymbol{Z}}_{k+1}-\frac{\varLambda_{1,k}}{\mu_k}$. Meanwhile, we also need to update the dual variables and the penalty parameter, as follows:

where the number of iterations is significantly influenced by the choice of $\rho$ values. Specifically, a larger value of $\rho$ generally results in faster convergence, whereas a smaller value of $\rho$ tends to yield a more accurate solution.

In the updated process, solving subproblem (8) involves addressing a quadratic problem, while subproblem (10) requires computing proximal operators using a fixed-point iteration algorithm for various formulations of the function $f_{\lambda}({\boldsymbol{X}})$, as detailed in Proposition 1 for the RMC method, focused on enhancing computational efficiency. We consider a “dictionary” that linearly spans the data space, which helps reduce computational complexity, as employed in the LRR method. Both of the aforementioned acceleration techniques are designed to minimize computational complexity. As demonstrated in [10], the lowest-rank representation can recover the underlying row space, thereby revealing the true data segmentation. Moreover, the optimal solver for subproblem (9) can be adapted based on different choices of $g({\boldsymbol{E}})$, such as ${\ell}_1$, ${\ell}_2$, or ${\ell}_{21}$ norms for various noise measurements. The initial values for the variables are set as $({\boldsymbol{Z}}_0, {\boldsymbol{E}}_0, {\boldsymbol{X}}_0, \varLambda_{1,0}, \varLambda_{2,0}, \mu_0)$. To assess convergence, we have established stopping criteria based on the following formula:

where $\epsilon=0.00001$. In summary, the detailed iteration procedure of the nonconvex ADMM with two dual variables for solving (4) using the augmented Lagrange function (7) is presented in our Algorithm 1.

2   Optimization algorithm for Problem (5)

To derive the vector of representation coefficients, we employ the foundational iteration procedures of ADMM to optimize Problem (4). These steps entail the sequential updates of variables and the penalty parameter. Throughout the optimization process, the availability of closed-form solvers is particularly crucial, especially when dealing with $\ell_q$-norms in Problem (5), where we set $q$ to 1, as extensively discussed in [11], [29], and [55]. Particularly, for the case of $q=2$, we omit the introduction of the auxiliary variable ${\boldsymbol{z}}$ and eliminate the use of the constrained equation ${\boldsymbol{x}}={\boldsymbol{z}}$ due to the differentiable property of $\|{\boldsymbol{x}}\|_{\ell_2}^2$. You can find further details in [11] and [32]. In this work, our focus is specifically on the optimization iterations for the case of $q=1$, which are elaborated upon in the following two primary steps:

Step 1 By introducing the dual variables $\varLambda_1$ and $\varLambda_2$, we formulate the augmented Lagrangian function for Problem (5) only with $q=1$, represented as

where this function formulation follows the same processing procedure as the previously described function (15). Then, we proceed to present the variables updated below.

Step 2 By alternately updating each variable in the objective function (15), we also take into account the variables at the $k$-th iteration and then present the following iteration sequences for the $(k+1)$-th iteration:

i) In the above-given function, while keeping $\widehat{\boldsymbol{x}}_{\varLambda_{1, k}}= {\boldsymbol{D}}-{\cal{A}}({\boldsymbol{x}}_k)-\frac{\varLambda_{1, k}}{\mu_k}$ fixed, we can update ${\boldsymbol{E}}$ through the following minimization subproblem:

and the closed-form solution can be achieved by using the generalized low-rank matrix computations [2], [47].

ii) Fixing $\widehat{\boldsymbol{E}}_{\varLambda_{1,k}} ={\boldsymbol{D}}-{\boldsymbol{E}}_{k+1}-\frac{\varLambda_{1,k}}{\mu_k}$, we subsequently update $({\boldsymbol{z}}, {\boldsymbol{x}})$ from (15) by

iii) Using the updated variables ${\boldsymbol{E}}_{k+1}$, ${\boldsymbol{z}}_{k+1}$, and ${\boldsymbol{x}}_{k+1}$ obtained from the previous steps, we proceed to update $(\varLambda_1,\varLambda_2)$ and $\mu$ according to the following equations:

where (19) and (20) are employed for the dual variables, while (21) is utilized for updating the penalty parameter in this process.

In updating the involved variables, analytical solutions for subproblems (16)–(18) can be readily obtained by computing the derivatives of (18) with respect to ${\boldsymbol{x}}$ and setting them to zero. Furthermore, the subproblem (17), which is based on the $\ell_1$-norm, can be solved exactly using the well-known soft-thresholding operator [56]. The subproblem (16), which relies on $f_{\lambda}({\boldsymbol{E}};p)$, also has a closed-form solution [2], [47]. In summary, the iteration procedures for solving Problem (5) using the nonconvex ADMM are outlined in Algorithm 2. The iterations continue until either reaching the maximum iteration limit $k_\text{max}$ or satisfying the predefined stopping criterion, which is set to $\varepsilon=0.001$, as specified in (14).

3   Algorithm analysis

In this subsection, we begin by examining the computational complexity of Algorithms 1 and 2. The computational complexity is influenced by the SVD computations and matrix multiplications carried out during each iteration, as well as the total number of iterations. We then proceed to establish convergence guarantees, relying on the updated rules and the properties of the objective function. The detailed analysis is presented below from two perspectives.

1) Computational complexity of Algorithms 1 and 2: The factorization technique efficiently computes an orthogonal matrix ${\boldsymbol{Q}}\in\mathbb{R}^{m\times d}$, enabling a small SVD of ${\boldsymbol{Q}}^{\mathrm{T}}{\boldsymbol{Z}}\in\mathbb{R}^{d\times n}$ to be performed in $O(nd^2)$ time. This method reduces the time complexity of obtaining ${\boldsymbol{Z}}^*$ to $O(mnd)$ due to the multiplication of two matrices of sizes $m\times n$ and $n\times d$. In contrast, the complexity for computing the matrix inverse is $O(n^3)$ for a matrix size of $n\times n$. The overall complexity of Algorithms 1 and 2 is determined by the complexity of each iteration multiplied by the total number of iterations.

2) Convergence guarantees of Algorithm 1: The convergence analysis encompasses two technical results, which are presented respectively as follows:

Lemma 1 Let $\{\varTheta_k=({\boldsymbol{Z}}_k, {\boldsymbol{E}}_k, {\boldsymbol{X}}_k, \varLambda_{1,k}, \varLambda_{2,k})\}$ be the sequence generated by nonconvex ADMM, and assume that $\sum^k_{i=0}\frac{1}{\mu_i}<+\infty$ holds. Then $\{\varTheta_k\}$ is a bounded variable sequence.

Theorem 1 Let $\{\varTheta_k=({\boldsymbol{Z}}_k, {\boldsymbol{E}}_k, {\boldsymbol{X}}_k, \varLambda_{1,k}, \varLambda_{2,k})\}$ be the sequence generated by nonconvex ADMM, assume $\lim\limits_{j\rightarrow +\infty}\mu_{k_j} \left({\boldsymbol{X}}_{k_j + 1} - {\boldsymbol{X}}_{k_j}\right)={0}$, $\lim\limits_{j\rightarrow +\infty}\mu_{k_j} \left({\boldsymbol{E}}_{k_j} - {\boldsymbol{E}}_{k_j + 1}\right) ={0}$, then any accumulation point $\varTheta_*=({\boldsymbol{Z}}_*, {\boldsymbol{E}}_*, {\boldsymbol{X}}_*, \varLambda_{1,*}, \varLambda_{2,*})$, it satisfies

as well as both ${\boldsymbol{X}}_{*}={\boldsymbol{Z}}_{*}$ and ${\boldsymbol{D}}={\boldsymbol{E}}_{*}+{\cal{A}}({\boldsymbol{Z}}_{*})$.

Hence, the above results accord to the desired conclusions as having provided in [31]. In other words, the limiting point $({\boldsymbol{Z}}_*, {\boldsymbol{E}}_*, {\boldsymbol{X}}_*, \varLambda_{1,*}, \varLambda_{2,*})$ satisfies the KKT conditions of (7) and $({\boldsymbol{Z}}_*, {\boldsymbol{E}}_*, {\boldsymbol{X}}_*)$ is a stationary point of Problem (4), respectively. This provides the local convergence property of Algorithm 1.

3) Convergence guarantees of Algorithm 2: The convergence analysis yields similar theoretical results to those presented in Algorithm 1, which are given as follows:

Lemma 2 Suppose that $\sum_i f(\sigma_i({\boldsymbol{D}}-{\cal{A}}({\boldsymbol{x}})))+ \lambda\|{\boldsymbol{x}}\|_{\ell_q}^q \rightarrow + \infty$ iff $\|{\boldsymbol{x}}\|\rightarrow +\infty$ and we assume that $\mu_{k-1}\left({\boldsymbol{x}}_{k-1}-{\boldsymbol{x}}_k\right)\rightarrow {\boldsymbol{0}}$ as $k\rightarrow +\infty$, then the dual variable sequences $\{\varLambda_{1,k}\}$ and $\{\varLambda_{2,k}\}$ generated by Algorithm 2 are both bounded.

Theorem 2 Let $\{{\cal{T}}_k=({\boldsymbol{E}}_k, {\boldsymbol{z}}_k, {\boldsymbol{x}}_k, \varLambda_{1,k},\varLambda_{2,k})\}$ be the sequence generated by Algorithm 2 for the case $p=1$, which has at least one accumulation point under the same assumptions with Lemma 2 and $\sum^{+\infty}_{i=0} \frac{\mu_i+\mu_{i+1}}{2\mu_i^2}< +\infty$. Then, for any accumulation point ${\cal{T}}_*=({\boldsymbol{E}}_*, {\boldsymbol{z}}_*, {\boldsymbol{x}}_*, \varLambda_{1,*}, \varLambda_{2,*})$, and the $({\boldsymbol{E}}_*, {\boldsymbol{z}}_*, {\boldsymbol{x}}_*)$ is a stationary point of Problem (5).

Through the proof procedures provided in Theorems 1 and 2 above, we further establish the boundedness of primal variable sequences, as demonstrated in Lemmas 1 and 2. In essence, we confirm that any accumulation point attained from Algorithms 1 and 2 qualifies as a stationary point. It is worth noting that the local convergence proofs for these results exhibit similarities under comparable conditions and slight revisions. In addition, the elaborate proofs for these analyses are available in the previously published conference papers [31], [32]. For the sake of brevity and space conservation, we have omitted them in this work.

IV.   Numerical Experiments

In this section, our main objective is to showcase the superior learning efficacy and computational efficiency of nonconvex rank regularization methods in addressing RMC, LRR, and RMR problems, as respectively formulated in Problems (4) and (5). We aim to provide theoretical insights into their convergence properties and present visual results from various viewpoints, covering a range of vision tasks, including image inpainting, clustering, classification, and reconstruction. This section offers a considerably more comprehensive overview and validation than the previously published conference papers [31], [32], which focused solely on the proposed methods for the experimental comparisons to validate the evaluation efficacy and computational efficiency. Please notice that although the proposed methods have not yet achieved the highest level of computational efficiency, we have successfully validated the effectiveness of the enhanced acceleration technologies employed in our approaches.

In the subsequent experiments, our primary focus is on benchmarking our proposed methods against several existing algorithms, utilizing notations commonly found in pertinent references. The comparison works are sourced from the corresponding journal publications and conference proceedings. These experiments are conducted using databases containing raw images and are executed on Matlab 2021b, running on a personal computer with 8.0 GB of RAM and an Intel(R) Core(TM) i7-7700 CPU@3.60 GHz. The forthcoming descriptions of experimental tasks and evaluations cover various perspectives, detailed below.

• In the first experiment, we employ matrix completion methods to robustly recover a natural image with missing entries, as shown in Figure 4. The initial image has dimensions of $600\times600\times3$, as shown in Figure 4(a). Subsequently, we truncate this image to create an incomplete version, treating it as a strictly low-rank matrix with a rank of 80, as depicted in Figure 4(b). The introduction of missing entries through text generates an image with incomplete sections, demonstrated in Figure 4(c). Considering that the image comprises three channels (red, green, and blue), we independently complete the missing pixel parts for each channel and then merge the results to achieve optimal inpainting performance. Our evaluation criteria include metrics such as peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) [2], [52]. Additionally, we assess computational efficiency in terms of CPU computation time (TIME) and the number of iterations (ITER). It is noteworthy that higher PSNR and SSIM values, coupled with lower TIME and ITER values, indicate the superiority of the evaluated methods to some degree.

Figure  4.  A series of visual images and plotted curves depicting three scenarios. These plotted curves correspond to the red (R), green (G), and blue (B) channels, highlighting the significance of singular values in image inpainting tasks.

DownLoad: Full-Size Img PowerPoint

• In the second experiment, we apply clustering methods for subspace segmentation to the ExtYaleB ¹ dataset, which features face images from 38 subjects. Each image is resized to dimensions of $32\times32$ pixels. Raw matrices ${\boldsymbol{D}}$ are created with sizes of $1024\times320$ and $1024\times640$ by selecting the first 5 and 10 subjects, respectively. You can view partial face images in Figure 5. To evaluate the clustering results [57], [58], we employ metrics including clustering accuracy (ACC), normalized mutual information (NMI), and TIME. Additionally, we construct an affinity matrix ${\boldsymbol{W}}$ based on the optimal ${\boldsymbol{X}}^*$, calculated as $(|{\boldsymbol{X}}|+|{\boldsymbol{X}}^{\mathrm{T}}|)/2$. Higher ACC and NMI values, along with lower TIME values, indicate superior performance and computational efficiency for the methods under consideration.

Figure  5.  Partial face images with various illumination corruptions from the ExtYaleB database used for subspace clustering tasks.

DownLoad: Full-Size Img PowerPoint

• In the third experiment, we employ regression techniques for image classification using two well-established face databases: AR ² and ExtYaleB (same as above-given). These databases contain partial face images, as shown in Figure 6, with various occlusions like sunglasses, scarves, and baboons added to challenge the testing samples. Our training sets consist of clean face images selected based on predefined criteria [11], [28]. We optimize Problem (5) using Algorithm 2 to obtain optimal coefficient vectors for two scenarios. To establish class decisions, we use the rule ${\rm{identity}}({\boldsymbol{D}})=$ ${\rm{argmin}}_i {\widetilde{\boldsymbol{E}}}_i({\boldsymbol{D}})$ for $i=1,2,\ldots ,n$, where ${\widetilde{\boldsymbol{E}}}_i({\boldsymbol{D}})$ is computed as $\frac{f\left(\sigma[{\cal{A}}({\boldsymbol{x}}{*}) -{\cal{A}}(\zeta_i({\boldsymbol{x}}{*}))]\right)}{|\zeta_i({\boldsymbol{x}})|}$, with ${\boldsymbol{x}}$ representing the optimal solution for each testing sample and $\zeta_i({\boldsymbol{x}}_{*})$ corresponding to the associated $i$-th class. Note that all the testing samples are processed in parallel to enhance computational efficiency.

Figure  6.  Partial face images from (a) the AR dataset, which include occlusions like sunglasses and scarves and (b) the ExtYaleB dataset with random baboon occlusions utilized for training and testing in image classification tasks.

DownLoad: Full-Size Img PowerPoint

• In the fourth experiment, we mainly conduct numerical assessments to validate the reconstruction capabilities of the proposed methods in both clustering and classification tasks. Our analysis begins by presenting the reconstructed and residual images from the illuminated ExtYaleB dataset. Furthermore, we meticulously curate two sets of face images, one from the AR dataset and another from the ExtYaleB dataset. One set comprises clean face images, while the other set features face images with three different occlusions. We apply the provided methods, leveraging four nonconvex functions for both clustering and classification tasks, respectively. Our particular emphasis is on comparing the reconstruction images and the residual images from these two vision tasks. In particular, the reconstruction images are achieved using the coefficient matrix and vector, while the residual images are obtained from the error matrix in the iteration process.

1   RMC for image inpainting

This experiment aims to assess the performance of Algorithm 1 in optimizing the RMC problem for image inpainting. Subsequently, we evaluated the efficiency and effectiveness of several existing completion methods, resulting in the following observations from two key perspectives:

• Table 2 presents the inpainting results, evaluating our proposed methods across four different nonconvex functions. It includes a comprehensive comparison with various methods, encompassing both convex and nonconvex approaches, some of which incorporate acceleration techniques. The table features diverse methods and their respective outcomes, comparing values of PSNR, SSIM, TIME, and ITER. It is worth noting that for the $\ell_p$-norm and ETP, we chose $p=0.5$, whereas for the Laplace and Geman functions, we utilized $p=0.001$. The findings reveal that convex methods such as APG and augmented Lagrange multipliers (ALM) yield lower PSNR and SSIM values. Please note that ALM originates from the work presented in the arXiv preprint arXiv:1009.5055. We here substituted this reference with [46] to ensure the availability of a DOI number. In contrast, nonconvex methods, including iteratively reweighted nuclear norm (IRNN), generalized proximal gradient (GPG), partial singular value thresholding (PSVT), weighted nuclear norm minimization (WNNM), accelerated proximal alternating linearized minimization (AccPALM), and L$_p$TNN (the model combining L$_p$-norm and the truncated nuclear norm), demonstrate superior performance, with notable effectiveness observed for both WNNM and AccPALM. Moreover, the utilization of acceleration techniques results in more efficient computations, as evident by ALM, IRNN, GPG, and AccPALM, which exhibit reduced iteration counts and/or lower computational time. It is obvious that these results underscore the advantages of our proposed methods, optimized by Algorithm 1, in terms of both inpainting efficacy and computational efficiency compared to most of the comparison methods.

Table  2.  Numerous results presented for image inpainting to evaluate performance and computational efficiency

Method	PSNR	SSIM	TIME (s)	ITER
APG [42]	50.697	0.9997	78.2	(354, 365, 338)
ALM [46]	50.864	0.9997	24.0	(96, 92, 100)
IRNN [26]	51.905	0.9998	21.6	(68, 68, 68)
GPG [47]	52.064	0.9998	21.7	(70, 69, 69)
PSVT [59]	50.921	0.9997	46.9	(160, 163, 165)
WNNM [21]	55.872	0.9999	132.9	(457, 593, 592)
AccPALM [52]	54.234	0.9998	12.6	(101, 103, 105)
${\mathrm{L}}_{2/3}$TNN [60]	50.895	0.9997	374.1	(90, 91, 93)
${\mathrm{L}}_{1/2}$TNN [60]	50.895	0.9997	350.9	(88, 89, 91)
${\mathrm{ADMM}}_{\ell_p}$	52.844	0.9998	20.0	(177, 177, 179)
${\mathrm{ADMM}}_{\text{ETP}}$	52.144	0.9997	20.1	(180, 180, 186)
${\mathrm{ADMM}}_{\text{Laplace}}$	51.910	0.9997	19.7	(178, 178, 181)
${\mathrm{ADMM}}_{\text{Geman}}$	52.227	0.9997	18.5	(177, 178, 176)

 | Show Table

DownLoad: CSV

• To evaluate our proposed methods under four nonconvex functions, we initiated the assessment by plotting convergence curves of the stopping condition for the $\ell_p$-norm and ETP. These plots illustrate the relationship between ITER and TIME, as shown in Figures 7(a) and (b), respectively. Furthermore, we presented the influence of different parameter choices for the $p$-value in the Laplace function and the initial $\bar{\mu}$-value, which is used for the initial penalty parameter (i.e., $\frac{\bar{\mu}}{\|{\boldsymbol{D}}\|_2}$) under the case of the Geman function on evaluation performance, as demonstrated in Figures 7(c) and (d). To sum up, these analyses not only validate the convergence properties of our approaches but also provide valuable insights into the multifaceted effects of various parameters.

Figure  7.  Curves showing the stopping function over ITER and TIME for (a) the $\ell_{p}$-norm and (b) the ETP, respectively, and the effects on PSNR values under different values of $\rho$ and $\bar{\mu}$ for (c) the Laplace function and (d) the Geman function, correspondingly.

DownLoad: Full-Size Img PowerPoint

2   LRR for image clustering

This subsection is dedicated to conducting a comprehensive comparison of subspace segmentation methods, which includes assessing both convex and nonconvex rank relaxation methods, as well as low-rank matrix factorization-based approaches. Our evaluation focuses on the unsupervised clustering task using the ExtYaleB dataset, considering scenarios with 5 and 10 subjects. Following this, we provide quantitative and qualitative results, along with highlighting significant observations, described as follows:

• Table 3 presents a comprehensive comparison of various clustering methods and exhibits advantages across four nonconvex functions. In the specific scenarios of our evaluations, it is apparent that LRR, least squares regression (LSR1, LSR2), and fast universal low rank representation (FULRR) exhibit relatively lower ACC and NMI values, along with less time consumption. In contrast, iteratively reweighted least squares (IRLS), smooth representation (SMR), the FULRR, Schatten-1/2 norm factorization based on subspace clustering (S_1/2NFSC), Schatten-2/3 norm factorization based on subspace clustering (S_2/3NFSC), AccPALM, and weighted schatten-p norm based on LRR (WsLRR) demonstrate improved ACC and NMI values compared to convex methods. Notably, LSR and SMR stand out for their higher efficiency in terms of computational costs. Furthermore, S_1/2NFSC, S_2/3NFSC, FULRR, WsLRR, and AccPALM leverage matrix factorization acceleration techniques and iteration reduction strategies, enabling them to efficiently achieve low-rank matrices with results that either outperform or match other methods. This naturally aligns with expectations since these nonconvex methods have been intentionally designed to strike a balance between accuracy and efficiency by using Algorithm 1 to optimize Problem (4).

Table  3.  Comparisons of numerical results for subspace segmentation using the ExtYaleB dataset with 5 and 10 subjects

Method	5 subjects			10 subjects
	ACC (%)	NMI (%)	TIME (s)	ACC (%)	NMI (%)	TIME (s)
LRR [10]	79.375	81.636	7.7	75.313	79.285	29.3
IRLS [61]	89.688	81.656	17.5	72.969	66.017	93.4
LSR1 [62]	94.063	87.481	$<$lt; $1	60.000	53.131	$<$lt; $1
LSR2 [62]	95.625	92.173	$<$lt; $1	58.125	51.218	$<$lt; $1
SMR [63]	94.688	86.634	$<$lt; $1	69.375	67.096	$<$lt; $1
FULRR [64]	90.313	79.606	12.1	84.063	77.463	43.4
WsLRR [65]	96.875	91.554	8.2	76.719	77.289	33.8
S1/2NFSC [57]	86.563	74.753	3.1	75.000	75.207	10.0
S2/3NFSC [57]	88.750	77.842	3.1	73.750	75.018	10.4
AccPALM [52]	89.063	76.065	$<$lt; $1	70.469	62.672	3.5
${\mathrm{ADMM}} _{\ell_p}$	97.500	92.900	2.1	84.063	79.192	9.8
${\mathrm{ADMM}}_{\rm{ETP}}$	97.813	93.888	1.8	85.469	80.672	9.0
${\mathrm{ADMM}}_{\rm{Laplace}}$	96.563	91.300	2.4	84.844	80.065	10.4
${\mathrm{ADMM}} _{\rm{Geman}}$	97.188	93.059	2.3	84.688	79.967	10.3

 | Show Table

DownLoad: CSV

• Figure 8 offers visual comparisons for our proposed methods employing four different nonconvex functions with 5 subjects in Figures 8(a) and (b) and 10 subjects in Figures 8(c) and (d), respectively. In Figure 8(a), we present the block-diagonal structures of the coefficient matrix with normalization, shedding light on their relationship with the number of subjects for the $\ell_{p}$-norm. Moving to Figure 8(b), we display the statistical distribution of the coefficient matrix, offering insights into the representation of clustering samples related to the ETP function. Meanwhile, Figure 8(c) allows us to analyze the impact of parameter choices through experiments on the Laplace function. Finally, we provide an analysis of the influences of randomly initialized variables on clustering accuracy in Figure 8(d) based on the Geman norm through 1000 runs. These visual results enhance the understanding of our proposed methods, thereby confirming their feasibility and stability from various viewpoints in this unsupervised task.

Figure  8.  (a) and (b) Visual comparison results showcased with the ExtYaleB dataset, featuring relevant coefficient matrices for 5 subjects displayed; (c) and (d) Analysis of the influences of the parameters and initial variables for 10 subjects, illustrating their effects and validating the property across four nonconvex functions.

DownLoad: Full-Size Img PowerPoint

3   RMR for image classification

In this subsection, we evaluate the performance of various classification methods using two experimental datasets: the AR dataset and the ExtYaleB dataset with three different types of occlusions. Moreover, we utilize the coefficient vectors obtained from (15). Following the previous studies [10], [45], the training samples remain uncorrupted, while the testing samples intentionally incorporate corruption. Then, we provide a comprehensive analysis encompassing both numerical and visual results, as detailed below.

• Table 4 presents a comparative analysis of classification methods based on their experimental results, considering ACC and TIME. We note that the integration of prior information into regression methods, including nuclear norm based matrix regression (NMR), faster NMR (FNMR), generalized iterated shrinkage algorithm (GISA), and our proposed methods, results in an enhanced classification performance at the expense of increased computation time compared to other methods, except for adaptive locality preserving regression (ALPR). This is attributed to the improved evaluation performance achieved by incorporating proper measurements for the noises. In contrast, collaborative representation classifier (CRC), GISA, and unified linear regression (ULR) demonstrated lower computational costs as they omit SVD computations in their iterative processes. This suggests that avoiding SVD computations can contribute to improved computational efficiency. Especially, we employ the four nonconvex functions, addressing each sample in parallel based on Algorithm 2. The results provided underscore the superiority of these proposed classification methods under various occlusions in both AR and ExtYaleB datasets. This superiority is due to the proper measurements for the residual error and the coefficient vector, simultaneously.

Table  4.  Evaluating the quantitative effectiveness and efficiency of various classification methods on both the AR and ExtYaleB datasets, considering three various occlusions

Method	AR_sunglass		AR_scarf		ExtYaleB_baboon
	ACC (%)	TIME (s)	ACC (%)	TIME (s)	ACC (%)	TIME (s)
CRC [66]	53.167	3.6	67.500	3.5	55.483	14.9
NMR [28]	73.000	340.5	76.333	366.2	96.491	829.5
FNMR [28]	73.000	216.5	76.167	232.1	96.491	489.2
ALPR [67]	41.667	207.5	51.167	145.3	44.518	387.4
ULR* [14]	50.833	37.1	66.667	36.3	52.851	77.1
ULR** [14]	50.833	11.5	67.883	11.6	52.851	22.5
GISA2/3 [68]	50.000	6.2	65.667	6.0	63.816	20.1
GISA1/2 [68]	50.500	6.1	66.000	6.1	63.816	20.9
${\mathrm{ADMM}} _{\ell_p}$	83.000	98.1	79.667	126.6	99.561	234.7
${\mathrm{ADMM}}_{\rm{ETP}}$	82.833	55.9	78.500	54.7	99.561	131.5
${\mathrm{ADMM}}_{\rm{Laplace}}$	85.500	122.7	82.167	123.8	99.781	282.3
${\mathrm{ADMM}}_{\rm{Geman}}$	85.833	120.3	82.333	115.6	99.781	266.9

 | Show Table

DownLoad: CSV

• Figure 9 offers visual comparisons of our proposed methods using four different nonconvex functions for classification. In Figures 9(a) and (b), we illustrate the statistical distribution of the coefficient vector with normalization, using both the $\ell_{p}$-norm and the ETP function for the AR datasets. These visuals clearly reveal that the coefficient values for the same subjects have larger magnitudes, while those for different subjects tend to be lower. In contrast, Figures 9(c) and (d) display the reconstruction errors for the ExtYaleB dataset, with a focus on the Laplace and Geman functions. In these scenarios, the reconstruction errors for the same subjects as the testing samples exhibit lower values, whereas errors for different subjects demonstrate higher values. These visual results offer valuable insights into the efficiency of our proposed methods.

Figure  9.  Visual results from the AR dataset displaying (a) the reconstruction errors and (b) the statistical distribution of the coefficient vector for $\ell_{p}$-norm and ETP functions, and (c) and (d) similar results from the ExtYaleB dataset for the Laplace and Geman functions. These outcomes are associated with four different nonconvex functions.

DownLoad: Full-Size Img PowerPoint

4   Image reconstruction by clustering and classification

This subsection focuses on evaluating the visual comparisons of our proposed clustering and classification methods in terms of their reconstruction capabilities. We utilize two experimental datasets with illumination corruptions and various occlusions. Subsequently, we present the reconstructed and residual images generated under four distinct nonconvex functions. Meanwhile, the visual results will offer valuable insights and observations, as follows:

• For the clustering task, our focus is on presenting visual examples in Figures 10(a)–(d) from the top to the bottom row. These images showcase a sequence of reconstructed images alongside corresponding residual images, obtained from the ExtYaleB dataset. Upon a detailed examination of these samples, it becomes apparent that our methods excel at mitigating illumination effects in the clustered images compared to Figure 5. Importantly, this reinforces the observations made during the validation of their reconstruction ability.

Figure  10.  Partial face reconstruction and residual images generated using subspace clustering for 10 subjects. These were achieved through the utilization of four distinct nonconvex functions in our proposed methods, all applied to the ExtYaleB dataset.

DownLoad: Full-Size Img PowerPoint

• For the classification task, we present visual results using face images from the AR and ExtYaleB dataset in Figures 11(a)–(d) from left to right, demonstrating the outcomes of the proposed methods employing four distinct nonconvex functions for processing the raw images, as shown in Figure 6. Additionally, we evaluate the reconstruction capabilities of these methods by analyzing the differences and similarities in reducing occlusions to some extent. It is noteworthy that among the relaxation functions used in our proposed methods, those based on the involved nonconvex functions consistently yield superior reconstruction performance in the regression process and analysis.

Figure  11.  Partial face reconstruction and residual images obtained within the context of image classification. This was accomplished using four distinct nonconvex functions, with input data sourced from two datasets: the AR dataset, which contained images with sunglass and scarf occlusions, and the ExtYaleB dataset with baboon occlusions.

DownLoad: Full-Size Img PowerPoint

V.   Conclusion and Future Work

This work focuses on the development of efficient and effective nonconvex multiple ADMM techniques, enhanced with randomized SVD acceleration, factorization, and/or parallel computing approaches. These techniques are designed to address a class of generalized nonconvex rank regularization problems under equality constraints, effectively extending the scope of problems like RMC, LRR, and RMR. By deriving update rules for the involved subproblems, which benefit from closed-form solutions and milder assumptions. Morover, we established the boundedness of one, and in some cases, two dual variables. Additionally, we delved into the computational complexity and provable convergence properties of the variable sequence generated by our approach. Our numerical experiments, conducted on real-world data, consistently confirm the theoretical properties, demonstrating the efficiency of our methodology. Extensive experiments in image inpainting, clustering, face classification, and reconstruction clearly showcase the superiority of our methods over most related ones in terms of both performance and efficiency.

As part of the future work, it will be pivotal to tackle the challenges associated with accelerating generalized proximal operators and conduct comprehensive global convergence analyses. This holds particular significance for advancing nonconvex first-order algorithms, especially in multi-variable low-rank matrix learning scenarios [54]. Additionally, we aim to broaden the applicability of the proposed algorithms by addressing nonconvex tensor recovery problems [16], [69]–[71]. Furthermore, we also plan to explore the integration of specific auxiliary information [15], [32], [67], [72], which could contribute significantly to enhancing the evaluation performance of the proposed methods.