# Convergence Analysis of Block Majorize-Minimize Subspace Approach

Emilie Chouzenoux, Jean-Baptiste Fest

► To cite this version:

Emilie Chouzenoux, Jean-Baptiste Fest. Convergence Analysis of Block Majorize-Minimize Subspace Approach. Optimization Letters, 2024, 18, pp.1111-1130. 10.1007/s11590-023-02055-z. hal-04202728

HAL Id: hal-04202728

https://inria.hal.science/hal-04202728v1

Submitted on 11 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Convergence Analysis of Block Majorize-Minimize Subspace Approach

Emilie Chouzenoux and Jean-Baptiste Fest

the date of receipt and acceptance should be inserted later

**Abstract** We consider the minimization of a differentiable Lipschitz gradient but non necessarily convex, function $F$ defined on $\mathbb{R}^N$. We propose an accelerated gradient descent approach which combines three strategies, namely (i) a variable metric derived from the majorization-minimization principle ; (ii) a subspace strategy incorporating information from the past iterates ; (iii) a block alternating update. Under the assumption that $F$ satisfies the Kurdyka-Łojasiewicz property, we give conditions under which the sequence generated by the resulting block majorize-minimize subspace algorithm converges to a critical point of the objective function, and we exhibit convergence rates for its iterates.

**Keywords** Block alternating method, majorization-minimization, memory gradient, quasi-Newton, non-convex optimization, Kurdyka-Łojasiewicz.

## 1 Introduction

Our work focuses on the resolution of

$$ \underset{\mathbf{x} \in \mathbb{R}^N}{\text{minimize}} F(\mathbf{x}), \qquad (1) $$

with $F: \mathbb{R}^N \to \mathbb{R}$ is a differentiable Lipschitz gradient function which is not assumed to be convex. Instead, we address the case when $F$ satisfies the Kurdyka-Łojasiewicz (KL) inequality [1,2].

In the case of large scale optimization problems, one major concern is to find an optimization algorithm able to deliver reliable numerical solutions in a reasonable time. Numerous works have been devoted to accelerate the first order gradient descent technique. These methods aim to increase the convergence rate while preserving theoretical guarantees and limited computational cost/mem- ory burden per iteration. Three main families of acceleration strategies can be distinguished in the literature. The first approach, adopted for example in the well-known L-BFGS [3] and non-linear conjugate gradient [4] methods, relies on subspace acceleration [5,6]. The convergence rate is im- proved by using information from past iterates for the construction of new estimates. Another efficient way to accelerate the convergence of a minimization algorithm is based on a variable met- ric (i.e., preconditioning) strategy [7,8]. The underlying metric is modified at each iteration thanks to a preconditioning matrix, which may incorporate structural second-order information about the function to minimize. The third technique to limit the dependence of an optimization algorithm on the dimension of the problem, is to adopt a block alternating scheme where, at each iteration, only a subset of the variables are updated [9].

Among various choices for preconditioning first-order methods, an important class of techniques rely on the principle of Majorization-Minimization (MM) [10,11]. At each iteration, a quadratic convex surrogate function majorizing $F$ is constructed. The inverse of its curvature (i.e., Hessian) matrix then serves to define a weighted Euclidean metric used for updating the next iterate. This idea is at the core of the half-quadratic algorithm [12,13] for image restoration. It has also been exploited in [14] to build an accelerated proximal gradient method for non smooth optimization, with guaranteed convergence of the iterates to a stationary point, in the non-convex case. The
latter result has been then extended in [15], where block alternating updates are introduced. Block alternating MM approaches have also been explored in [16, 17, 18, 19], although without established convergence guarantees on their iterates in the non-convex setting. MM metrics are also well suited to the construction of efficient subspace optimization methods [20, 21, 22, 10]. In [20], subspace acceleration is employed to reduce the complexity of an MM algorithm in large scale image processing problems, and in [21], convergence guarantees are obtained on the iterates under the KL assumption. This algorithm has recently been extended in [23] to the resolution of convex constrained optimization problems.

In this letter, we propose to bridge the gap between the theoretical analysis from [15] and [20]. We introduce the Block MM Subspace (B2MS) algorithm to solve (1), that incorporates the three aforementioned catalyzing effects, namely (i) MM-based preconditioning, (ii) subspace acceleration, (iii) block alternating update. We show the convergence of its iterates to a critical point of F. We furthermore perform its convergence rate analysis, relying on the KL exponent properties from [24].

The paper is organized as follows. Section 2 introduces the notation, the proposed B2MS algorithm, and the considered assumptions. Section 3 provides technical descent lemmas essential to our analysis. Section 4 presents our main contribution, namely the proof of convergence for B2MS, and a study of its convergence rate. Section 5 discusses the advantages of B2MS acceleration features through an ablation study on a practical problem of sparse signal blind deconvolution. Section 6 concludes the work.

## 2 Block MM subspace algorithm

### 2.1 Notation

We consider the Euclidean space $\mathbb{R}^N$, endowed with the scalar product $\langle \cdot | \cdot \rangle$ and norm $\| \cdot \|$. $I_N$ states for the identity matrix of $\mathbb{R}^N$. For any $\mathbf{A} \in \mathbb{R}^{N \times N}$ symmetric definite positive (SDP), we also introduce the weighted norm $\| \cdot \|_{\mathbf{A}} = \sqrt{\langle \cdot | \mathbf{A} \cdot \rangle}$. Let $\mathcal{S} \subset \{1, \dots, N\} \triangleq \llbracket 1, N \rrbracket$ with cardinal $|\mathcal{S}|$ and complementary set $\bar{\mathcal{S}} \triangleq \llbracket 1, N \rrbracket / \mathcal{S}$. For all $\mathbf{x} = (x^n)_{n \in \llbracket 1, N \rrbracket} \in \mathbb{R}^N$, we denote $\mathbf{x}^{(S)} \triangleq (\mathbf{x}^i)_{i \in \mathcal{S}} \in \mathbb{R}^{|\mathcal{S}|}$. Similarly, the restriction to block $\mathcal{S}$ of the gradient of $F$, at some $\mathbf{x} \in \mathbb{R}^N$ reads $\nabla F^{(S)}(\mathbf{x}) \in \mathbb{R}^{|\mathcal{S}|}$. For any $\mathbf{x} \in \mathbb{R}^N$, we finally introduce function $F^{(S)}(\cdot, \mathbf{x}) : \mathbf{v} \in \mathbb{R}^{|\mathcal{S}|} \mapsto F(\mathbf{u})$ where $\mathbf{u}^{(S)} = \mathbf{v}$ and $\mathbf{u}^{(\bar{S})} = \mathbf{x}^{(\bar{S})}$.

### 2.2 B2MS scheme

The proposed B2MS algorithm solves (1) through a block alternating minimization approach. Let $\mathcal{S}$ a family of $C \ge 1$ nonempty subsets of $\llbracket 1, N \rrbracket$ (not necessarily disjoints). Let $\mathbf{x}_0 \in \mathbb{R}^N$. At every iteration $k \in \mathbb{N}$, the entries of the current iterate $\mathbf{x}_k$ within a selected block $\mathcal{S}_k \in \mathcal{S}$ are updated using one iteration of the MM subspace algorithm [20] on the restriction of $F$ to the $k$-th block $F^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$. The entries of $\mathbf{x}_k$ within the complementary set $\bar{\mathcal{S}}_k$ remain constant.

To implement the MM subspace update, we first build the following quadratic majorant approximation [10] of $F^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$ at $\mathbf{x}_k$,

$$ (\forall \mathbf{v} \in \mathbb{R}^{|\mathcal{S}_k|}) \quad Q^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k) \triangleq F(\mathbf{x}_k) + \langle \nabla F^{(\mathcal{S}_k)}(\mathbf{x}_k), \mathbf{v} - \mathbf{x}_k^{(\mathcal{S}_k)} \rangle + \frac{1}{2} \|\mathbf{v} - \mathbf{x}_k^{(\mathcal{S}_k)}\|_{\mathcal{A}(\mathcal{S}_k)(\mathbf{x}_k)}^2, \quad (2) $$

where $\mathbf{A}^{(\mathcal{S}_k)}(\mathbf{x}_k) \in \mathbb{R}^{|\mathcal{S}_k| \times |\mathcal{S}_k|}$ is an SDP matrix such that:

$$ (\forall \mathbf{v} \in \mathbb{R}^{|\mathcal{S}_k|}) \quad F^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k) \le Q^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k). \quad (3) $$

Second, we choose a subspace acceleration matrix $\mathbf{D}_k \in \mathbb{R}^{|\mathcal{S}_k| \times M_k}$ [5]. The block update $\mathbf{x}_{k+1}^{(\mathcal{S}_k)}$ is then defined as a minimizer of $Q^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$ within the vectorial subspace spanned by the columns of $\mathbf{D}_k$. Iterating the above procedure in a block alternating fashion yields Algorithm (12):

