Efficient hybrid algorithm for nonnegative matrix factorization based on modified nonmonotone linear search Jing Wu, Wenbo Li, Lijun Su, Huiru Wang, Yike Li ABSTRACT In this paper, we present a modified nonmonotone line search algorithm that employs a variable parameter to control the degree of nonmonotonicity. This modification enhances both the probability of identifying the global minimum and the rate of convergence. Within the framework of alternating nonnegative least squares (ANLS), we propose a hybrid algorithm that employs either the modified nonmonotone projected Barzilai–Borwein method and the block coordinate descent method to address the subproblems in each iteration. To further accelerate convergence, we integrate a technique that allows for a larger step size. Under mild assumptions, we establish the global convergence of the algorithm. Numerical experiments conducted on both synthetic and real datasets demonstrate that the proposed algorithm is efficient for nonnegative matrix factorization (NMF) and outperforms other state-of-the-art methods. 1 Introduction Nonnegative Matrix Factorization (NMF) [ 1 – 5 ] is a prevalent and efficacious technique for the analysis of high-dimensional datasets. It facilitates the automatic extraction of sparse and significant features from a set of nonnegative, redundant data vectors. The standard NMF problem is formulated as follows: given an m × n data matrix V with V i j ≥ 0 and a pre-specified positive integer r < min { m , n } , NMF seeks two nonnegative matrices W ∈ ℝ + m × r and H ∈ ℝ + r × n such that V = W H + E , (1) where E ∈ R m × n denotes the approximation error. A common formulation for solving NMF (1) is min W , H f ( W , H ) ≡ 1 2 ‖ V − W H ‖ F 2 subject to W ≥ 0 , H ≥ 0 , (2) where ‖ · ‖ F is the Frobenius norm. This model is particularly suitable for the problem (1) when the approximation error follows Gaussian noise, which is a common assumption in many practical applications [ 6 ]. The NMF problem (2) , initially introduced by Paatero and Tapper [ 5 ], has attracted significant attention in recent years owing to its broad applicability in areas such as image processing [ 7 ], text mining [ 8 ], machine learning [ 9 ], and subsystem identification [ 10 ]. We now briefly review several well-established approaches for solving the NMF problem (2) . Lee and Seung developed a multiplicative update (MU) algorithm [ 3 ] and showed its equivalence to a gradient descent method. However, a limitation of the MU algorithm is that it may not converge to a stationary point due to the possibility of division by zero in the update rules [ 11 ]. To address this, Pauca et al. [ 8 ] introduced a small positive constant into the update rules, leading to improved numerical performance. The Alternating Nonnegative Least Squares (ANLS) framework [ 5 ] provides another major approach, with proven convergence to a stationary point of (11) . Within this framework, several methods have been developed, such as the projected gradient method by Lin [ 12 ] and a quasi-Newton method by Kim et al. [ 2 ]. Other contributions include the alternating projected Barzilai–Borwein methods from Han et al. [ 13 ] and a projected Newton method by Gong and Zhang [ 1 ]. Despite the variety of methods available for solving NMF problem (2) , many suffer from inefficiencies due to challenges in selecting line search step sizes or inverting Hessian matrices, especially for large-scale applications. Recently, several fast algorithms based on proximal point modifications have been proposed, such as NeNMF [ 14 ], quadratic regularization projected Barzilai–Borwein [ 15 ], and monotone projected Barzilai–Borwein (MPBB) [ 16 ]. Guan et al. [ 14 ] introduced NeNMF, which leverages Nesterov’s optimal gradient method (OGM) [ 17 ] without line search. However, Huang et al. [ 15 ] noted that OGM may require a large number of iterations to achieve a given tolerance, limiting the efficiency of NeNMF. The QRPBB method [ 15 ] utilizes the Lipschitz constant of the gradient to enhance performance and has been shown to outperform other solvers such as PG [ 12 ], APBB2 [ 13 ], and NeNMF [ 14 ]. Nevertheless, QRPBB involves a computationally expensive nonmonotone line search. To address this, the MPBB method [ 16 ] was proposed, which determines the step size without line search. However, our analysis indicates that MPBB still requires many iterations to meet a given tolerance, which can be prohibitive for large-scale problems. These limitations motivate the development of a more efficient algorithm for NMF. In this paper, we introduce a modified nonmonotone technique based on a variable parameter that controls the degree of nonmonotonicity in the line search rule. We theoretically prove that the modified objective function forms a decreasing sequence, which aids in establishing global convergence under mild conditions. By incorporating this modified nonmonotone line search, we propose an efficient hybrid algorithm that employs either the projected gradient method or the block coordinate descent method to solve subproblems within the ANLS framework. The Barzilai–Borwein step size and a larger step size technique are utilized to accelerate convergence. We establish the global convergence of the proposed method. Numerical experiments on synthetic, image, and text datasets demonstrate the efficiency of our algorithm. The remainder of this paper is organized as follows. Section 2 introduces the fast hybrid algorithm for NMF and presents its global convergence analysis. Section 3 provides experimental comparisons with other NMF algorithms. Finally, Section 4 concludes the paper. 2 A hybrid method for NMF and its global convergence In this section, we first propose a modified nonmonotone line search technique, and then develop a fast hybrid method for NMF by incorporating this technique along with a strategy for enabling larger step sizes. We also establish the global convergence of the proposed algorithm. Note that since the role of W and H is perfectly symmetric for the problem (2) , therefore, we focus only on the update of the matrix W . Suppose that the matrices V ∈ R + m × n and H k ∈ R + r × n are fixed, we only need to solve the following problems: min W ≥ 0 f ( W , H k ) = 1 2 ‖ V − W H k ‖ F 2 . (3) To simplify the notation, f ( W , H k ) will be denoted simply by f ( W ) in the following part of this paper. It is easy to know that the objective function f ( W ) is convex [ 18 – 22 ] and the gradient of it is Lipschitz continuous by Lemma 1 and 2 in [ 14 ]. These properties are very important in our proof, which will be presented in following result. Lemma 1 [ 14 ] The following two statements are valid. (i) The objective function f(W) of (3) is convex. (ii) The gradient ∇ f ( W ) = ( W H k − V ) ( H k ) T is Lipschitz continuous with constant L = ‖ H k ( H k ) T ‖ 2 . Since cost function (3) is not strongly convex objective function, and thus one can only expect that the algorithms find a stationary point instead of the global or even local minimizer. To overcome this drawback, similar to [ 23 ], in this paper, we consider a proximal point modification version of cost function (3) by linearizing f ( W ) which is the form of min W ≥ 0 φ ( W ~ , W ) : = ⟨ ∇ f ( W ~ ) , W − W ~ ⟩ + L 2 ‖ W − W ~ ‖ F 2 . (4) Obviously, according to (ii) of the Lemma 1, we can deduce that φ ( W ~ , W ) is strictly convex in W for any fixed W ~ . At each iteration, we first calculate a point Z t by solving the following strongly convex quadratic minimization problem min W ≥ 0 φ ( W t , W ) . (5) Due to the strongly convex property of the objective function (4) , the problem has a unique closed-form solution Z t = P [ W t − 1 L W ∇ W f ( W t , H k ) ] , (6) where L W = ‖ W k ( W k ) T ‖ 2 and the operator P [ X ] projects all the negative entries of X to zero. In next section, we will put forward an efficient hybrid strategy to update W t + 1 by using Z t . 2.1 Main algorithm In [ 15 ], the authors developed a nonmonotone proximal quadratic regularization projected alternating Barzilai-Borwein method for NMF, incorporating a nonmonotone technique and the Barzilai-Borwein step-size [ 24 ]. This nonmonotone term, adapted from [ 25 ], defines C t = max 0 ≤ j ≤ min { t , M − 1 } f ( W t − j ) , (7) where M is a predefined constant. Because the maximum function may discard favorable function values from any iteration, the method’s numerical performance can depend significantly on the choice of M . To overcome these limitations, Zhang and Hager proposed an alternative nonmonotone technique in [ 26 ], where a weighted average of previous function values replaces the maximum function value. This approach relaxes the Armijo-type line search condition as follows: C t = { f ( W t ) , if t = 0 , ( η t − 1 Q t − 1 C t − 1 + f ( W t ) ) / Q t , if t ≥ 1 , with Q t = { 1 , if t = 0 , η t − 1 Q t − 1 + 1 , if t ≥ 1 , where η t − 1 ∈ [ η m i n , η m a x ] for η m i n ∈ [ 0 , 1 ) and η m a x ∈ [ η m i n , 1 ] . Clearly, C t represents a convex combination of the preceding C t − 1 and f ( W t ) , incorporating the complex terms η t and Q t . This formulation implies that each C t implicitly incorporates information from all previously known function values. In practice, however, updating η t and Q t at every iteration becomes computationally burdensome. To address this limitation, the following expression for S t [ 27 ] was proposed: S t = { f ( W 0 ) , if t = 0 , f ( W t ) + η t − 1 ( S t − 1 − f ( W t ) ) , if t ≥ 1 , (8) using either a fixed η ∈ ( 0 , 1 ) or a variable η t . An analysis of S t (8) reveals that it fails to fully utilize the current well function value. Notably, the nonmonotone strategy exhibits superior performance by incorporating the maximum function—this can be attributed to the fact that the maximum function represents one of the most prominent pieces of information derived from recent successful iterations, a factor that should not be overlooked. Consequently, we define S l ( t ) = max 0 ≤ j ≤ m ( t ) { S t − j } , (9) with 0 ≤ m ( t ) ≤ min { m ( t − 1 ) + 1 , M } , m (0)=0, and S t = { f ( Z 0 ) , if t = 0 , f ( Z t ) + η t − 1 ( S t − 1 − f ( Z t ) ) , if t ≥ 1 , (10) where η t ∈ [ 0 , 1 ] . As with M in (7) , the selection of η t critically influences the degree of nonmonotonicity (see [ 27 ]). To enhance the efficiency of the nonmonotone line search, Ahookhosh et al. [ 28 ] introduced a varying η t determined by a simple formula. Subsequently, Nosratipour et al. [ 29 ] argued that η t should relate to a suitable measure of the distance to the optimal solution, defining it as η t = 1 − e − ‖ ∇ f ( Z t ) ‖ . (11) However, if the iterative sequence { Z t } becomes trapped in a narrow curved valley, ∇ f ( Z t ) may approach zero, forcing η t to zero and reducing the nonmonotone line search to the standard Armijo method, which is inefficient due to very short or zigzagging steps. To address this limitation, we propose the following η t : η t = 1 − e − | f ( Z t ) − f ( Z t − 1 ) | . (12) When the function value exhibits a rapid decrease, the absolute difference | f ( Z t ) − f ( Z t − 1 ) | increases significantly. Accordingly, this induces an elevation in η t and enhances the prominence of the nonmonotone strategy. Conversely, as f ( Z t ) converges toward the optimal solution, | f ( Z t ) − f ( Z t − 1 ) | tends to zero. This subsequent reduction in the absolute difference drives η t to approach zero, with the nonmonotone strategy gradually losing its efficacy—thereby ultimately transitioning into a monotone strategy. We then modify the Armijo-type line search by replacing S t [ 27 ] with S l ( t ) : f ( Z t + λ t D t ) ≤ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ . (13) Nonmonotone line search methods are known to be efficient for large-scale optimization problems [ 26 – 29 ]. However, a direct application to NMF does not guarantee convergence or the existence of an optimal step size, since the theoretical analysis requires f ( Z t ) ≤ S l ( t ) at each iteration (see Lemma 7 and Theorem 1). A key challenge is therefore how to apply the modified nonmonotone line search technique to (4). Numerical experiments indicate that the modified nonmonotone line search performs well provided f ( Z t ) ≥ S t − 1 and f ( W t ) ≤ S t hold. From these conditions and the definition of S l ( t ) , it follows that f ( Z t ) ≤ S l ( t ) (see Lemma 6). It is therefore reasonable to employ the modified nonmonotone line search for solving (4) when f ( Z t ) ≥ S t − 1 and f ( W t ) ≤ S t ; otherwise, we use the block coordinate descent method [ 30 ] to solve the NMF. Based on this discussion, we propose a hybrid strategy for updating W k , as detailed in Algorithm 1. The same procedure can be applied to solve for H k . Algorithm 1. An efficient hybrid method for negative matrix factorization (HMNMF) 1. Initialize α 0 = 1 , M > 0, ρ , γ and η t ∈ ( 0 , 1 ) , β ∈ ( 1 , 2 ) , α m a x > α m i n > 0 , λ m a x > 0 , λ ≤ λ m a x , L = ‖ H k ( H k ) T ‖ 2 and W 1 = Z 0 = W 0 = W k . Set t = 1. 2. If ‖ P [ W t − ∇ W F ( W t ) ] − W t ‖ = 0 , stop. 3. Compute Z t = P [ W t − 1 L ∇ W F ( W t ) ] . (14) 4. Compute S t by (10) , and compute S l ( t ) by (9) . 5. If s g n ( f ( W t ) − S t ) * s g n ( f ( Z t ) − S t − 1 ) < 0 , set W t + 1 = Z t and go to Step 6. Otherwise, compute D t = P [ Z t − α t ∇ f ( Z t ) ] − Z t which is the direction with α t be the BB stepsize, and let m t 1 and m t 2 are the smallest nonnegative integer m respectively satisfying S t ≤ S l ( t − 1 ) + ( 1 − η t − 1 ) γ β λ ~ t − 1 ⟨ ∇ f ( Z t − 1 ) , D t − 1 ⟩ , (15) with λ ~ t − 1 = λ ρ m t 1 and f ( Z t + β λ t D t ) ≤ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ , (16) where λ t = λ ~ t − 1 ρ m t 2 . Calculate W t + 1 = Z t + β λ t D t . 6. Calculate S t = W t + 1 − Z t and Y t = ∇ W F ( W t + 1 ) − ∇ W F ( Z t ) . If ⟨ S t , S t ⟩ / ⟨ S t , Y t ⟩ ≤ 0 , set α t + 1 = α m a x ; otherwise, set α t + 1 = min { α m a x , max { α m i n , ⟨ S t , S t ⟩ / ⟨ S t , Y t ⟩ } } . 7. Set t = t + 1 and go to step 2. For ease of reference, we define two index sets: I = { t : f ( W t ) ≤ S t and f ( Z t ) ≥ S t − 1 } , and J = P \ I , Here, P denotes the index set for the total number of sub-iterations used to solve (4) . Remark 1 Equation (9) indicates that the sequence { S t } produced by Algorithm 1 can occasionally increase. This behavior contrasts with the strictly nonincreasing sequences established for the methods in [ 27 , 28 ]. The present nonmonotone condition on { S t } is also simpler to satisfy than its counterpart in those references. Moreover, the incorporation of a nonmonotone { S t } into the development of a new algorithm for solving (4) necessitates a different approach to establishing convergence. In [ 31 ], Nocedal observed that step sizes in nonmonotone line search methods can deviate unpredictably from unity, varying above or below one depending on problem scaling. Following this insight, and analogous to the strategy of employing larger step sizes for updating Lagrange multipliers in [ 32 ], we introduce a relaxation factor β > 0 to update W t + 1 as W t + 1 = Z t + β λ t D t . (17) The parameter β is empirically selected from the interval (1, 2). The following lemma 2 is central to our global convergence analysis. Lemma 2 For all α ∈ ( 0 , α m a x ] , W ≥ 0 , (i) ⟨ ∇ f ( Z ) , D t ⟩ ≤ − 1 α ‖ D t ‖ 2 ≤ − 1 α m a x ‖ D t ‖ 2 , (ii) Z is a stationary point of (3) if and only if D t = 0 , (iii) ‖ D t ‖ ≤ α t ‖ ∇ f ( Z t ) ‖ . Proof. The proof of (i) and (ii) are similar to the proof of Lemma 2.1 in [ 33 ] and therefore it is omitted here. (iii) By use of the Cauchy equality, from (i), we obtain (iii). □ The following lemma is drown from Lemma 3 [ 15 ]. Lemma 3 [ 15 ] Assume that the sequences { Z t } and { W t } are generated by Algorithm 1, then we have f ( Z t ) ≤ f ( W t ) − L 2 ‖ Z t − W t ‖ 2 . (18) To demonstrate that Algorithm 1 is well-defined, we establish the following result. Lemma 4 For a given iterate Z t and a search direction D t at Z t , there exists a step size λ t such that for all t ∈ J , the inequality f ( Z t + β t λ t D t ) ≤ f ( Z t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ (19) holds, where λ t = λ ρ m . Proof. Assume no step size λ t satisfies inequality (19) . Then for all sufficiently large positive integers m , we have f ( Z t + β ρ m D t ) − f ( Z t ) > γ β ρ m ⟨ ∇ f ( Z t ) , D t ⟩ . By the mean value theorem, there exists θ t ∈ ( 0 , 1 ) such that β ρ m ⟨ ∇ f ( Z t + θ t β ρ m D t ) , D t ⟩ > γ β ρ m ⟨ ∇ f ( Z t ) , D t ⟩ , which simplifies to ⟨ ( ∇ f ( Z t + θ t β ρ m D t ) − ∇ f ( Z t ) ) , D t ⟩ > ( γ − 1 ) ⟨ ∇ f ( Z t ) , D t ⟩ . Taking the limit as m → ∞ yields ( γ − 1 ) ⟨ ∇ f ( Z t ) , D t ⟩ ≤ 0 . Given γ ∈ ( 0 , 1 ) , this implies ⟨ ∇ f ( Z t ) , D t ⟩ ≥ 0 , contradicting the condition ⟨ ∇ f ( Z t ) , D t ⟩ ≤ 0 . □ The following lemma implies that S l ( i ) is monotonically decreasing for all i ∈ { 1 , 2 , ⋯ , t } when i ∈ I . Lemma 5 Suppose the sequence { Z i } for i ∈ { 1 , 2 , ⋯ , t } is generated by Algorithm 1; if i ∈ I holds for all i ∈ { 1 , 2 , ⋯ , t } , then S l ( i ) ≤ S l ( i − 1 ) . Proof. For i = 1 ∈ I , Lemma 3 implies that f ( Z 1 ) ≤ f ( W 1 ) = f ( Z 0 ) . (20) By the definition of S t , we obtain S 1 = f ( Z 1 ) + η 0 ( S 0 − f ( Z 1 ) ) = ( 1 − η 0 ) f ( Z 1 ) + η 0 S 0 ≤ ( 1 − η 0 ) f ( Z 0 ) + η 0 S 0 = S 0 . (21) The inequality follows from (20) . From (21) and the definition of S l ( t ) , it follows that S l ( 1 ) ≤ S l ( 0 ) , which establishes the result. Next, we assume that for all i with 1 ≤ i < t , the inequality S i ≤ S i − 1 holds; then, by the definition of S l ( t ) , it follows that S l ( i ) ≤ S l ( i − 1 ) . If S i ≤ S i − 1 , the definition of S i yields f ( Z i ) + η i − 1 ( S i − 1 − f ( Z i ) ) ≤ S i − 1 , which implies f ( Z i ) ≤ S i − 1 . (22) From the definition of S i together with (22) , we obtain f ( Z i ) ≤ S i . (23) For i = t ∈ I , the definition of S t and Lemma 3 give S t = f ( Z t ) + η t − 1 ( S t − 1 − f ( Z t ) ) ≤ ( 1 − η t − 1 ) f ( Z t − 1 ) + η t − 1 S t − 1 ≤ ( 1 − η t − 1 ) S t − 1 + η t − 1 S t − 1 = S t − 1 . Here, the final equality relies on (23) . By the definition of S l ( t ) , we conclude that S l ( t ) ≤ S l ( t − 1 ) . □ Next, we demonstrate a key property of the modified line search. For a given W 0 > 0, the level set is defined as ℒ ( W 0 ) = { W ∣ f ( W ) ≤ f ( W 0 ) , W ≥ 0 } . Lemma 6 Suppose the sequences { Z t } and { W t } are generated by Algorithm 1; then { Z t } , { W t } ⊂ ℒ ( W 0 ) , and { S l ( t ) } is a decreasing sequence. Proof. We first show that { S l ( t ) } is decreasing by considering two cases. Case I: For t + 1 ∈ J with t ∈ { 0 , 1 , 2 , … } , the inequality m ( t + 1 ) ≤ m ( t ) + 1 together with the definition of { S l ( t ) } and equation (34) implies S l ( t + 1 ) = max 0 ≤ j ≤ m ( t + 1 ) { S t + 1 − j } ≤ max 0 ≤ j ≤ m ( t ) + 1 { S t + 1 − j } = max { S l ( t ) , S t + 1 } ≤ S l ( t ) . (24) Case II: For t + 1 ∈ I , the definition of S t + 1 gives S t + 1 = f ( Z t + 1 ) + η t ( S t − f ( Z t + 1 ) ) = ( 1 − η t ) f ( Z t + 1 ) + η t S t ≤ ( 1 − η t ) f ( Z t ) + η t S t . (25) If t ∈ J , Algorithm 1 ensures f ( Z t ) < S t − 1 , and since S t − 1 ≤ S l ( t ) by definition, we have f ( Z t ) ≤ S l ( t ) . (26) Substituting inequality (26) into (25) yields S t + 1 ≤ ( 1 − η t ) S l ( t ) + η t S t ≤ S l ( t ) , (27) where the last step uses the definition of S l ( t ) . Hence, S l ( t + 1 ) ≤ S l ( t ) . (28) If i ∈ I for i ∈ { t , t − 1 , … , t − j − 1 } and t − j ∈ J , then from Algorithm 1, f ( Z t − j ) < S t − j − 1 . (29) Combining this with (22) and (23) gives S t − j + 1 ≤ S t − j , and as in the proof of Lemma 5, we obtain S t ≤ S t − 1 ≤ … ≤ S t − j − 1 , so S l ( t + 1 ) ≤ S l ( t ) by definition. Otherwise, if i ∈ I for all i ∈ { t , t − 1 , … , 0 } , Lemma 5 again implies S l ( t + 1 ) ≤ S l ( t ) . The sequence { S l ( t ) } is therefore monotonically decreasing. We next demonstrate that { Z t } and { W t } lie within ℒ ( W 0 ) . Since S l ( 0 ) = f ( Z 0 ) ≤ f ( W 0 ) holds by definition, we proceed by induction to show that f ( W t ) ∈ ℒ ( W 0 ) for all t ∈ 𝐍 . Assuming f ( W i ) ∈ ℒ ( W 0 ) for i = 1 , 2 , ⋯ , t , we verify that W t + 1 ∈ ℒ ( W 0 ) . This result is established by considering the following two cases: Case I: For t + 1 ∈ J , where t ∈ { 0 , 1 , 2 , ⋯ } , we apply (35) and Lemma 2 to obtain f ( W t + 1 ) ≤ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ ≤ S l ( t ) . (30) Combining inequality (30) with Lemma 6 yields f ( W t + 1 ) ≤ S l ( t ) ≤ f ( Z 0 ) ≤ f ( W 0 ) . (31) Therefore, the point W t + 1 lies within ℒ ( W 0 ) . Case II: When t + 1 ∈ I , we use (26) , (29) , (22) , (23) and Lemma 5 to derive f ( Z t ) ≤ S l ( t ) . (32) Algorithm 1 gives f ( W t + 1 ) = f ( Z t ) . This equality, combined with (32) and Lemma 6, leads to f ( W t + 1 ) ≤ S l ( t ) ≤ f ( Z 0 ) ≤ f ( W 0 ) . (33) Consequently, the point W t + 1 also belongs to ℒ ( W 0 ) . Thus, the entire sequence { W t } remains within ℒ ( W 0 ) . Lemma 3 further confirms that { Z t } ⊂ ℒ ( W 0 ) . □ The following corollary establishes the convergence of the sequence { S l ( t ) } . Corollary 1 Suppose that the level set ℒ ( W 0 ) is bounded; then the sequence { S l ( t ) } converges. Proof . From (31) , (33) , and Lemma 6, it follows that there exists τ such that for all n ∈ 𝐍 , τ ≤ f ( W t + n ) ≤ S l ( t + n ) ≤ S l ( t − 1 + n ) ≤ ⋯ ≤ S l ( t + 1 ) ≤ S l ( t ) , which implies that the sequence { S l ( t ) } is bounded below. Therefore, { S l ( t ) } converges. □ We now establish the well-definiteness of the line search. Theorem 1 Suppose the sequences { Z t } and { W t } are generated by Algorithm 1. Then Algorithm 1 is well-defined. Proof . The proof is straightforward for all t ∈ I , so it suffices to show that S t + 1 ≤ S l ( t ) + ( 1 − η t ) γ β λ ~ t ⟨ ∇ f ( Z t ) , D t ⟩ (34) and f ( Z t + β λ t D t ) ≤ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ (35) are well-defined for all t ∈ J . We proceed by induction. The base case t = 0 is easily verified. Now assume that for some λ i and all i with 0 < i ≤ t , inequali t ies (34) and (35) hold. From Algorithm 1, we have f ( Z t ) < S t − 1 . Given that S t − 1 ≤ S l ( t ) , it follows that f ( Z t ) ≤ S l ( t ) . For i = t + 1, Lemma 4 guarantees the existence of a step size λ ~ t > 0 such that (19) holds. According to Lemma 3, we derive ( 1 − η t ) f ( Z t + 1 ) ≤ ( 1 − η t ) f ( Z t ) + ( 1 − η t ) γ β λ ~ t ⟨ ∇ f ( Z t ) , D t ⟩ ≤ ( 1 − η t ) S l ( t ) + ( 1 − η t ) γ β λ ~ t ⟨ ∇ f ( Z t ) , D t ⟩ ≤ η t ( S l ( t ) − S t ) + ( 1 − η t ) S l ( t ) + ( 1 − η t ) γ β λ ~ t ⟨ ∇ f ( Z t ) , D t ⟩ . The final inequality is equivalent to (34) , confirming that (34) is well defined. From (19) , we observe that λ t satisfies f ( Z t + β λ t D t ) ≤ f ( Z t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ ≤ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ . This last inequality ensures that (35) is well defined. Consequently, Algorithm 1 is well-defined. □ We now introduce a key property of the sequence S l ( t M ) , which is essential for establishing global convergence. Theorem 2 Assume that the sequences { Z t } and { W t } are generated by Algorithm 1; then, S l ( ( t + 1 ) M ) ≤ S l ( t M ) + δ l ( ( t + 1 ) M ) − 1 λ l ( ( t + 1 ) M ) − 1 ⟨ ∇ f ( Z l ( ( t + 1 ) M ) − 1 ) , D l ( ( t + 1 ) M ) − 1 ⟩ , (36) where δ l ( ( t + 1 ) M ) − 1 = γ β ( 1 − η l ( ( t + 1 ) M ) − 1 ) and t ∈ { 1 , 2 , ⋯ } . Furthermore, ∑ t = 1 ∞ λ l ( ( t + 1 ) M ) − 1 | ⟨ ∇ f ( Z l ( ( t + 1 ) M ) − 1 ) , D l ( ( t + 1 ) M ) − 1 ⟩ | < ∞ . (37) proof From the definition of S l ( t ) and Lemma 6, we obtain S t M + 1 ≤ max { S ( t − 1 ) M + 1 , ⋯ , S t M } + δ t M λ t M ⟨ ∇ f ( Z t M ) , D t M ⟩ = S l ( t M ) + δ t M λ t M ⟨ ∇ f ( Z t M ) , D t M ⟩ S t M + 2 ≤ max { S l ( t M ) , S t M + 1 } + δ t M + 1 λ t M + 1 ⟨ ∇ f ( Z t M + 1 ) , D t M + 1 ⟩ = S l ( t M ) + δ t M + 1 λ t M + 1 ⟨ ∇ f ( Z t M + 1 ) , D t M + 1 ⟩ ⋮ By induction, S t M + i ≤ S l ( t M ) + δ t M + i − 1 λ t M + i − 1 ⟨ ∇ f ( Z t M + i − 1 ) , D t M + i − 1 ⟩ for i ∈ { 1 , 2 , ⋯ , M } . Because l ( ( t + 1 ) M ) ∈ { t M + 1 , ⋯ , ( t + 1 ) M } , the desired result (36) follows. We now prove (37) . Since f is bounded below and S l ( t M ) is a convex combination of certain values of f ( Z t M ) , the sequence S l ( t M ) is also bounded below. Combining the inequalities in (36) with Corollary 1 yields ∑ t = 1 ∞ δ l ( t M ) − 1 | ⟨ ∇ f ( Z l ( t M ) − 1 ) , D l ( t M ) − 1 ⟩ | ≤ S l ( 0 ) − lim t → ∞ S l ( t M ) < ∞ . This completes the proof. 2.2 Convergence analysis This section analyzes the convergence properties of the proposed algorithm, establishing its global convergence. To prove the main result, we first derive a lower bound for the step length λ t . Lemma 7 Assume λ t is a step size generated by Algorithm 1; if Z t is not a stationary point of (3), then for all t ∈ J , there exists a constant λ ~ such that λ t ≥ λ ~ . λ t ≥ min { 1 , 2 ρ ( 1 − γ ) L α m a x } . (38) Proof. For the obtained step size λ t , if λ t does not satisfy (35) , that is, f ( Z t + β t λ t D t ) ≥ S l ( t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ ≥ f ( Z t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ . Thus, f ( Z t + β t λ t D t ) ≥ f ( Z t ) + γ β λ t ⟨ ∇ f ( Z t ) , D t ⟩ . Similar to Lemma 4 in [ 15 ], we obtain λ t ≥ min { 1 , 2 ρ ( 1 − γ β ) L α m a x } : = λ ~ . Inequality (38) is therefore satisfied. To establish global convergence, we now prove the following result. Lemma 8 Assume that the sequences { Z t } and { W t } are generated by Algorithm 1. Then ‖ ∇ f ( W t + 1 ) ‖ ≤ ( 1 + α m a x λ m a x β L ) ‖ ∇ f ( Z t ) ‖ . (39) Moreover, lim t → ∞ ‖ D l ( t M ) − 1 ‖ = 0 . (40) Proof. Algorithm 1 ensures that the step size satisfies λ t ≤ λ m a x for all t ∈ J . Using Lemma 2(iii), we obtain ‖ W t + 1 − Z t ‖ = β λ t ‖ D t ‖ ≤ α m a x λ m a x β ‖ ∇ f ( Z t ) ‖ . (41) The Lipschitz continuity of ∇ f implies ‖ ∇ f ( W t + 1 ) − ∇ f ( Z t ) ‖ ≤ α m a x λ m a x β L ‖ ∇ f ( Z t ) ‖ (42) Therefore, inequality (39) is established. We now demonstrate the validity of equality (40) . Using Theorem 2, it follows that ∑ t = 2 ∞ λ ~ 1 α m a x ‖ D l ( t M ) − 1 ‖ 2 ≤ ∑ t = 2 ∞ λ ~ | ⟨ ∇ f ( Z l ( t M ) − 1 ) , D l ( t M ) − 1 ⟩ | ≤ ∑ t = 2 ∞ λ l ( t M ) − 1 | ⟨ ∇ f ( Z l ( t M ) − 1 ) , D l ( t M ) − 1 ⟩ | < ∞ . Thus lim t → ∞ ‖ D l ( t M ) − 1 ‖ = 0 . We next establish the following global convergence result for our HMNMF method. □ Theorem 3 Suppose that the level set ℒ ( W 0 ) is bounded; then any accumulation point of the sequence { Z t } generated by Algorithm 1 is a stationary point of (3). Proof. We consider two cases. Case I: For t ∈ I , Lemma 8 implies that lim t → ∞ ‖ D t ‖ = 0 , (43) so any accumulation point of { Z t } is a stationary point of (3). Case II: For t ∈ J , the boundedness of ℒ ( W 0 ) together with Lemma 8 and Lemma 2(ii) shows that { Z l ( t M ) − 1 } has an accumulation point Z * that is a stationary point of (3). We now prove Theorem 3 by contradiction. Assume Z * is not a stationary point of (3). Then Lemma 2(ii) gives ‖ D α ( Z * ) ‖ > 0 for all α ∈ ( 0 , α m a x ] . By continuity and compactness, there exists η > 0 such that ‖ D α ( Z * ) ‖ > η for α ∈ [ α m i n , α m a x ] . Hence, for sufficiently large t , ‖ D α ( Z * ) ‖ > η / 2 . Using Lemmas 2, 3, 6 and 7, we derive f ( Z l ( t M ) ) ≤ f ( W l ( t M ) ) = f ( Z l ( t M ) − 1 + β λ l ( t M ) − 1 D l ( t M ) − 1 ) ≤ S l ( t M ) − 1 + γ β λ l ( t M ) − 1 ⟨ ∇ f ( Z l ( t M ) − 1 ) , D l ( t M ) − 1 ⟩ ≤ S l ( t M ) − 1 − γ β λ ~ α m a x ‖ D l ( t M ) − 1 ‖ 2 ≤ S l ( 0 ) − γ β λ ~ η 2 4 α m a x which yields f ( Z l ( t M ) ) → − ∞ as t → ∞ . This contradicts the property of the norm, so Z * must be a stationary point of (3). By Theorem 3, Lemma 2, and Lemma 3, the following key convergence result is established. Theorem 4 If the level set ℒ ( W 0 ) is bounded, then every accumulation point of the sequence { W t } produced by Algorithm 1 constitutes a stationary point of (3). 3 Numerical experiments This section presents numerical experiments evaluating our algorithm’s performance against six methods: NeNMF [ 14 ], the projected BB method (APBB2 [ 13 ]) (The code is available at http://homepages.umflint.edu/~lxhan/software.html ), QRPBB [ 15 ], MPBB [ 16 ], hierarchical alternating least squares (HALS) [ 34 ], and the block coordinate descent (BCD) method [ 30 ]. We compared these methods using both synthetic datasets and real-world problems from the Yale image database ( http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html ), the CBCL image database http://cbcl.mit.edu/software-datasets/FaceData2.html , and the Reuters-21578 and TDT2 text corpora (Both Reuters-21578 corpus and TDT-2 corpus in MATLAB format are available at http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html ). All code was implemented in MATLAB. The experiments ran on a Lenovo laptop with an Intel Core(TM) i7 CPU at 4.9 GHz and 16 GB of memory, using Windows 10 and MATLAB R2021a. 3.1 Stopping criterion By the KKT conditions for constrained optimization, ( W , H ) is stationary point of NMF (2) if and only if it satisfies ∇ W P f ( W , H ) = 0 and ∇ H P f ( W , H ) = 0 , where [ ∇ W P f ( W , H ) ] i j = [ ∇ W f ( W , H ) ] i j , if W i j > 0 , min { 0 , [ ∇ W f ( W , H ) ] i j } , if W i j = 0 , and ∇ H P f ( W ( k ) , H ( k ) ) is defined in the same way. Thus, we use the following stopping criterion as Lin [ 12 ] in the numerical experimentation: ‖ [ ∇ W P f ( W ( k ) , H ( k ) ) , ∇ H P f ( W ( k ) , H ( k ) ) T ] ‖ ≤ ϵ ‖ [ ∇ W P f ( W ( 1 ) , H ( 1 ) ) , ∇ H P f ( W ( 1 ) , H ( 1 ) ) T ] ‖ , (44) where ϵ > 0 is a tolerance. 3.2 Synthetic data We first evaluate the performance of HMNMF and the other algorithms on synthetic datasets. The matrix V in this test is exactly low-rank and is constructed as V = LR , where L and R are generated using the MATLAB commands max (0, randn ( m , r )) and max (0, randn ( r , n )), respectively. The parameters of our method are set as follows throughout all experiments: α max = 10 20 , α min = 10 − 20 , ρ = 0.25 , γ = 10 − 4 , and λ = 1 . These settings are consistent with those used in APBB2, QRPBB, and MPBB. The tolerance for all algorithms is set to tol = 10 −8 . For HMNMF, we choose β = 1.88 and update η t according to equation (12) . The maximum number of iterations (maxit) is set to 50,000 for all algorithms. All other parameters for APBB2, NeNMF, QRPBB, and MPBB are set to their default values. For each test dataset with independent Gaussian noise at a signal-to-noise ratio of 60 dB, we use 10 different randomly generated initial points. The average results are summarized in Table 1 . Here, “iter” denotes the number of iterations required to satisfy the termination criterion (44), and “niter” represents the total number of sub-iterations for solving subproblems (3) and (4). Performance is measured using the relative error relerr = ‖ V − W k H k ‖ F / ‖ V ‖ F , the final projected gradient norm ‖ [ ∇ P H F ( W k , H k ) , ∇ P W F ( W k , H k ) ] ‖ F , and the CPU time (in seconds). As shown in Table 1 , HMNMF achieves the shortest execution time and the smallest number of sub-iterations among all algorithms, particularly for large-scale datasets. These results indicate that HMNMF significantly outperforms the other four solvers across all test cases. This improvement can be attributed to two factors: first, the modified objective function in the nonmonotone line search S l ( t ) may enhance efficiency; second, the introduction of the relaxation factor β in the update rules allows larger step sizes, thereby reducing computational time. 10.1371/journal.pone.0344857.t001 Table 1 Experimental results on synthetic datasets. (m n r) Alg Iter Niter Pgn Time Residual (600 200 30) NeNMF 153.3 5456.0 7.58E-4 1.52 7.5550E-4 APBB2 161.8 3441.8 7.94E-4 2.13 7.5460E-4 QRPBB 141.0 1988.4 5.60E-4 1.21 7.5509E-4 MPBB 83.1 2547.9 6.86E-4 0.87 7.5306E-4 HMNMF 52.2 530.4 6.84E-4 0.39 7.5449E-4 (500 700 40) NeNMF 160.3 5807.8 2.46E-3 3.05 7.7824E-4 APBB2 185.0 4545.3 2.18E-3 5.58 7.7758E-4 QRPBB 147.9 2190.9 1.70E-3 2.69 7.7762E-4 MPBB 97.9 3050.4 2.32E-3 2.09 7.7752E-4 HMNMF 72.1 712.1 2.01E-3 1.03 7.7781E-4 (1000 200 50) NeNMF 201.1 7784.6 2.58E-3 6.16 7.1992E-4 APBB2 249.1 6443.7 2.57E-3 11.44 7.2020E-4 QRPBB 240.4 3579.7 2.29E-3 5.00 7.1959E-4 MPBB 133.7 4827.2 2.43E-3 4.04 7.1962E-4 HMNMF 96.3 1010.6 2.28E-3 1.59 7.1969E-4 (1000 600 60) NeNMF 226.2 8357.3 6.44E-3 8.82 7.7041E-4 APBB2 241.5 6121.9 6.21E-3 15.73 7.7086E-4 QRPBB 207.7 3375.3 5.63E-3 8.00 7.7116E-4 MPBB 124.8 4386.5 6.39E-3 6.12 7.7124E-4 HMNMF 88.8 974.7 5.16E-3 2.68 7.7098E-4 (500 2000 70) NeNMF 240.8 10004.9 1.29E-2 30.25 7.6550E-4 APBB2 251.1 6929.6 1.32E-2 37.32 7.6553E-4 QRPBB 211.2 3492.2 1.10E-2 17.84 7.6549E-4 MPBB 138.6 4611.8 1.25E-2 15.09 7.6589E-4 HMNMF 97.6 1150.2 1.17E-2 6.85 7.6546E-4 (3000 900 80) NeNMF 238.5 8946.3 3.13E-2 54.35 7.8611E-4 APBB2 267.4 6860.5 3.24E-2 95.20 7.8594E-4 QRPBB 262.6 4127.7 2.82E-2 48.05 7.8631E-4 MPBB 165.0 5905.1 3.06E-2 40.17 7.8566E-4 HMNMF 87.4 1059.4 2.55E-2 13.50 7.8602E-4 (5000 1000 90) NeNMF 267.6 9911.9 6.03E-2 100.90 7.8828E-4 APBB2 271.8 9894.6 5.55E-2 221.37 7.8828E-4 QRPBB 223.2 4263.6 5.76E-2 91.66 7.8828E-4 MPBB 162.5 5862.3 5.97E-2 80.61 7.8844E-4 HMNMF 117.9 1455.1 5.79E-2 34.77 7.8828E-4 (8000 1000 100) NeNMF 287.3 10579.7 1.47E-1 209.28 7.8661E-4 APBB2 291.3 10939.6 1.14E-1 189.83 7.8661E-4 QRPBB 223.2 4309.1 1.08E-1 154.14 7.8661E-4 MPBB 165.5 5628.6 1.15E-1 139.37 7.8718E-4 HMNMF 133.8 1715.6 1.11E-1 69.03 7.8661E-4 With the close association between HMNMF, QRPBB, and MPBB, and considering HALS and BCD as some of the most efficient NMF methods, we further compare the performance of HMNMF, QRPBB, MPBB, HALS, and BCD. Figs 1 – 3 present comparisons of these five methods on eight randomly generated datasets with independent Gaussian noise at a signal-to-noise ratio of 30 dB. The algorithms are terminated when the stopping criterion in (44) is satisfied with ϵ = 10 − 8 or when the iteration count exceeds 30. The results clearly demonstrate that HMNMF requires the fewest iterations and the least CPU time to reach the specified tolerance in most cases, especially for high-dimensional datasets. Moreover, for high-dimensional data, the PBB-based methods outperform HALS and BCD, which can be explained by the fact that PBB-based methods implicitly utilize second-order information of the cost function, whereas HALS and BCD rely on first-order approximations to search for stationary points. 10.1371/journal.pone.0344857.g001 Fig 1 The influence of different choices of parameter η t on the computational efficiency of HMNMF on the synthetic datasets. 10.1371/journal.pone.0344857.g002 Fig 2 The influence of different relaxation factors S on the computational efficiency of HMNMF on the synthetic datasets. 10.1371/journal.pone.0344857.g003 Fig 3 The influence of different relaxation factors S on the computational efficiency of HMNMF on the synthetic datasets. 3.3 Image data The Yale face database, created by the Yale Center for Computational Vision and Control, contains 165 grayscale images of 15 individuals, with 11 images per person. The images exhibit variations in lighting conditions (left-light, center-light, right-light), facial expressions (normal, happy, sad, surprised, wink), and the presence or absence of glasses. The data matrix V , with rows representing images, has dimensions 165 × 4096. The CBCL image database comprises 2,429 facial images, each with 19×19 pixels, resulting in a matrix of size 361×2,429. For each database, we perform 10 trials with different randomly generated initial points, using ϵ = 10 − 8 in (44) and a maximum of 50,000 iterations for all algorithms. The average results are presented in Table 2 . It can be observed that for both databases, HMNMF converges in fewer iterations and less CPU time, while achieving residual values comparable to those of other solvers. 10.1371/journal.pone.0344857.t002 Table 2 Experimental results on Yale and CBCL datasets. (m n r) Alg Iter Niter Pgn Time Residual (165 4,096 20) NeNMF 3122.2 127172.0 1.12E-1 122.34 1.849E-1 APBB2 2896.8 93407.0 1.04E-1 209.27 1.848E-1 QRPBB 2632.5 51428.7 9.38E-2 88.92 1.848E-1 MPBB 1725.0 66687.0 1.02E-1 65.18 1.846E-1 HMNMF 812.7 9104.7 1.09E-1 16.78 1.848E-1 (361 2,429 49) NeNMF 1767.3 99033.1 2.09E-2 153.26 1.925E-1 APBB2 395.7 18474.5 1.87E-2 29.18 1.926E-1 QRPBB 540.8 12244.8 1.68E-2 20.66 1.929E-1 MPBB 593.5 20806.6 1.78E-2 32.97 1.926E-1 HMNMF 284.7 5707.3 1.60E-2 14.59 1.924E-1 3.4 Text data The Reuters-21578 corpus includes 21,578 documents distributed across 135 categories. Documents with multiple category labels were discarded, leaving 8,293 documents in 65 categories. After preprocessing, the corpus contains 18,933 distinct terms, represented by a matrix of size 18 , 933 × 8 , 293 . The TDT2 corpus consists of news articles from sources such as ABC, CNN, VOA, NYT, PRI, and APW from 1998. It contains 11,201 on-topic documents classified into 96 semantic categories. After removing documents appearing in two or more categories and retaining only the largest 30 categories, we obtain 9,394 documents, represented by a matrix of size 36 , 771 × 9 , 394 . As in the previous subsection, we set ϵ = 10 − 8 , and report average results over 10 random initializations in Table 3 . The results show that the CPU time required by HMNMF is significantly less than that of NeNMF, APBB2, QRPBB, and MPBB. Meanwhile, the projected gradient norms obtained by APBB2, QRPBB, MPBB, and HMNMF are similar and smaller than those of NeNMF, which confirms the effectiveness of our proposed HMNMF method. 10.1371/journal.pone.0344857.t003 Table 3 Experimental results on Reuters-21578 and TDT2 datasets. (m n r) Alg Iter Niter Pgn Time Residual (18,933 8,293 65) NeNMF 397.5 18660.0 1.34E + 0 476.06 6.877E-1 APBB2 161.3 3691.9 1.01E + 0 265.84 6.885E-1 QRPBB 123.6 2015.3 1.06E + 0 116.98 6.889E-1 MPBB 152.0 4926.1 1.13E + 0 154.60 6.879E-1 HMNMF 46.0 478.7 1.03E + 0 28.83 6.878E-1 (36,771 9,394 100) NeNMF 206.7 7936.1 4.88E + 0 560.75 7.396E-1 APBB2 108.1 1967.6 3.78E + 0 380.35 7.398E-1 QRPBB 120.4 1328.5 3.01E + 0 233.38 7.396E-1 MPBB 54.3 1376.7 3.67E + 0 115.43 7.399E-1 HMNMF 40.1 303.8 4.00E + 0 56.35 7.398E-1 3.5 Influence of parameters η t and β In this section, we first intend to investigate what is the impact for our modified nonmonotone line search rules. In particular, how does the definition of η t in (10) improve the numerical efficiency of algorithms? To do so, we shall compare our η t with the other two η t , proposed in [ 28 , 29 ]. For simplicity of statement, we introduce the following notations. HMNMF-1:Algorithm 1 with the η t defined in [ 28 ]; HMNMF-2:Algorithm 1 with the η t defined in [ 29 ]; HMNMF:Algorithm 1 with the η t defined by (12). Fig 4 shows the relative residual value versus the running time on synthetic datas which are the same as those in Section 3.1 . The maximum number of iterations (maxit) is set to be 20 for all algorithms, and all of the other parameters for experimental settings here are the same as those in Section 3.1 . From Fig 3 , it is clear that our η t is superior to the other two η t in [ 28 , 29 ]. 10.1371/journal.pone.0344857.g004 Fig 4 Residual value versus time of HMNMF on synthetic datasets. Next we report that how does the adjustability of the relaxation factor s in the update rule of W t + 1 can improve the numerical efficiency of algorithms? In fact, we run the HMNMF with the following different s : s = 0.08, 0.48, 0.88, 1.0, 1.48, 1.88, 1.98 on synthetic datas which are the same as those in Section 3.1 . Fig 5 shows the relative residual value versus the running time. The maximum number of iterations (maxit) is set to be 30 for all algorithms, and all of the other parameters for experimental settings here are the same as those in Section 3.1 . From Fig 5 , we can see that the relaxation factor s fails to accelerate the convergence when s < 1 and increasing constant s significantly accelerates the convergence when 1 < s < 2. As for NMPBB, it is seem that s = 1.88 is much better value than the other values in term of convergence rate, thus we use s = 1.88 for our HMNMF in all experiments. 10.1371/journal.pone.0344857.g005 Fig 5 Residual value versus time of HMNMF on relaxation factor s on synthetic datasets. 4 Conclusion This paper introduces a fast prox-linear variant of a hybrid algorithm for solving NMF within the ANLS framework; the algorithm employs either a modified nonmonotone projected Barzilai-Borwein gradient method or a block coordinate descent method to address the subproblems in each iteration. A modified line search rule incorporating a nonmonotone technique [ 25 , 27 ] is also integrated into the algorithm to enhance its efficiency. Under mild assumptions, the global convergence of the algorithm is established. Numerical experiments demonstrate the effectiveness of the proposed algorithm for NMF.