$$ \text{Initialize } \mathbf{x}_0 \in \mathbb{R}^N. \\ \text{For } k = 0, 1, 2, \dots \\ \quad (B2MS) \quad \left\{ \begin{array}{l} \text{Choose } \mathcal{S}_k \in \mathcal{S} \text{ and } \mathbf{D}_k \in \mathbb{R}^{|\mathcal{S}_k| \times M_k} \\ \quad \mathbf{u}_k \in \arg \min_{\mathbf{u} \in \mathbb{R}^{M_k}} Q^{(\mathcal{S}_k)} \left( \mathbf{x}_k^{(\mathcal{S}_k)} + \mathbf{D}_k \mathbf{u}, \mathbf{x}_k \right) \\ \quad \mathbf{x}_{k+1}^{(\mathcal{S}_k)} = \mathbf{x}_k^{(\mathcal{S}_k)} + \mathbf{D}_k \mathbf{u}_k \\ \quad \mathbf{x}_{k+1}^{(\bar{\mathcal{S}}_k)} = \mathbf{x}_k^{(\bar{\mathcal{S}}_k)} \end{array} \right. \quad (4) $$
If $\mathcal{S} = \{[1, N]\}$ (so $C = 1$), we retrieve the MM subspace algorithm from [20, 21]. When $D_k = I_{|S_k|}$, the above approach can be viewed as a particular case of the BSUM scheme [16, 25] using quadratic surrogates, or of the approach from [15] using a null proximal term.

## 2.3 Assumptions

**Assumption 1.**

Family $\mathcal{S}$ verifies $\bigcup_{S \in \mathcal{S}} S = [1, N]$. Moreover, there exists $K \in \mathbb{N}^*$ such that, for all $k \in \mathbb{N}$, every $S \in \mathcal{S}$ belongs to $\{S_k, \dots, S_{k+K-1}\}$.

**Assumption 2.**

$F$ is $C^1$ and coercive on $\mathbb{R}^N$.

**Assumption 3.**

(i) For all $k \in \mathbb{N}$, $D_k$ has full column rank.

(ii) There exists $(\gamma_0, \gamma_1) > 0$ such that, for all $k \in \mathbb{N}$,

$$ (d_k)^\top \nabla F^{(S_k)}(x_k) \leq -\gamma_0 \|\nabla F^{(S_k)}(x_k)\|^2, \quad (5) $$

$$ \|d_k\| \leq \gamma_1 \|\nabla F^{(S_k)}(x_k)\|, \quad (6) $$

with $d_k \in \mathbb{R}^{|S_k|}$ the first column of $D_k$.

**Assumption 4.**

(i) For every $k \in \mathbb{N}$, there exists an SDP matrix $A^{(S_k)}(x_k)$ such that inequality (11) holds.

(ii) There exists $(\eta, \nu) > 0$ such that

$$ (\forall k \in \mathbb{N}) \quad \eta I_{|S_k|} \preceq A^{(S_k)}(x_k) \preceq \nu I_{|S_k|}. \quad (7) $$

**Assumption 5.**

$F$ is Lipschitz differentiable on every bounded subset of $\mathbb{R}^N$. In other words, for each bounded $E \subset \mathbb{R}^N$, there exists $\beta(E) > 0$ such that

$$ (\forall (\mathbf{x}, \mathbf{y}) \in E^2) \quad \|\nabla F(\mathbf{x}) - \nabla F(\mathbf{y})\| \leq \beta(E) \|\mathbf{x} - \mathbf{y}\|. \quad (8) $$

**Assumption 6.** For $\xi \in \mathbb{R}$ and any bounded $E \subset \mathbb{R}^N$, there exists $(\kappa, \zeta, \theta) \in \mathbb{R}_+^* \times \mathbb{R}_+^* \times ]0, 1[$ such that, for all $\mathbf{x} \in E$ with $|F(\mathbf{x}) - \xi| \leq \zeta$,

$$ \|\nabla F(\mathbf{x})\| \geq \kappa |F(\mathbf{x}) - \xi|^\theta. \quad (9) $$

Assumption 7, also adopted in [15], implies that every set of $\mathcal{S}$ is updated at least once during any $K$-length cycle. It is also known as quasi-cyclic or acyclic rule [18], the cyclic rule being a special case of it. Assumption 8 ensures the existence of a minimizer for $F$. Assumption 9(ii) is equivalent to imposing a gradient-related condition [26] on the first column of $D_k$. This is satisfied by a large number of typical subspace acceleration matrices [20][Tab. I]. In particular, setting $D_k = [-\nabla F(x_k)|x_k - x_{k-1}|] \in \mathbb{R}^{N \times 2}$ for $k \in \mathbb{N}^*$ yields the memory gradient subspace [27, 28] which has strong connections with the non-linear conjugate gradient method [29]. Assumption 10 is rather mild, and inherent to the well-posedness and stability of quadratic MM schemes [20, 14]. Assumption 11 is a standard smoothness assumption, also considered in [2]. Finally, Assumption 12 is usually refereed to as the KL inequality [1, 2], and arises from the literature of non-smooth analysis. It is satisfied by a large variety of functions, non necessarily convex, such as semi-algebraic or analytical functions, to name a few. Its use has become popular in the last decade, as it provides a key tool for establishing convergence of iterates for descent methods in the nonconvex setting [24, 15, 8].
## 2.4 Notation

We consider the Euclidean space $\mathbb{R}^N$, endowed with the scalar product $\langle \cdot | \cdot \rangle$ and norm $\| \cdot \|$. $I_N$ states for the identity matrix of $\mathbb{R}^N$. For any $\mathbf{A} \in \mathbb{R}^{N \times N}$ symmetric definite positive (SDP), we also introduce the weighted norm $\| \cdot \|_{\mathbf{A}} = \sqrt{\langle \cdot | \mathbf{A} \cdot \rangle}$. Let $\mathcal{S} \subset \{1, \dots, N\} \triangleq \llbracket 1, N \rrbracket$ with cardinal $|\mathcal{S}|$ and complementary set $\bar{\mathcal{S}} \triangleq \llbracket 1, N \rrbracket / \mathcal{S}$. For all $\mathbf{x} = (x^n)_{n \in \llbracket 1, N \rrbracket} \in \mathbb{R}^N$, we denote $\mathbf{x}^{(\mathcal{S})} \triangleq (\mathbf{x}^i)_{i \in \mathcal{S}} \in \mathbb{R}^{|\mathcal{S}|}$. Similarly, the restriction to block $\mathcal{S}$ of the gradient of $F$, at some $\mathbf{x} \in \mathbb{R}^N$ reads $\nabla F^{(\mathcal{S})}(\mathbf{x}) \in \mathbb{R}^{|\mathcal{S}|}$. For any $\mathbf{x} \in \mathbb{R}^N$, we finally introduce function $F^{(\mathcal{S})}(\cdot, \mathbf{x}) : \mathbf{v} \in \mathbb{R}^{|\mathcal{S}|} \mapsto F(\mathbf{u})$ where $\mathbf{u}^{(\mathcal{S})} = \mathbf{v}$ and $\mathbf{u}^{(\bar{\mathcal{S}})} = \mathbf{x}^{(\bar{\mathcal{S}})}$.

## 2.5 B2MS scheme

The proposed B2MS algorithm solves (1) through a block alternating minimization approach. Let $\mathcal{S}$ a family of $C \ge 1$ nonempty subsets of $\llbracket 1, N \rrbracket$ (not necessarily disjoints). Let $\mathbf{x}_0 \in \mathbb{R}^N$. At every iteration $k \in \mathbb{N}$, the entries of the current iterate $\mathbf{x}_k$ within a selected block $\mathcal{S}_k \in \mathcal{S}$ are updated using one iteration of the MM subspace algorithm [20] on the restriction of $F$ to the $k$-th block $F^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$. The entries of $\mathbf{x}_k$ within the complementary set $\bar{\mathcal{S}}_k$ remain constant.

To implement the MM subspace update, we first build the following quadratic majorant approximation [10] of $F^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$ at $\mathbf{x}_k$,

$$ (\forall \mathbf{v} \in \mathbb{R}^{|\mathcal{S}_k|}) \quad Q^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k) \triangleq F(\mathbf{x}_k) + \langle \nabla F^{(\mathcal{S}_k)}(\mathbf{x}_k), \mathbf{v} - \mathbf{x}_k^{(\mathcal{S}_k)} \rangle + \frac{1}{2} \|\mathbf{v} - \mathbf{x}_k^{(\mathcal{S}_k)}\|_{\mathbf{A}^{(\mathcal{S}_k)}(\mathbf{x}_k)}^2, \quad (10) $$

where $\mathbf{A}^{(\mathcal{S}_k)}(\mathbf{x}_k) \in \mathbb{R}^{|\mathcal{S}_k| \times |\mathcal{S}_k|}$ is an SDP matrix such that:

$$ (\forall \mathbf{v} \in \mathbb{R}^{|\mathcal{S}_k|}) \quad F^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k) \le Q^{(\mathcal{S}_k)}(\mathbf{v}, \mathbf{x}_k). \quad (11) $$

Second, we choose a subspace acceleration matrix $\mathbf{D}_k \in \mathbb{R}^{|\mathcal{S}_k| \times M_k}$ [5]. The block update $\mathbf{x}_{k+1}^{(\mathcal{S}_k)}$ is then defined as a minimizer of $Q^{(\mathcal{S}_k)}(\cdot, \mathbf{x}_k)$ within the vectorial subspace spanned by the columns of $\mathbf{D}_k$. Iterating the above procedure in a block alternating fashion yields Algorithm (12):

$$ \text{Initialize } \mathbf{x}_0 \in \mathbb{R}^N. \\ \text{For } k = 0, 1, 2, \dots \\ \quad \left( \begin{array}{@{}l@{}} \text{Choose } \mathcal{S}_k \in \mathcal{S} \text{ and } \mathbf{D}_k \in \mathbb{R}^{|\mathcal{S}_k| \times M_k} \\ \quad (B2MS) \left[ \begin{array}{@{}l@{}} \mathbf{u}_k \in \arg \min_{\mathbf{u} \in \mathbb{R}^{M_k}} Q^{(\mathcal{S}_k)} \left( \mathbf{x}_k^{(\mathcal{S}_k)} + \mathbf{D}_k \mathbf{u}, \mathbf{x}_k \right) \\ \quad \mathbf{x}_{k+1}^{(\mathcal{S}_k)} = \mathbf{x}_k^{(\mathcal{S}_k)} + \mathbf{D}_k \mathbf{u}_k \\ \quad \mathbf{x}_{k+1}^{(\bar{\mathcal{S}}_k)} = \mathbf{x}_k^{(\bar{\mathcal{S}}_k)} \end{array} \right. \end{array} \right. \quad (12) $$

If $\mathcal{S} = \{\llbracket 1, N \rrbracket\}$ (so $C = 1$), we retrieve the MM subspace algorithm from [20, 21]. When $\mathbf{D}_k = I_{|\mathcal{S}_k|}$, the above approach can be viewed as a particular case of the BSUM scheme [16, 25] using quadratic surrogates, or of the approach from [15] using a null proximal term.

## 2.6 Assumptions

**Assumption 7.**

Family $\mathcal{S}$ verifies $\bigcup_{\mathcal{S} \in \mathcal{S}} S = \llbracket 1, N \rrbracket$. Moreover, there exists $K \in \mathbb{N}^*$ such that, for all $k \in \mathbb{N}$, every $S \in \mathcal{S}$ belongs to $\{\mathcal{S}_k, \dots, \mathcal{S}_{k+K-1}\}$.

**Assumption 8.**

$F$ is $C^1$ and coercive on $\mathbb{R}^N$.

**Assumption 9.**

(i) For all $k \in \mathbb{N}$, $\mathbf{D}_k$ has full column rank.

(ii) There exists $(\gamma_0, \gamma_1) > 0$ such that, for all $k \in \mathbb{N}$,

$$ (\mathbf{d}_k)^\top \nabla F^{(\mathcal{S}_k)}(\mathbf{x}_k) \le -\gamma_0 \|\nabla F^{(\mathcal{S}_k)}(\mathbf{x}_k)\|^2, \quad (13) $$

$$ \|\mathbf{d}_k\| \le \gamma_1 \|\nabla F^{(\mathcal{S}_k)}(\mathbf{x}_k)\|, \quad (14) $$

with $\mathbf{d}_k \in \mathbb{R}^{|\mathcal{S}_k|}$ the first column of $\mathbf{D}_k$.
**Assumption 10.**

(i) For every $k \in \mathbb{N}$, there exists an SDP matrix $A^{(S_k)}(\mathbf{x}_k)$ such that inequality (11) holds.

(ii) There exists $(\eta, \nu) > 0$ such that

$$ (\forall k \in \mathbb{N}) \quad \eta \mathbf{I}_{|S_k|} \preceq A^{(S_k)}(\mathbf{x}_k) \preceq \nu \mathbf{I}_{|S_k|}. \qquad (15) $$

**Assumption 11.**

$F$ is Lipschitz differentiable on every bounded subset of $\mathbb{R}^N$. In other words, for each bounded $E \subset \mathbb{R}^N$, there exists $\beta(E) > 0$ such that

$$ (\forall (\mathbf{x}, \mathbf{y}) \in E^2) \quad \|\nabla F(\mathbf{x}) - \nabla F(\mathbf{y})\| \le \beta(E) \|\mathbf{x} - \mathbf{y}\|. \qquad (16) $$

**Assumption 12.** For $\xi \in \mathbb{R}$ and any bounded $E \subset \mathbb{R}^N$, there exists $(\kappa, \zeta, \theta) \in \mathbb{R}_+^* \times \mathbb{R}_+^* \times ]0, 1[$ such that, for all $\mathbf{x} \in E$ with $|F(\mathbf{x}) - \xi| \le \zeta$,

$$ \|\nabla F(\mathbf{x})\| \ge \kappa |F(\mathbf{x}) - \xi|^\theta. \qquad (17) $$

Assumption 7, also adopted in [15], implies that every set of $\mathcal{S}$ is updated at least once during any $K$-length cycle. It is also known as quasi-cyclic or a cyclic rule [18], the cyclic rule being a special case of it. Assumption 8 ensures the existence of a minimizer for $F$. Assumption 9(ii) is equivalent to imposing a gradient-related condition [26] on the first column of $D_k$. This is satisfied by a large number of typical subspace acceleration matrices [20][Tab. I]. In particular, setting $D_k = [-\nabla F(\mathbf{x}_k)|\mathbf{x}_k - \mathbf{x}_{k-1}] \in \mathbb{R}^{N \times 2}$ for $k \in \mathbb{N}^*$ yields the memory gradient subspace [27, 28] which has strong connections with the non-linear conjugate gradient method [29]. Assumption 10 is rather mild, and inherent to the well-posedness and stability of quadratic MM schemes [20, 14]. Assumption 11 is a standard smoothness assumption, also considered in [2]. Finally, Assumption 12 is usually refereed to as the KL inequality [1, 2], and arises from the literature of non-smooth analysis. It is satisfied by a large variety of functions, non necessarily convex, such as semi-algebraic or analytical functions, to name a few. Its use has become popular in the last decade, as it provides a key tool for establishing convergence of iterates for descent methods in the nonconvex setting [24, 15, 8].

## 3 Technical lemmas

This section presents technical lemmas that turn out to be essential to our convergence analysis.

**Lemma 1** Under Assumptions 7-8-9-10(i), $(F(\mathbf{x}_k))_{k \in \mathbb{N}}$ converges to a finite limit and sequence $(\mathbf{x}_k)_{k \in \mathbb{N}}$ is bounded. Moreover, under Assumptions 7-8-9-10, the B2MS sequence $(\mathbf{x}_k)_{k \in \mathbb{N}}$ satisfies:

$$ (\forall k \in \mathbb{N}) \quad F(\mathbf{x}_k) - F(\mathbf{x}_{k+1}) \ge \frac{\gamma_0^2}{2\gamma_1^2\nu} \|\nabla F^{(S_k)}(\mathbf{x}_k)\|^2, \qquad (18) $$

$$ \sum_{k=0}^{+\infty} \|\nabla F^{(S_k)}(\mathbf{x}_k)\|^2 < +\infty, \qquad (19) $$

$$ (\forall k \in \mathbb{N}) \quad \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2 \le \frac{1}{\eta^2} \|\nabla F^{(S_k)}(\mathbf{x}_k)\|^2, \qquad (20) $$

$$ (\forall k \in \mathbb{N}) \quad \|\nabla F^{(S_k)}(\mathbf{x}_k)\|^2 \le \frac{\gamma_1^2 \nu^2}{\gamma_0^2} \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2. \qquad (21) $$

*Proof.* Consider $k \in \mathbb{N}$. Since $\mathbf{x}_{k+1}$ is the concatenation of $\mathbf{x}_{k+1}^{(S_k)}$ and $\mathbf{x}_k^{(\overline{S_k})}$, the use of the majorizing inequality (11) (Assumption 10(i)) gives,

$$ F(\mathbf{x}_{k+1}) = F^{(S_k)}(\mathbf{x}_{k+1}^{(S_k)}, \mathbf{x}_k) \le Q^{(S_k)}(\mathbf{x}_{k+1}^{(S_k)}, \mathbf{x}_k) = Q^{(S_k)}(\mathbf{x}_k^{(S_k)} + \mathbf{D}_k \mathbf{u}_k, \mathbf{x}_k). \qquad (22) $$

Let $e = (1, 0, \dots, 0)^\top \in \mathbb{R}^{M_k}$. Since $\mathbf{u}_k$ minimizes $Q^{(S_k)}(\mathbf{x}_k^{(S_k)} + \mathbf{D}_k \cdot, \mathbf{x}_k)$, any $t \in \mathbb{R}$ satisfies

$$ Q^{(S_k)}(\mathbf{x}_k^{(S_k)} + \mathbf{D}_k \mathbf{u}_k, \mathbf{x}_k) \le Q^{(S_k)}(\mathbf{x}_k^{(S_k)} + \mathbf{D}_k te, \mathbf{x}_k) = Q^{(S_k)}(\mathbf{x}_k^{(S_k)} + t \mathbf{d}_k, \mathbf{x}_k). $$
Moreover, $t \mapsto Q^{(S_k)}(x_k^{(S_k)} + t d_k, x_k)$ is scalar quadratic with $F(x_k) - \frac{\langle \nabla F^{(S_k)}(x_k), d_k \rangle^2}{2\|d_k\|_{A^{(S_k)}(x_k)}^2}$ as minimal value. Hence, Assumptions 9 leads to

$$Q^{(S_k)}(x_k^{(S_k)} + D_k u_k, x_k) \le F(x_k) - \frac{\langle \nabla F^{(S_k)}(x_k), d_k \rangle^2}{2\|d_k\|_{A^{(S_k)}(x_k)}^2} \le F(x_k) - \frac{\gamma_0^2 \|\nabla F^{(S_k)}(x_k)\|^2}{2\|d_k\|_{A^{(S_k)}(x_k)}^2}. \quad (23)$$

Combining (23) and (22) ensures that $(F(x_k))_{k \in \mathbb{N}}$ is a decreasing sequence. The coercivity of $F$ in Assumption 8 both guarantees that $(F(x_k))_{k \in \mathbb{N}}$ converges to a finite limit $F^\infty$ and that $(x_k)_{k \in \mathbb{N}}$ is bounded, which concludes the first part of the proof. Using now Assumption 10(ii) and (23) leads to

$$Q^{(S_k)}(x_k^{(S_k)} + D_k u_k, x_k) \le F(x_k) - \frac{\gamma_0^2}{2\gamma_1^2 \nu} \|\nabla F^{(S_k)}(x_k)\|^2. \quad (24)$$

Combination of (24) with (22) directly gives (18) in Lemma 1. Moreover,

$$\sum_{k=0}^{+\infty} \|\nabla F^{(S_k)}(x_k)\|^2 \le \frac{2\gamma_1^2 \nu}{\gamma_0^2} (F^\infty - F(x_0)), \quad (25)$$

so that (19) in Lemma 1 is obtained. Since function $Q^{(S_k)}(x_k^{(S_k)} + D_k \cdot, x_k)$ is quadratic, we also deduce that its minimizer $u_k$ satisfies:

$$(\nabla F^{(S_k)}(x_k))^{\top} D_k u_k = - \|D_k u_k\|_{A^{(S_k)}(x_k)}^2. \quad (26)$$

Equality $D_k u_k = x_{k+1} - x_k$, and Assumption 10(ii), lead to

$$Q^{(S_k)}(x_k^{(S_k)} + D_k u_k, x_k) = F(x_k) - \frac{1}{2} \|D_k u_k\|_{A^{(S_k)}(x_k)}^2 \ge F(x_k) - \frac{\nu}{2} \|x_{k+1} - x_k\|^2. \quad (27)$$

Equation (21) of Lemma 1 then comes by plugging (27) into (24). Using again the expression of $u_k$ as a minimizer of a quadratic form, we can rewrite one iteration of B2MS scheme as

$$x_{k+1} - x_k = -B_k \nabla F^{(S_k)}(x_k), \quad (28)$$

with $B_k \triangleq D_k (D_k^\top A^{(S_k)}(x_k) D_k)^{-1} D_k^\top$. Remark that Assumption 9(i) ensures that $B_k$ is a well-defined symmetric definite positive matrix. Then, by Assumption 10(ii),

$$B_k \preceq \frac{1}{\eta} D_k (D_k^\top D_k)^{-1} D_k^\top \preceq \frac{1}{\eta} I_{|S_k|}. \quad (29)$$

Plugging (29) into (28) and taking the squared norm of the quantities gives (20).

□

**Lemma 2** Let $(u_k)_{k \in \mathbb{N}}$, $(v_k)_{k \in \mathbb{N}}$ two sequences of positive real. If there exists $k^* \ge K$ such that

$$(\forall k \ge k^*) \quad u_k \le \rho \sum_{i=k-K}^{k-1} u_i + v_{k-1}, \quad (30)$$

if $\rho < \frac{1}{K}$ and $\sum_{k=0}^{+\infty} v_k < +\infty$, then $\sum_{k=0}^{+\infty} u_k < +\infty$.

*Proof.* Summing (30) from $k^*$ to $n \ge k^*$ leads to

$$\sum_{k=k^*}^{n} u_k \le \rho \sum_{k=k^*}^{n} \sum_{i=k-K}^{k-1} u_i + \sum_{k=k^*}^{n} v_{k-1}, \quad (31)$$

with

$$\sum_{k=k^*}^{n} \sum_{i=k-K}^{k-1} u_i = \sum_{k=k^*}^{n} \sum_{i=1}^{K} u_{k-i} = \sum_{i=1}^{K} \sum_{k=k^*-i}^{n-i} u_k \le \sum_{i=1}^{K} \sum_{k=0}^{n} u_k. \quad (32)$$
Plugging (32) into (31), yields

$$ \sum_{k=k^*}^{n} u_k \le \rho K \sum_{k=k^*}^{n} u_k + \left( \rho K \sum_{k=0}^{k^*-1} u_k + \sum_{k=k^*}^{n} v_{k-1} \right) \le \rho K \sum_{k=k^*}^{n} u_k + \left( \rho K \sum_{k=0}^{k^*-1} u_k + \sum_{k=0}^{+\infty} v_k \right), \quad (33) $$

that is $(1 - \rho K) \sum_{k=k^*}^{n} u_k \le \rho K \sum_{k=0}^{k^*-1} u_k + \sum_{k=0}^{+\infty} v_k$. With $0 < 1 - \rho K < 1$, we deduce the summability of $(u_k)_{k \in \mathbb{N}}$. $\square$

Lemma 1 gathers the different inequalities and descent properties which result from B2MS scheme (12). Equations (18)-(19) can be interpreted as a generalized block version of [20, Theorem 1]. Lemma 2 is an alternative of [30, Lemma 3], [31, Lemma 5.1].

## 4 Asymptotical behaviour

For the sake of clarity, our presentation for the convergence analysis of scheme (12) is divided into three parts. First, we establish the convergence of the gradient of the B2MS iterates to zero, under Assumptions 7-11. Second, under the additional Assumption 12 (i.e., KL inequality), we show the convergence of the iterates of B2MS to a stationary point. Third, we establish a convergence rate result involving the KL exponent $\theta$ of function $F$.

### 4.1 Global convergence

**Theorem 1** Let $(x_k)_{k \in \mathbb{N}}$ the B2MS sequence. Under Assumptions 7-11, sequence $(\|\nabla F(x_k)\|)_{k \in \mathbb{N}}$ converges to 0. Moreover, there exists $x^*$, a stationary point of $F$, such that $F(x_k) \underset{k \to +\infty}{\to} F(x^*)$.

*Proof.* Let $k \ge K$. For all $S \in \mathcal{S}$, Assumption 7 ensures that $\{t \in [k - K, k - 1] / S_t = S\}$ is a non-empty set. We can thus rewrite every set of $\mathcal{S}$ as $S = S_{T_k^S}$ with

$$ T_k^S \triangleq \max \{t \in [k - K, k - 1] / S_t = S\}. $$

The application of $k - T_k^S$ Jensen's inequalities on $\|\nabla F^S(x_k)\|^2$ leads to

$$ \|\nabla F^{(S)}(x_k)\|^2 \le \sum_{i=T_k^S}^{k-1} 2^{k-i} \|\nabla F^{(S)}(x_{i+1}) - \nabla F^{(S)}F(x_i)\|^2 + 2^{k-T_k^S} \|\nabla F^{(S)}F(x_{T_k^S})\|^2. \quad (34) $$

We now majorize both parts of the right term of (34). According to Lemma 1, the iterates belong to a bounded set that we denote $E$. Using Assumption 11, we apply inequality (16), using the short notation $\beta \triangleq \beta(E)$, and then apply (20). The latter part of (34) is handled by using $S = S_{T_k^S}$ and noticing that $k - i \in ]0, K[$ for $i \in [T_k^S, k - 1]$. It yields

$$ \begin{aligned} \|\nabla F^{(S)}(x_k)\|^2 &\le \frac{2^K \beta^2}{\eta^2} \sum_{i=T_k^S}^{k-1} \|\nabla F^{(S_i)}(x_i)\|^2 + 2^K \|\nabla F^{(S_{T_k^S})}(x_{T_k^S})\|^2, \\ &\le 2^K \left( \frac{\beta^2}{\eta^2} + 1 \right) \sum_{i=T_k^S}^{k-1} \|\nabla F^{(S_i)}(x_i)\|^2, \\ &\le 2^K \left( \frac{\beta^2}{\eta^2} + 1 \right) \sum_{i=k-K}^{k-1} \|\nabla F^{(S_i)}(x_i)\|^2. \end{aligned} \quad (35) $$

Then from (19) we have $\|\nabla F^{(S)}(x_k)\|^2 \underset{k \to +\infty}{\to} 0$. Since $[1, N] = \bigcup_{S \in \mathcal{S}} S$ (by Ass. 7) and $\mathcal{S}$ finite,

$$ \|\nabla F(x_k)\|^2 \le \sum_{S \in \mathcal{S}} \|\nabla F^{(S)}(x_k)\|^2 \underset{k \to +\infty}{\to} 0. \quad (36) $$

According to Lemma 1, $(F(x_k))_{k \in \mathbb{N}}$ converges to a finite limit denoted $F^\infty$. The boundedness of $(x_k)_{k \in \mathbb{N}}$ guarantees the existence of $x^* \in \mathbb{R}^n$, an accumulation point of $(x_k)_{k \in \mathbb{N}}$. As $\|\nabla F(x_k)\| \underset{k \to +\infty}{\to} 0$ and $\nabla F$ is continuous (by Ass. 8), $\nabla F(x^*) = 0$ directly follows, so that $x^*$ is a stationary point of $F$. Moreover, $F^\infty = F(x^*)$ since $F$ is continuous, which concludes our proof. $\square$
Theorem 1 shows a classical behaviour for a descent method applied to a non-convex Lipschitz differentiable objective function [32].

## 4.2 Sequence convergence

This part is dedicated to refine the result of Theorem 1, when we additionally introduce Assumption 12. We first state a technical inequality giving a direct relation between the gradient at the current iterate and the differences of past iterates over a cycle (i.e a K-length period)

**Proposition 1.** Let $(\mathbf{x}_k)_{k \in \mathbb{N}}$ the B2MS sequence. Under Assumptions 7-11, for all $k \ge K$,

$$ \|\nabla F(\mathbf{x}_k)\|^2 \le 2^K C \left( \beta^2 + \frac{\gamma_1^2}{\gamma_0^2} \nu^2 \right) \sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2. \quad (37) $$

*Proof.* Let $k \ge K$. The beginning of the proof is identical to that of Theorem 1 until Eq.(34). We then derive a new majoration for the quantity involved in the right term of (34). We first majorize using Ass. 8 combined with $S = S_{T_k^S}$. We then use (21) of Lemma 1. This yields:

$$ \begin{aligned} \|\nabla F^{(S)}(\mathbf{x}_k)\|^2 &\le 2^K \beta^2 \sum_{i=T_k^S}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2 + 2^K \|\nabla F^{(S_{T_k^S})}(\mathbf{x}_{T_k^S})\|^2, \\ &\le 2^K \beta^2 \sum_{i=T_k^S}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2 + 2^K \frac{\nu^2 \gamma_1^2}{\gamma_0^2} \|\mathbf{x}_{T_k^S+1} - \mathbf{x}_{T_k^S}\|^2, \\ &\le 2^K \left( \beta^2 + \frac{\gamma_1^2}{\gamma_0^2} \nu^2 \right) \sum_{i=T_k^S}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2, \\ &\le 2^K \left( \beta^2 + \frac{\gamma_1^2}{\gamma_0^2} \nu^2 \right) \sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2. \end{aligned} \quad (38) $$

We then sum (38) over $\mathcal{S}$ (of cardinal $C$). The right term being independent from $S$, it is simply multiplied by $C$. Then, noting that $\|\nabla F(\mathbf{x}_k)\|^2 \le \sum_{S \in \mathcal{S}} \|\nabla F^{(S)}(\mathbf{x}_k)\|^2$ concludes our proof. $\square$

Remark that an alternative proof of Theorem 1 could be obtained from Prop. 1. However, inequality (35) is more direct to demonstrate than (37).

We finally state our main theoretical result, namely the convergence of the iterates of B2MS scheme.

**Theorem 2** Let $(\mathbf{x}_k)_{k \in \mathbb{N}}$ the B2MS sequence. Under Assumptions 7-12,

$$ \sum_{k=0}^{+\infty} \|\mathbf{x}_{k+1} - \mathbf{x}_k\| < +\infty. \quad (39) $$

Moreover, $(\mathbf{x}_k)_{k \in \mathbb{N}}$ converges to a stationary point of $F$.

*Proof.* Following the same notations as those of Theorem 1, let us apply (17) to set $E = \{\mathbf{x}_k / k \in \mathbb{N}\}$, which is a bounded set by Lemma 1, and $\xi = F^\infty$. Then, by KL inequality (Ass. 12), there exists $(\kappa, \zeta, \theta) \in \mathbb{R}_+^* \times \mathbb{R}_+^* \times ]0, 1[$ such that for every $k \in \mathbb{N}$ verifying $|F(\mathbf{x}_k) - F^\infty| \le \zeta$,

$$ \|\nabla F(\mathbf{x}_k)\| \ge \kappa |F(\mathbf{x}_k) - F^\infty|^\theta. \quad (40) $$

Using (21) and (18) gives, for every $k \in \mathbb{N}$,

$$ \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2 \le \frac{2\gamma_1^2\nu}{\gamma_0^2\eta^2} (F(\mathbf{x}_k) - F(\mathbf{x}_{k+1})) = \frac{2\gamma_1^2\nu}{\gamma_0^2\eta^2} [(F(\mathbf{x}_k) - F^\infty) - (F(\mathbf{x}_{k+1}) - F^\infty)]. \quad (41) $$

Let us now invoke the convexity of $v \in \mathbb{R}_+ \mapsto v^{\frac{1}{1-\theta}}$. It follows that for all $v, w \in \mathbb{R}_+$ with $v \le w$

$$ w - v \le (1 - \theta)^{-1} w^{\theta} (w^{1-\theta} - v^{1-\theta}). \quad (42) $$
Plugging (42) in (41) with $w = F(\mathbf{x}_k) - F^\infty$ and $v = F(\mathbf{x}_{k+1}) - F^\infty$ yields, for every $k \in \mathbb{N}$,

$$ \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2 \le \frac{2\gamma_1^2\nu}{\gamma_0^2\eta^2(1-\theta)} [F(\mathbf{x}_k) - F^\infty]^\theta \Delta^k, \quad (43) $$

with $\Delta_k \triangleq (F(\mathbf{x}^k) - F^\infty)^{1-\theta} - (F(\mathbf{x}_{k+1}) - F^\infty)^{1-\theta}$. Since $F(\mathbf{x}_k) \underset{k \to +\infty}{\longrightarrow} F^\infty$, there exists $k_0 \ge K$ such that

$$ (\forall k \ge k_0) \quad |F(\mathbf{x}_k) - F^\infty| \le \zeta. \quad (44) $$

Thus, using (40),

$$ (\forall k \ge k_0) \quad \|\nabla F(\mathbf{x}_k)\| \ge \kappa |F(\mathbf{x}_k) - F^\infty|^\theta. \quad (45) $$

Combining (45) and (43) leads to

$$ (\forall k \ge k_0) \quad \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2 \le \frac{2\gamma_1^2\nu}{\gamma_0^2\eta^2\kappa(1-\theta)} \|\nabla F(\mathbf{x}_k)\| \Delta_k. \quad (46) $$

We now rely on the majoration of Proposition 1, to obtain

$$ (\forall k \ge k_0) \quad \|\mathbf{x}_{k+1} - \mathbf{x}_k\|^2 \le \Lambda \sqrt{\sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|^2} \quad \Delta_k \le \Lambda \sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\| \Delta_k, \quad (47) $$

with $\Lambda \triangleq \frac{2\gamma_1^2}{\kappa(1-\theta)} \frac{\gamma_0^2\nu}{\gamma_0^2\eta^2} \sqrt{C} \sqrt{\beta^2 + \frac{\gamma_1^2}{\gamma_0^2}\nu^2}$. We extract the square root of (47) and invoke the inequality $\sqrt{ab} \le \frac{a}{c} + \frac{bc}{4}$ with $a = \sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\|$, $b = \Delta_k$ and some $c > 0$. Then,

$$ (\forall k \ge k_0) \quad \|\mathbf{x}_{k+1} - \mathbf{x}_k\| \le \frac{\sqrt{\Lambda}}{c} \sum_{i=k-K}^{k-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\| + \frac{c}{4} \sqrt{\Lambda} \Delta_k. \quad (48) $$

($\Delta_k$)$_{k \in \mathbb{N}}$ is summable and $\sqrt{\Lambda}/c \in [0, 1/K]$ for $c > \sqrt{\Lambda}K$, we apply Lemma 2 with $k^* = k_0$. Finally, $(\|\mathbf{x}_{k+1} - \mathbf{x}_k\|)$$_{k \in \mathbb{N}}$ is summable and $(\mathbf{x}_k)$$_{k \in \mathbb{N}}$ is a Cauchy sequence possessing $\mathbf{x}^*$ as an accumulation point. Sequence $(\mathbf{x}_k)$$_{k \in \mathbb{N}}$ thus converges to $\mathbf{x}^*$. $\square$

## 4.3 Convergence rate

As highlighted above, Theorem 2 guarantees the convergence of sequence $(\mathbf{x}_k)_{k \in \mathbb{N}}$ to $\mathbf{x}^*$, a stationary point of function $F$. Our last contribution lies in characterizing the convergence rate for B2MS algorithm. Here again, KL inequality (Ass. 12) is an anchor point of our analysis.

**Theorem 3** Let $(\mathbf{x}_k)_{k \in \mathbb{N}}$ the B2MS sequence. Under Assumptions 7-12, the following holds.

(i) if $\theta \in [1/2, 1[$, then $\|\mathbf{x}_k - \mathbf{x}^*\| = \mathcal{O}(k^{-\frac{1-\theta}{2\theta-1}})$;

(ii) If $\theta \in [0, 1/2]$, then there exists $\varepsilon \in [0, 1[$ such that $\|\mathbf{x}_k - \mathbf{x}^*\| = \mathcal{O}(\varepsilon^k)$.

*Proof.* Keeping the same notations as previously, let $c > 0$ and $k \ge k_0$. We sum (48) from $kK$

$$ \Gamma_k \le \frac{\sqrt{\Lambda}}{c} \sum_{j=kK}^{+\infty} \sum_{i=j-K}^{j-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\| + \frac{c}{4} \sqrt{\Lambda} \sum_{j=kK}^{+\infty} \Delta_j, \quad (49) $$

with $\Gamma_k \triangleq \sum_{j=kK}^{+\infty} \|\mathbf{x}_{j+1} - \mathbf{x}_j\|$. On the one hand,

$$ \begin{aligned} \sum_{j=kK}^{+\infty} \sum_{i=j-K}^{j-1} \|\mathbf{x}_{i+1} - \mathbf{x}_i\| &= \sum_{j=kK}^{+\infty} \sum_{i=0}^{K-1} \|\mathbf{x}_{i+j-K+1} - \mathbf{x}_{i+j-K}\|, \\ &= \sum_{i=0}^{K-1} \sum_{j=kK}^{+\infty} \|\mathbf{x}_{i+j-K+1} - \mathbf{x}_{i+j-K}\| \le K\Gamma_{k-1}. \end{aligned} \quad (50) $$
On the other hand, using $F(\boldsymbol{x}) - F(\boldsymbol{x}^*) \underset{k \to +\infty}{\longrightarrow} 0$, (40) and Proposition 1, yields

$$ 
\begin{align} 
[F(\boldsymbol{x}_{kK}) - F(\boldsymbol{x}^*)]^{1-\theta} &\le \kappa^{\frac{\theta-1}{\theta}} \|\nabla F(\boldsymbol{x}_{kK})\|^{1-\frac{\theta}{\theta}} 
&\le \Lambda' \left( \sum_{j=(k-1)K}^{kK-1} \|\boldsymbol{x}_{j+1} - \boldsymbol{x}_j\|^2 \right)^{\frac{1-\theta}{2\theta}}, \nonumber \\
&\le \Lambda' \left( \sum_{j=(k-1)K}^{kK-1} \|\boldsymbol{x}_{j+1} - \boldsymbol{x}_j\| \right)^{\frac{1-\theta}{\theta}}, \nonumber \\
&= \Lambda' (\Gamma_{k-1} - \Gamma_k)^{\frac{1-\theta}{\theta}}, \tag{51}
\end{align} 
$$

with $\Lambda' \triangleq \kappa^{\frac{\theta-1}{\theta}} (2^K C (\beta^2 + \frac{\gamma_1^2}{\gamma_0^2} \nu^2))^{\frac{1-\theta}{2\theta}}$. Plugging (50), (51) in (49), with $c = 2\sqrt{\Lambda}K$ and $\sum_{j=kK}^{+\infty} \Delta_j = [F(\boldsymbol{x}_{kK}) - F(\boldsymbol{x}^*)]^{1-\theta}$ gives

$$ \Gamma_k \le \frac{1}{2} \Gamma_{k-1} + \frac{1}{2} K \Lambda \Lambda' (\Gamma_{k-1} - \Gamma_k)^{\frac{1-\theta}{\theta}}. \quad (52) $$

By multiplying (52) by 2 and removing $\Gamma_k$ from each side,

$$ \Gamma_k \le (\Gamma_{k-1} - \Gamma_k) + K \Lambda \Lambda' (\Gamma_{k-1} - \Gamma_k)^{\frac{1-\theta}{\theta}}. \quad (53) $$

Since $(\Gamma_k)_{k \in \mathbb{N}}$ is a positive decreasing sequence to zero, we can apply [24, Theorem 2].

* If $\theta \in ]1/2, 1[$, there exists $\lambda > 0$ such that

$$ (\forall k \ge k_0) \quad \Gamma_k \le \lambda k^{-\frac{1-\theta}{2\theta-1}}. \quad (54) $$

Denoting $q(k), r(k)$ the quotient and remainder of the Euclidean division of $k$ by $K$, leads to

$$ \|\boldsymbol{x}_k - \boldsymbol{x}^*\| = \|\boldsymbol{x}_{q(k)K+r(k)} - \boldsymbol{x}^*\| \le \Gamma_{q(k)}. \quad (55) $$

Combining (55) with (54) gives, for $k$ large enough,

$$ \|\boldsymbol{x}_k - \boldsymbol{x}^*\| \le \lambda q(k)^{-\frac{1-\theta}{2\theta-1}} = \lambda \left(\frac{k-r(k)}{K}\right)^{-\frac{1-\theta}{2\theta-1}} \le \lambda \left(\frac{k}{K}-1\right)^{-\frac{1-\theta}{2\theta-1}}, \quad (56) $$

with $\lambda (\frac{k}{K}-1)^{-\frac{1-\theta}{2\theta-1}} = \mathcal{O}(k^{-\frac{1-\theta}{2\theta-1}})$.

* If $\theta \in ]0, 1/2]$, there exist $\mu > 0$ and $\delta \in ]0, 1[$ such that

$$ (\forall k \ge k_0) \quad \Gamma_k \le \mu \delta^k. \quad (57) $$

Similarly with the previous case, for $k$ large enough,

$$ \|\boldsymbol{x}_k - \boldsymbol{x}^*\| \le \mu \delta^{q(k)} = \mu \delta^{\frac{k-r(k)}{K}} \le \mu \delta^{\frac{k}{K}}. \quad (58) $$

Conclusion is obtained by taking $\varepsilon = \delta^{\frac{1}{K}} \in ]0, 1[$.

□

One can notice the dependency of the convergence rate with the KL exponent $\theta$. This result is similar to the one in [15], though with a more direct proof following naturally from our global convergence Theorem 2. We also notice that the gradient Lipschitz property (see Assumption 11) entails that the convergence rate obtained for $(\|\boldsymbol{x}_k - \boldsymbol{x}^*\|)_{k \in \mathbb{N}}$ also holds for the sequence $(\|\nabla F(\boldsymbol{x}_k)\|)_{k \in \mathbb{N}}$.
# 5 Numerical illustration

## 5.1 Problem formulation

Let us illustrate numerically the benefits of each acceleration features introduced in B2MS. To do so, we focus on the signal processing problem of sparse signal blind deconvolution [33]. Let $\mathbf{y} \in \mathbb{R}^P$, $P \ge 1$, a vector of observations, related to a sought signal $\bar{\mathbf{z}} \in \mathbb{R}^P$ through the model

$$ \mathbf{y} = \bar{\mathbf{h}} * \bar{\mathbf{z}} + \mathbf{e}, \qquad (59) $$

with $\bar{\mathbf{h}} \in \mathbb{R}^L$, $L \ge 1$, a blur kernel, * the 1D discrete convolution operator with zero-padding assumption, and $\mathbf{e} \in \mathbb{R}^P$ a realization of an i.i.d. zero-mean Gaussian distribution. Blind deconvolution amounts to retrieving estimates $(\tilde{\mathbf{z}}, \tilde{\mathbf{h}})$ of $(\bar{\mathbf{z}}, \bar{\mathbf{h}})$ from $\mathbf{y}$ under some structural assumptions. Namely here, we consider a sparse signal $\bar{\mathbf{z}}$, with few non-zero entries within the range $[z_{\min}, z_{\max}]$, $-\infty < z_{\min} < z_{\max} < +\infty$, and a blur kernel with bounded energy and entries within the range $[h_{\min}, h_{\max}]$, $-\infty < h_{\min} < h_{\max} < +\infty$. Under these specifications, we propose to solve (1) where

$$ (\forall \mathbf{x} = (\mathbf{z}, \mathbf{h}) \in \mathbb{R}^{P+L}) \qquad F(\mathbf{x}) = \frac{1}{2} \|\mathbf{h} * \mathbf{z} - \mathbf{y}\|^2 + \lambda \text{SOOT}(\mathbf{z}) + \frac{\rho}{2} d_{[z_{\min}, z_{\max}]^P}^2(\mathbf{z}) + \frac{\xi}{2} d_{[h_{\min}, h_{\max}]^L}^2(\mathbf{h}) + \frac{\zeta}{2} \|\mathbf{h}\|^2, \quad (60) $$

with $(\lambda, \rho, \xi, \zeta) > 0$ some penalization weights. Hereabove, SOOT denotes the smoothed $\ell_1$-over-$\ell_2$ sparsity promoting penalty introduced in [34], defined as

$$ (\forall \mathbf{z} \in \mathbb{R}^P) \quad \text{SOOT}(\mathbf{z}) = \log \left( \frac{\ell_{1,\alpha}(\mathbf{z}) + \beta}{\ell_{2,\eta}(\mathbf{z})} \right) \qquad (61) $$

where

$$ (\forall \mathbf{z} = (z^p)_{p \in \{1, P\}} \in \mathbb{R}^P) \quad \ell_{1,\alpha}(\mathbf{z}) = \sum_{p=1}^{P} \left( \sqrt{(z^p)^2 + \alpha^2} - \alpha \right), \quad \ell_{2,\eta}(\mathbf{z}) = \sqrt{\sum_{p=1}^{P} (z^p)^2 + \eta^2}. \quad (62) $$

Function (61) is non-convex and Lipschitz-differentiable on $\mathbb{R}^P$ (see [35, Prop.2] with $p = 1$ and $q = 2$). The scalars $(\alpha, \beta, \eta) > 0$ act as smoothing hyper-parameters so that the penalty term (61) can be viewed as a smoothed non-convex proxy of the norm ratio $\ell_1$ over $\ell_2$. SOOT penalty was shown in [34] to suitably enhance the restoration of sparse signals in the context of blind deconvolution, when compared to standard $\ell_1$-based formulation. It was later on generalized in [35, 36] to tackle signal processing tasks arising in chemistry, and hereagain showed superior results when compared to various state-of-the-art sparsity priors. Function $d_C$ denotes the Euclidean distance to a set $C$. If $C$ is non-empty and convex, function $\frac{1}{2}d_C^2$ is convex and 1-Lipschitz differentiable [37]. The two distance terms in (60) act as smoothed exterior penalty terms, weighted by $(\rho, \xi)$ favoring the fulfillment of the considered range constraints. Finally, the quadratic penalty term weighted by $\zeta$ controls the boundedness of the estimated kernel energy.

## 5.2 B2MS implementation

Let us discuss the practical application of the proposed B2MS scheme to the minimization of function (60). The latter is $C^1$ and coercive on $\mathbb{R}^{P+L}$ so Assumption 8 holds. Moreover, it satisfies the Lipschitz condition from Assumption 11. A similar analysis than in [34] leads to the fulfillment of Assumption 12. We define the family

$$ \mathcal{S} = \{[1, P], [P+1, P+L]\}, \qquad (63) $$

with the aim to build a B2MS scheme alternating between updates on the signal variable $\mathbf{z}$ and the kernel variable $\mathbf{h}$. We adopt a quasi-cyclic strategy

$$ (\forall k \in \mathbb{N}) \quad S_k = \begin{cases} [P+1, P+L] & \text{if } (k \equiv K) = 0, \\ [1, P] & \text{otherwise,} \end{cases} \qquad (64) $$

with $\equiv$ the modulo operation, and $K \ge 1$ a predefined value of the number of updates on variable $\mathbf{z}$ before processing again (and a single time) the variable $\mathbf{h}$. Definitions (63)-(64) satisfy by
construction Assumption 7. Let $H \in \mathbb{R}^{P \times P}$ the Toeplitz operator such that $h * z = Hz$, and $Z \in \mathbb{R}^{L \times L}$ the correlation operator such that $h * z = Zh$. We define

$$ (\forall \mathbf{x} = (\mathbf{z}, \mathbf{h}) \in \mathbb{R}^{P+L}) \quad \mathbf{A}^{([1,P])}(\mathbf{x}) = \mathbf{H}^{\top}\mathbf{H} + \frac{9\lambda}{8\eta^2}\mathbf{I}_P + \frac{\lambda}{\ell_{1,\alpha}(\mathbf{z}) + \beta}\mathrm{Diag}\left(\left(\left(\left(z^p\right)^2 + \alpha^2\right)^{-1/2}\right)_{p \in [1,P]}\right) + \rho\mathbf{I}_P, \quad (65) $$

and

$$ (\forall \mathbf{x} = (\mathbf{z}, \mathbf{h}) \in \mathbb{R}^{P+L}) \quad \mathbf{A}^{([P+1,P+L])}(\mathbf{x}) = \mathbf{Z}^{\top}\mathbf{Z} + (\xi + \zeta)\mathbf{I}_L. \quad (66) $$

Using [34, Prop.2], the descent lemma [37] and the block definitions (63)-(64) allows to show that the majorizing condition (11) holds for every $k \in \mathbb{N}$. Hence, Assumption 10(i) holds. Regarding the subspace choice, we adopt unless specified otherwise the memory gradient subspace from [27, 21], which reads in the block alternating case as ([38]):

$$ (\forall k \in \mathbb{N}) \quad \mathbf{D}_k = [-\nabla F^{(S_k)}(\mathbf{x}_k) | \mathbf{x}_k^{(S_k)} - \mathbf{x}_{\iota_k}^{(S_k)}] \in \mathbb{R}^{|S_k| \times 2}, \quad (67) $$

where, for every $k \in \mathbb{N}$, $\iota_k \in [0, k-1]$ is the largest index when the same block $S_{\iota_k} = S_k$ was updated (with default choice $\iota_k = 0$). This choice of subspace trivially meets Assumption 9. In a nutshell, Assumption 7 to Assumption 10(i) hold, so that, by Lemma 1, the B2MS iterates are bounded. This allows to deduce, through a straightforward analysis of (65)-(66), that Assumption 10(ii) holds. Furthermore, Assumptions 11 and 12 hold so that our convergence Theorems 1 and 2 apply.

## 5.3 Numerical results

We now present our numerical results. We rely on the same dataset and model implementation than in the SOOT Matlab toolbox<fnref n="1" />. The ground truth signal/kernel $(\bar{z}, \bar{h})$ have size $P = 784$ and $L = 41$. We set the range values $(z_{\min}, z_{\max}, h_{\min}, h_{\max})$ to the ground truth minimal and maximal values of the sought quantities. The SOOT parameters $(\lambda, \alpha, \beta, \eta)$ and the initialization $(\mathbf{z}_0, \mathbf{h}_0)$ are kept unchanged with respect to the toolbox implementation. A rough grid search is used to set the hyper-parameters $(\rho, \xi, \zeta) = (10^{-1}, 10^{-1}, 10^{-2})$ so as to reach an accurate restoration. Example of observed signal $y$, ground truth signal/kernel vectors $(\bar{z}, \bar{h})$ and estimated ones $(\tilde{z}, \tilde{h})$ are displayed in Figure 1. Running times displayed in the forthcoming sections are for a Matlab 2021a implementation on a x64 Dell Destop with 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz with 32 Go RAM.

### 5.3.1 Role of quasi-cyclic rule

The rule (64) corresponds to the standard cyclic (i.e., Gauss Seidel) rule when $K = 1$. When $K > 1$, a quasi-cyclic rule is obtained, when B2MS iterates several times on the signal before updating (once) the kernel. Our theoretical analysis encompasses such choice. To illustrate the benefit for such versatility, we display on Figure 2 the computational time required to satisfy

$$ \|\mathbf{z}_k - \tilde{\mathbf{z}}\|_1 \le 10^{-4}, \quad \text{and} \quad \|\mathbf{h}_k - \tilde{\mathbf{h}}\|_1 \le 10^{-4}, \quad (68) $$

as a function of $K$ in (64), with $(\tilde{z}, \tilde{h})$ the B2MS iterate after a very large number of iterations (typically $10^4$). One can observe that the minimal running time is not obtained for $K = 1$ (i.e., cyclic rule) but for a larger value of $K$, here around 100. This shows the advantage of adopting Assumption 7 instead of the standard cyclic update requirement. This phenomenon was already observed in the study in [34] but for another block alternating scheme. The setting $K = 100$ is retained for our next experiments.

<footnote n="1">¹ https://www.mathworks.com/matlabcentral/fileexchange/50481-soot-l1-l2-norm-ratio-sparse-blind-deconvolution</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: Observed signal $y$ (top). Ground truth (black continuous line) and restored (blue dashed line) signal (middle) and kernel (bottom). Reconstruction errors $\|\bar{z} - \tilde{z}\|_1 = 3.4 \times 10^{-3}$ and $\|\bar{h} - \tilde{h}\|_1 = 1.7 \times 10^{-2}$.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Computational time in seconds required for B2MS iterates to satisfy stopping criterion (68) as a function of $K$.</figcaption></figure>

### 5.3.2 Ablation study on B2MS

In order to assess the role of both subspace and MM acceleration in B2MS, we perform an ablation study. To that aim, we implement three ablated versions of B2MS, where we removed either one or both aforementioned features. Namely, we can remove subspace acceleration (B2MS-NoSub) by simply setting

$$ (\forall k \in \mathbb{N}) \quad D_k = -\nabla F^{(S_k)}(x_k) \in \mathbb{R}^{|S_k|}. \qquad (69) $$
<figure><img src="image_4.png" /><figcaption>Fig. 3: Evolution of the gradient norm of $F$ (left), of the estimation error on the signal (middle) and of the estimation error on the kernel (right) along time in seconds for B2MS and its ablated versions. B2MS-NoPrec-NoSub and B2MS-NoPrec plots are almost superimposed.</figcaption></figure>

We can also remove the effect of the MM preconditioner (B2MS-NoPrec) by setting, for every $x = (z, h) \in \mathbb{R}^{P+L}$, $\mathbf{A}(\llbracket 1, P \rrbracket)(\mathbf{x}) = B(h)\mathbf{I}_P$ and $\mathbf{A}(\llbracket P+1, P+L \rrbracket)(\mathbf{x}) = B(z)\mathbf{I}_L$, with $(B(h), B(z)) \in ]0, +\infty]^2$ some upper bounds on the spectra of (65)-(66). For every $x = (z, h) \in \mathbb{R}^{P+L}$, a straightforward analysis leads to

$$ (\forall h \in \mathbb{R}^L) \quad B(h) = \|\|H\|\|^2 + \frac{9\lambda}{8\eta^2} + \frac{\lambda}{\alpha\beta} + \rho, \quad (70) $$

$$ (\forall z \in \mathbb{R}^P) \quad B(z) = \|\|Z\|\|^2 + \xi + \zeta, \quad (71) $$

with $\|\cdot\|$ the spectral norm. We display in Figure 3 the evolution of the gradient norm and the estimation error along time for the four tested methods. A first observation is that the methods not using the MM preconditioner (i.e., B2MS-NoPrec, B2MS-NoPrec-NoSub) exhibit very slow convergence, in comparison with the two others. This shows the crucial role of the MM acceleration technique, especially in this example when the bounds (71) reach very high values (typically of the order of $10^8$). As an additional remark, note that (71) requires to recompute, at each iteration, spectral norms of large operators which is cumbersome. Second, using the memory gradient subspace instead of a basic gradient descent search improves the convergence speed of B2MS, as can be seen when comparing B2MS and B2MS-NoSub plots. In a nutshell, both MM preconditioning and subspace catalyzers are essential in this problem.

### 5.3.3 Comparison with state-of-the-art

We conclude our analysis by comparing B2MS with several non alternating minimization solvers from the state-of-the-art publicly available on the internet. Namely, we ran the CG-DESCENT<fnref n="2" /> solver, based on a conjugate gradient (CG) approach as described in [39]. We also ran both quasi-Newton LBFGS [3] and CG algorithms available on the minFunc<fnref n="3" /> solver from [40]. Figure 4 shows the convergence plots in terms of gradient norm and restoration error. The benchmark methods are implemented in C Mex files. For fair comparison, we thus only display the criteria evolution as a function of iteration number (which is equals, for all methods, to the number of gradient evaluations). One can observe the fast convergence of B2MS in all plots. In particular, B2MS iterates do converge to a stationary point canceling the gradient of the cost function, which does not seem to be the case for the competitors (see Fig. 4(left)). Note that, up to our knowledge, neither CG nor LBFGS possess any theoretical guarantees on the convergence of their iterates, in this example, due to the non-convexity of $F$, which might explain such behavior. CG-DESCENT exhibits great performance, in terms of estimation errors. In contrast, both minFunc solvers lead to solutions with higher estimation error (see Fig. 4(middle-right)). This shows again the advantage of the proposed scheme which benefits from sounded convergence and good practical behavior.

## 6 Conclusion

This work introduces a block alternating MM subspace algorithm and provides its convergence analysis in the non-convex case. Numerical experiments illustrate the performance of the proposed

<footnote n="2">² https://people.clas.ufl.edu/hager/software/</footnote>

<footnote n="3">³ https://www.cs.ubc.ca/~schmidtm/Software/minFunc.html</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 4: Evolution of the gradient norm of F (left), of the estimation error on the signal (middle) and of the estimation error on the kernel (right) along time in seconds for B2MS and its competitors.</figcaption></figure>

method on a practical problem of blind signal restoration. When combined with a memory gradient subspace (see, for e.g., [28]), the proposed method can be viewed as a convergent preconditioned block alternating non linear conjugate gradient algorithm for non-convex large scale optimization. Future work will be dedicated to building a distributed implementation for B2MS, for instance by adopting an asynchronous approach [17] where block updates are spread among core machines with possible update delay.

## Declarations

*Funding:* This research work received funding support from the European Research Council Starting Grant MAJORIS ERC-2019-STG-850925.

*Competing interests:* The authors have no relevant financial or non-financial interests to disclose.

## References

1. K. Kurdyka, On gradients of functions definable in o-minimal structures, in: Annales de l'institut Fourier, Vol. 48, 1998, pp. 769-783.

2. J. Bolte, A. Daniilidis, O. Ley, L. Mazet, Characterizations of Łojasiewicz inequalities and applications, arXiv preprint arXiv:0802.0826 (2008).

3. D. C. Liu, J. Nocedal, On the limited memory BFGS method for large scale optimization, Mathematical programming 45 (1) (1989) 503-528.

4. R. Fletcher, C. M. Reeves, Function minimization by conjugate gradients, The Computer Journal 7 (2) (1964) 149-154.

5. Y.-X. Yuan, Subspace methods for large scale nonlinear equations and nonlinear least squares, Optimization and Engineering 10 (2) (2008) 207-218.

6. A. Wald, T. Schuster, Sequential subspace optimization for nonlinear inverse problems, Journal of Inverse and Ill-posed Problems 25 (1) (2017) 99-117.

7. S. Bonettini, F. Porta, M. Prato, S. Rebegoldi, V. Ruggiero, L. Zanni, Recent Advances in Variable Metric First-Order Methods, Springer International Publishing, Cham, 2019, pp. 1-31.

8. P. Frankel, G. Garrigos, J. Peypouquet, Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates, Journal of Optimization Theory and Applications 165 (3) (2015) 874-900.

9. J. Bolte, S. Sabach, M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming 146 (1-2) (2014) 459-494.

10. Y. Sun, P. Babu, D. P. Palomar, Majorization-minimization algorithms in signal processing, communications, and machine learning, IEEE Transactions on Signal Processing 65 (3) (Aug. 2016).

11. Z. Zhang, J. T. Kwok, D.-Y. Yeung, Surrogate maximization/minimization algorithms and extensions, Machine Learning 69 (2007) 1-33.

12. M. C. Robini, Y. Zhu, Generic half-quadratic optimization for image reconstruction, SIAM Journal on Imaging Sciences 8 (3) (2015) 1752-1797.

13. M. Allain, J. Idier, Y. Goussard, On global and local convergence of half-quadratic algorithms, IEEE Transactions on Image Processing 15 (5) (2006) 1130-1142.

14. E. Chouzenoux, J.-C. Pesquet, A. Repetti, Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function, Journal of Optimization Theory and Applications 162 (1) (2014) 107-132.

15. E. Chouzenoux, J.-C. Pesquet, A. Repetti, A block coordinate variable metric forward-backward algorithm, Journal of Global Optimization 66 (3) (2016) 457-485.

16. M. Hong, M. Razaviyayn, Z.-Q. Luo, J.-S. Pang, A unified algorithmic framework for block-structured optimization involving big data: With applications in machine learning and signal processing, IEEE Signal Processing Magazine 33 (1) (2015) 57-77.

17. G. Scutari, Y. Sun, Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization, Springer Verlag Series, C.I.M.E Lecture Notes in Mathematics, 2018.
18. M. W. Jacobson, J. A. Fessler, An expanded theoretical treatment of iteration-dependent majorize-minimize algorithms, IEEE Transactions on Image Processing 16 (10) (2007) 2411-2422.

19. S. Sotthivirat, J. A. Fessler, Image recovery using partitioned-separable paraboloidal surrogate coordinate ascent algorithms, IEEE Transactions on Signal Processing 11 (3) (2002) 306-317.

20. E. Chouzenoux, J. Idier, S. Moussaoui, A majorize-minimize strategy for subspace optimization applied to image restoration, IEEE Transactions on Image Processing 20 (6) (2010) 1517-1528.

21. E. Chouzenoux, A. Jezierska, J.-C. Pesquet, H. Talbot, A majorize-minimize subspace approach for $ℓ_2-ℓ_0$ image regularization, SIAM Journal on Imaging Sciences 6 (1) (2013) 563-591.

22. E. Chouzenoux, J.-C. Pesquet, Convergence rate analysis of the majorize-minimize subspace algorithm, IEEE Signal Processing Letters 23 (9) (2016) 1284-1288.

23. E. Chouzenoux, S. Martin, J.-C. Pesquet, A local MM subspace method for solving constrained variational problems in image recovery, Journal of Mathematical Imaging and Vision(to appear) (2022).

24. H. Attouch, J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Mathematical Programming 116 (1) (2009) 5-16.

25. M. Razaviyayn, M. Hong, Z.-Q. Luo, A unified convergence analysis of block successive minimization methods for nonsmooth optimization, SIAM Journal on Optimization 23 (2) (2013) 1126-1153.

26. D. P. Bertsekas, Nonlinear programming, Journal of the Operational Research Society 48 (3) (1997) 334-334.

27. A. Miele, J. Cantrell, Study on a memory gradient method for the minimization of functions, Journal of Optimization Theory and Applications 3 (6) (1969) 459-470.

28. A. Florescu, E. Chouzenoux, J.-C. Pesquet, P. Ciuciu, S. Ciochina, A majorize-minimize memory gradient method for complex-valued inverse problems, Signal Processing 103 (2014) 285-295.

29. Relation between the memory gradient method and the Fletcher-Reeves method, Journal of Optimization Theory and Applications 4 (1) (1969) 67-71.

30. R. I. Boţ, E. R. Csetnek, An inertial tseng's type proximal algorithm for nonsmooth and nonconvex optimization problems, Journal of Optimization Theory and Applications 171 (2) (2016) 600-616.

31. D. Davis, The asynchronous PALM algorithm for nonsmooth nonconvex problems, arXiv preprint arXiv:1604.00526 (2016).

32. J. Nocedal, S. Wright, Numerical optimization, Springer Science & Business Media, 2006.

33. S. Haykin, Blind Deconvolution, 1994.

34. A. Repetti, M. Pham, L. Duval, E. Chouzenoux, J.-C. Pesquet, Euclid in a Taxicab: Sparse blind deconvolution with smoothed l1/l2 regularization, IEEE Signal Processing Letters 22 (5) (2015) pages 539-543.

35. A. Cherni, E. Chouzenoux, L. Duval, J.-C. Pesquet, SPOQ lp-over-lq regularization for sparse signal recovery applied to mass spectrometry, IEEE Transactions on Signal Processing 68 (2020) 6070-6084.

36. P. Zheng, E. Chouzenoux, L. Duval, PENDANTSS:penalized norm-ratios disentangling additive noise, trend and sparse spikes, Tech. rep., https://arxiv.org/abs/2301.01514 (2023).

37. H. Bauschke, P. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd Edition, Springer, New York, 2017.

38. S. Cadoni, E. Chouzenoux, J.-C. Pesquet, C. Chaux, A block parallel majorize-minimize memory gradient algorithm, in: 23rd IEEE Int. Conf. Image Process. (ICIP 2016), Phoenix, AZ, 2016, pp. 3194-3198.

39. W. H. Hager, H. Zhang, Algorithm 851: CG DESCENT, a conjugate gradient method with guaranteed descent, ACM Transactions on Mathematical Software 32 (1) (2006) 113-137.

40. M. Schmidt, minFunc: unconstrained differentiable multivariate optimization in Matlab, Tech. rep. (2005).