betaFeedback

WorksEngineering

Efficient SCA Algorithms for Sparse Bayesian Learning

Abstract

Type-II sparse Bayesian learning (SBL) for the multiple measurement vector model recovers a sparse signal power vector by minimizing the marginal negative log-likelihood via the expectation-maximization (EM) algorithm, referred to as M-SBL. We revisit the covariance learning (CL) problem and develop three parallel first-order algorithms within the successive convex approximation (SCA) framework. CL-SCA minimizes per-coordinate surrogates formed by partially linearizing the log-determinant term, while CL-FP uses a damped projected fixed-point iteration derived from stationarity conditions. Both methods have closed-form updates. We prove that the fixed points of both update maps are exactly the KKT points of the CL problem, that each update direction satisfies a quantitative descent inequality, that the damped iterates achieve sufficient decrease with an O(T−1/2)\mathcal{O}(T^{-1/2}) best-iterate stationarity rate, and we derive a backtracking rule that retains this rate without step-size tuning. If damping factors are bounded away from zero, the residual vanishes along the whole sequence and every limit point is a KKT point. Local analysis motivates CL-Hyb, which combines CL-SCA and CL-FP. Experiments on device activity detection in massive random access show that CL-Hyb-bt matches the best CL solvers' accuracy at a fraction of the runtime and is over an order of magnitude faster than EM.

Introduction

In the multiple measurements vector (MMV) [1] model, the measurement vectors yt∈CM\mathbf{y}_t \in\mathbb{C}^{M} follow the generative model yt=Axt+et\mathbf{y}_t = \mathbf{A}\mathbf{x}_t + \mathbf{e}_t, t=1,…,Qt = 1,\ldots,Q, where A=(a1⋯aN)∈CM×N\mathbf{A} = (\mathbf{a}_1 \cdots\mathbf{a}_N) \in\mathbb{C}^{M \times N} is a fixed (known) overcomplete matrix (N>MN > M) and et∈CM\mathbf{e}_t \in\mathbb{C}^{M} is an unobserved zero mean white noise random vector, i.e., cov⁡(et)=σ2I\operatorname{cov}(\mathbf{e}_t) = \sigma^2\mathbf{I}. Matrix A\mathbf{A} is called the dictionary or measurement matrix, and its column vectors ai\mathbf{a}_i are referred to as atoms. The unobserved random signal vectors xt=(x1t,…,xNt)T\mathbf{x}_t = (x_{1t},\ldots,x_{Nt})^{\mathsf{T}}, t=1,…,Qt = 1,\ldots,Q are assumed to be jointly sparse, i.e., most of their elements are zero, and all xt\mathbf{x}_t-s share the same support. Letting Y=(y1⋯yQ)∈CM×Q\mathbf{Y} = (\mathbf{y}_1 \cdots\mathbf{y}_Q) \in\mathbb{C}^{M \times Q} denote the matrix of measurement vectors, we can write the model in matrix form as

Y=AX+E,(1)\mathbf{Y} = \mathbf{A}\mathbf{X} + \mathbf{E}, \tag*{(1)}

where matrices X=(xnt)∈CN×Q\mathbf{X} = (x_{nt}) \in\mathbb{C}^{N \times Q} and E=(emt)∈CM×Q\mathbf{E} = (e_{mt}) \in\mathbb{C}^{M \times Q} contain the signal and noise vectors as columns, respectively. Given KK signals, the key assumption underlying the MMV model is that the signal matrix X\mathbf{X} is KK-rowsparse, i.e., at most KK rows of X\mathbf{X} contain non-zero entries. The row support of X∈CN×Q\mathbf{X} \in\mathbb{C}^{N \times Q} is the index set of rows containing non-zero elements:

M=supp⁡(X)={n∈[N]:xnt≠0 for some t∈[Q]}\mathcal{M} = \operatorname{supp}(\mathbf{X}) = \{n \in[N] : x_{nt} \ne0 \text{ for some } t \in[Q]\}

where [N]={1,…,N}[N] = \{1,\ldots,N\}. Since X\mathbf{X} is KK-rowsparse, i.e., ∣supp⁡(X)∣=K|\operatorname{supp}(\mathbf{X})| = K, joint estimation of xt\mathbf{x}_t-s using (1) can lead to both to computational advantages and increased reconstruction accuracy [1, 2, 3, 4, 5, 6]. In sparse signal recovery (SSR) problems, the goal is identifying the support M\mathcal{M} and possibly X\mathbf{X}, given only the data Y\mathbf{Y}, the dictionary A\mathbf{A}, and possibly the sparsity level KK.

In Sparse Bayesian Learning (SBL) [7], [8], the signal vectors xt\mathbf{x}_t-s are modeled as i.i.d. circular Gaussian random vectors with independent elements and zero mean. Additionally, xt\mathbf{x}_t-s are assumed to be statistically independent of the noise vectors et\mathbf{e}_t-s. The noise vectors are assumed to be i.i.d. Gaussian with et∼CNM(0,σ2I)\mathbf{e}_t \sim\mathcal{CN}_{M}(\mathbf{0},\sigma^2\mathbf{I}). This implies that yt∼CNM(0,Σ)\mathbf{y}_t \sim\mathcal{CN}_{M}(\mathbf{0},\mathbf{\Sigma}), where the positive definite Hermitian (PDH) M×MM \times M covariance matrix Σ=cov⁡(yt)\mathbf{\Sigma} = \operatorname{cov}(\mathbf{y}_t) has the form

Σ=AΓAH+σ2I=∑n=1NγnananH+σ2I(2)\mathbf{\Sigma} = \mathbf{A}\mathbf{\Gamma}\mathbf{A}^{\mathsf{H}} + \sigma^2\mathbf{I} = \sum_{n=1}^{N}\gamma_n\mathbf{a}_n\mathbf{a}_n^{\mathsf{H}} + \sigma^2\mathbf{I} \tag*{(2)}

where the signal covariance matrix Γ=cov⁡(xt)=diag⁡(γ)\mathbf{\Gamma} = \operatorname{cov}(\mathbf{x}_t) = \operatorname{diag}(\boldsymbol{\gamma}) is a diagonal matrix and γ∈R≥0N\boldsymbol{\gamma} \in\mathbb{R}_{\geq0}^{N} is a vector of signal powers with only KK non-zero elements, i.e., M=supp⁡(X)=supp⁡(γ)\mathcal{M} = \operatorname{supp}(\mathbf{X}) = \operatorname{supp}(\boldsymbol{\gamma}). We assume σ2>0\sigma^2 > 0 to be known. In many applications, the noise variance σ2\sigma^2 can be accurately estimated a priori and can thus be considered as a known constant.

Covariance learning (CL)-based support recovery algorithms can be constructed by minimizing the negative log-likelihood function (LLF) of the data Y\mathbf{Y}. We let

ϕ(⋅;μ,Σ)=∣Σ∣−1exp⁡(−[⋅−μ]HΣ−1[⋅−μ])\phi(\cdot;\boldsymbol{\mu},\mathbf{\Sigma}) = |\mathbf{\Sigma}|^{-1}\exp\left(-[\cdot-\boldsymbol{\mu}]^{\mathsf{H}}\mathbf{\Sigma}^{-1}[\cdot-\boldsymbol{\mu}]\right)

denote the probability density function (up to an irrelevant normalizing constant) of the multivariate circular Gaussian distribution CNM(μ,Σ)\mathcal{CN}_{M}(\boldsymbol{\mu},\mathbf{\Sigma}) with mean vector μ\boldsymbol{\mu} and covariance matrix Σ\mathbf{\Sigma}. Here, ∣⋅∣|\cdot| denotes the matrix determinant. Then, the scaled negative LLF of the data Y\mathbf{Y} is

ℓ(γ)=−1Qlog⁡(∏t=1Qϕ(yt;0,Σ))=g(γ)+f(γ),(3)\ell(\boldsymbol{\gamma}) = -\frac{1}{Q}\log\left(\prod_{t=1}^{Q}\phi(\mathbf{y}_t;\mathbf{0},\mathbf{\Sigma})\right) = g(\boldsymbol{\gamma}) + f(\boldsymbol{\gamma}), \tag*{(3)}

where g:R≥0N→Rg:\mathbb{R}_{\geq0}^{N}\to\mathbb{R} is a convex continuously differentiable function in R≥0N\mathbb{R}_{\geq0}^{N} and f:R≥0N→Rf:\mathbb{R}_{\geq0}^{N}\to\mathbb{R} is a concave continuously differentiable function, defined as,

g(γ)=tr⁡((Adiag⁡(γ)AH+σ2I)−1S)(4)g(\boldsymbol{\gamma})=\operatorname{tr}\left(\left(\mathbf{A}\operatorname{diag}(\boldsymbol{\gamma})\mathbf{A}^{\mathrm{H}}+\sigma^{2}\mathbf{I}\right)^{-1}\mathbf{S}\right) \tag*{(4)}
f(γ)=log⁡∣Adiag⁡(γ)AH+σ2I∣,(5)f(\boldsymbol{\gamma})=\log\left|\mathbf{A}\operatorname{diag}(\boldsymbol{\gamma})\mathbf{A}^{\mathrm{H}}+\sigma^{2}\mathbf{I}\right|, \tag*{(5)}

where tr⁡(⋅)\operatorname{tr}(\cdot) denotes the matrix trace, and S=1Q∑t=1QytytH\mathbf{S}=\frac{1}{Q}\sum_{t=1}^{Q}\mathbf{y}_{t}\mathbf{y}_{t}^{\mathrm{H}} is the sample covariance matrix (SCM) of the data. We then study the nonconvex optimization problem

minimize⁡γ≥0ℓ(γ)(6)\underset{\boldsymbol{\gamma}\geq0}{\operatorname{minimize}}\quad\ell(\boldsymbol{\gamma}) \tag*{(6)}

and derive efficient algorithms using the SCA framework [9].

Relevant Prior Work

A wide range of methods have been developed for the MMV problem in (1). Convex relaxation methods treat X\mathbf{X} as deterministic and promote row sparsity through ℓ2,1\ell_{2,1}-type penalties [3]. Greedy methods, such as simultaneous orthogonal matching pursuit (SOMP) [2], recover the common support sequentially at low computational complexity. Another class of deterministic row-sparse recovery methods relies on iterative reweighting or non-convex sparsity-promoting penalties, with M-FOCUSS [10] as a representative example. When the source and noise vectors are modeled as independent random Gaussian vectors, the resulting marginal likelihood leads to Type-II objective in (3) as in SBL [7, 8, 11].

SBL is the most prominent Type-II method, introduced for the single measurement vector (SMV) setting in [7, 8] and extended to MMV as M-SBL [11]. The traditional expectation-maximization (EM) solver for M-SBL is known to converge slowly, especially in large-scale problems. In addition, with strictly positive initialization, EM’s multiplicative updates do not produce exact zeros. These drawbacks have motivated faster or more flexible Type-II variants, including MM-based covariance learning algorithm (CLMM) [12], generalized approximate message passing (GAMP)-based implementations with linear per-iteration complexity [13], variational methods for jointly learning signal powers and full-structure noise covariance matrices [14].

Greedy methods are attractive for their simplicity and low complexity. The greedy principle has recently been adopted in the covariance domain: covariance learning matching pursuit (CL-MP) [15], independently developed as light-weight sequential SBL (LWS-SBL) [16], sequentially selects atoms by optimizing a Type-II (sequential) likelihood and stops after KK iterations. Although effective at low sparsity levels, greedy methods can degrade at higher sparsity levels due to accumulated support-selection errors.

Covariance learning has also emerged as a powerful tool for activity detection (AD) in grant-free random access (GFRA), a key massive machine-type communication (mMTC) application [17]. Due to sporadic traffic, the received pilots follow an MMV model with a row-sparse channel matrix, making AD a support-recovery problem. Although many works use compressive sensing (CS) formulations with AMP-type solvers [18, 19], Type-II/CL methods can detect more active devices with the same pilot length when sufficiently many base station (BS) antennas are available [20]. Here the CL variables represent device powers, namely activity indicators scaled by large-scale fading and transmit powers. Since EM-based M-SBL, coordinate-wise optimization (CWO) [20], and CL-MP/LWS-SBL [15, 16] optimize the same Type-II likelihood, they provide natural benchmarks for the proposed algorithms. Further related developments include joint activity and data detection [21], phase-transition analysis [22], robust CL-based AD [23], and SCA-based ML/MAP detectors [24].

Contributions

Our contributions are summarized as follows.

  1. We propose a parallel SCA algorithm (CL-SCA) for covariance learning that preserves the convex part of the surrogate objective and linearizes only the concave part. This yields NN convex per-coordinate subproblems whose exact minimizers are given in closed-form at each iteration (Theorem 1) and can be updated in parallel. The per-iteration computational complexity is O(NM2)\mathcal{O}(NM^{2}), matching one cycle of CWO [20 Alg. 1], and one iteration of CL-MP [15 Alg. 1], M-SBL [11] or CLMM [12].

  1. We derive a fixed-point form of the KKT conditions (Lemma 1) and derive CL-FP algorithm as a damped fixed-point iteration (obtained earlier as PSCA-ML-UD [24] from a different surrogate) and give the first rate and step-size analysis. Its per-iteration cost equals that of CL-SCA.

  1. We provide a rigorous convergence analysis showing that the fixed points of both the CL-SCA and CL-FP update maps coincide exactly with the KKT points of the CL problem. In addition, each update direction satisfies a quantitative descent inequality, and the damped iterates achieve sufficient decrease and an O(T−1/2)\mathcal{O}(T^{-1/2}) best-iterate stationarity rate after TT iterations. Moreover, when the damping factors are bounded away from zero, the residual vanishes along the entire sequence, and every limit point is a KKT point (cf. Theorems 2 and 3).

  1. We then propose a hybrid algorithm (CL-Hyb) exploiting the benefits of both mappings. Local analysis shows that CL-SCA allows twice the step size of CL-FP, whereas CL-FP is faster near stationarity. This motivates CL-Hyb, which uses CL-SCA for the first few iterations and then switches to CL-FP. Since both updates satisfy the same sufficient-decrease inequality with the same constants, the convergence guarantees carry over to the hybrid scheme.

  1. We provide a unified fixed-point view of CL-SCA, CL-FP, CLMM, and EM as updates γn↦γn+(multiplier)×(residual)\gamma_n\mapsto\gamma_n+(\text{multiplier})\times(\text{residual}) (Table I), showing that the fixed points of the first three are exactly the KKT points, whereas EM’s vanishing multiplier at γn=0\gamma_n=0 creates spurious fixed points on the boundary.

  1. We apply the proposed methods to joint activity detection and channel estimation (JADCE) in GFRA and compare them with M-SBL [11], CLMM [12], CWO [20], and CL-MP [15]. CL-Hyb with backtracking (CL-Hyb-bt) attains the missed-detection performance of CWO at roughly half its runtime and is more than an order of magnitude faster than M-SBL (cf. Figure 3). The objective-gap analysis in Figure 1 further shows

Convergence plots for representative methods

Figure 1. Convergence for M=20M=20, K=30K=30, Q=50Q=50, N=300N=300 (20 MC runs) Top: median objective gap ℓ(γk)−ℓ⋆\ell(\boldsymbol{\gamma}^{k})-\ell^{\star}. Bottom: normalized running-minimum loss for representative runs, drawn until reaching the target ℓref\ell_{\mathrm{ref}} (the loss after ten CWO cycles) or 250 iterations. The legend gives the average iterations and time-to-target. “>>” marks methods that did not reach it. CWO required 8.4 ms for its ten cycles. For better visualisation we truncate range of kk (x-axis) to k≤60k\leq60 at the bottom panel.

Running time versus the number of active devices $K$ for $M=20$ (a) and $M=50$ (b)

Figure 3. Running time versus the number of active devices KK for M=20M = 20 (a) and M=50M = 50 (b), averaged over Q∈{20,30,…,80}Q \in\{20,30,\ldots,80\} and 1000 MC trials per QQ. All optimization-based methods use the stopping criterion (27) with δ=10−2\delta= 10^{-2}.

that CL-Hyb-bt converges fastest among the optimization-based methods, in both iterations and runtime.

For reproducible research, code for all proposed and benchmark methods is available at https://github.com/esollila/CL-SCA. Preliminary results appeared in [12], [25].

Organization and Notation

The paper is structured as follows. Section II gives the 1st-order and fixed-point characterizations of the CL problem and relates them to CWO. Section III reviews M-SBL and its EM solver. Section IV develops the proposed CL-SCA algorithm and its stationarity-rate analysis, and discusses step-size selection, including a backtracking rule that attains the O(T−1/2)\mathcal{O}(T^{-1/2}) rate without step-size tuning. § 5 develops CL-FP and its rate analysis, and casts CL-SCA, CL-FP, CLMM, and EM in a unified fixed-point view in subsection V-B. The local convergence analysis in subsection V-C then motivates the third algorithm, CL-Hyb. Section VI applies the methods to JADCE in GFRA, and Section VII concludes the paper.

We use bold lowercase and uppercase letters for vectors and matrices, respectively. For a matrix X\mathbf{X}, XH\mathbf{X}^{\mathrm{H}}, tr⁡(X)\operatorname{tr}(\mathbf{X}), ∣X∣\lvert\mathbf{X}\rvert, and ∥X∥2\lVert\mathbf{X}\rVert_{2} denote its Hermitian transpose, trace, determinant, and spectral norm. The entry in the mmth row and nnth column of X\mathbf{X} is denoted by [X]mn[\mathbf{X}]_{mn}, and its largest eigenvalue is denoted by λmax⁡(X)\lambda_{\max}(\mathbf{X}). The Euclidean norm of a vector x\mathbf{x} is denoted by ∥x∥2\lVert\mathbf{x}\rVert_{2}, and [x]+[\mathbf{x}]_{+} denotes the element-wise projection of x\mathbf{x} onto the nonnegative orthant. The symbol ⊙\odot denotes the Hadamard (element-wise) product. 1{⋅}\mathbf{1}\{\cdot\} denotes the indicator function.

First order characterization of the problem

Write

Σ\n=∑j≠nγjajajH+σ2I=Σ−γnananH(7)\boldsymbol{\Sigma}_{\backslash n}=\sum_{j\ne n}\gamma_j\mathbf{a}_j\mathbf{a}_j^{\mathrm{H}}+\sigma^2\mathbf{I}=\boldsymbol{\Sigma}-\gamma_n\mathbf{a}_n\mathbf{a}_n^{\mathrm{H}} \tag*{(7)}

as the covariance matrix of yt-s\mathbf{y}_{t\text{-s}} when the contribution from the nnth signal is removed. Define

cn=Σ\n−1anandbn=Σ−1an,(8)\mathbf{c}_n=\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{a}_n\quad\text{and}\quad\mathbf{b}_n=\boldsymbol{\Sigma}^{-1}\mathbf{a}_n, \tag*{(8)}

for n=1,…,Nn=1,\ldots,N. Note that cn≡cn(γ)\mathbf{c}_n\equiv\mathbf{c}_n(\boldsymbol{\gamma}) and bn≡bn(γ)\mathbf{b}_n\equiv\mathbf{b}_n(\boldsymbol{\gamma}) depend on γ\boldsymbol{\gamma} through Σ\boldsymbol{\Sigma} but to keep notations short, we have dropped this notation. Write ∇n=∂∂γn\nabla_n=\frac{\partial}{\partial\gamma_n} as a shorthand notation. Then the coordinate derivatives dn(γ)=∇nf(γ)d_n(\boldsymbol{\gamma})=\nabla_n f(\boldsymbol{\gamma}) and en(γ)=−∇ng(γ)e_n(\boldsymbol{\gamma})=-\nabla_n g(\boldsymbol{\gamma}) of functions f(γ)f(\boldsymbol{\gamma}) and g(γ)g(\boldsymbol{\gamma}) are

dn(γ)=∇nlog⁡∣Σ∣=anHΣ−1an=anHbn(9)d_n(\boldsymbol{\gamma})=\nabla_n\log\lvert\boldsymbol{\Sigma}\rvert=\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}^{-1}\mathbf{a}_n=\mathbf{a}_n^{\mathrm{H}}\mathbf{b}_n \tag*{(9)}
en(γ)=−∇ntr⁡(Σ−1S)=anHΣ−1SΣ−1an=bnHSbn(10)e_n(\boldsymbol{\gamma})=-\nabla_n\operatorname{tr}(\boldsymbol{\Sigma}^{-1}\mathbf{S})=\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}^{-1}\mathbf{S}\boldsymbol{\Sigma}^{-1}\mathbf{a}_n=\mathbf{b}_n^{\mathrm{H}}\mathbf{S}\mathbf{b}_n \tag*{(10)}

and note that dn(γ)>0d_n(\boldsymbol{\gamma})>0 as Σ≻0\boldsymbol{\Sigma}\succ0 and en(γ)≥0e_n(\boldsymbol{\gamma})\ge0 for all γ\boldsymbol{\gamma}. For notational simplicity we often write dn≡dn(γ)d_n\equiv d_n(\boldsymbol{\gamma}) and en≡en(γ)e_n\equiv e_n(\boldsymbol{\gamma}), dropping the dependency of γ\boldsymbol{\gamma}. With the above definitions, the nnth coordinate function of the gradient of ℓ(γ)=f(γ)+g(γ)\ell(\boldsymbol{\gamma})=f(\boldsymbol{\gamma})+g(\boldsymbol{\gamma}) can be expressed as:

∇nℓ(γ)=anHbn−bnHSbn=dn−en(11)\nabla_n\ell(\boldsymbol{\gamma})=\mathbf{a}_n^{\mathrm{H}}\mathbf{b}_n-\mathbf{b}_n^{\mathrm{H}}\mathbf{S}\mathbf{b}_n=d_n-e_n \tag*{(11)}

The KKT condition for the constrained case γ≥0\boldsymbol{\gamma}\ge0 is

∇nℓ(γ){=0,if γn>0,≥0,if γn=0.(12)\nabla_n\ell(\boldsymbol{\gamma})\begin{cases} =0, & \text{if }\gamma_n>0,\\ \ge0, & \text{if }\gamma_n=0. \end{cases} \tag*{(12)}

Next result characterizes the solution to (6).

Lemma 1. Let γ∈R≥0N\boldsymbol{\gamma}\in\mathbb{R}_{\ge0}^{N} and let H(γ)H(\boldsymbol{\gamma}) have coordinate functions

Hn(γ)=γn+1dn(endn−1)(13)H_n(\boldsymbol{\gamma})=\gamma_n+\frac{1}{d_n}\left(\frac{e_n}{d_n}-1\right) \tag*{(13)}
=γn−∇nℓ(γ)dn2.(14)=\gamma_n-\frac{\nabla_n\ell(\boldsymbol{\gamma})}{d_n^2}. \tag*{(14)}

Then γ\boldsymbol{\gamma} satisfies the KKT conditions (12) if and only if it verifies the fixed-point equation

γ=[H(γ)]+.(15)\boldsymbol{\gamma}=[H(\boldsymbol{\gamma})]_{+}. \tag*{(15)}

In particular, every local minimizer of ℓ\ell over R≥0N\mathbb{R}_{\ge0}^{N}, and hence the minimizer γ^\widehat{\boldsymbol{\gamma}}, verifies (15), and on the support {n:γn>0}\{n:\gamma_n>0\} the projection is inactive, so γn=Hn(γ)\gamma_n=H_n(\boldsymbol{\gamma}).

Proof. See Appendix A.

The CWO algorithm is closely related with fixed point map. Namely, in cycle kk, coordinate nn is updated by minimizing

ℓCW,n(γ)=ℓ(γ1k,…,γn−1k,γ,γn+1k−1,…,γNk−1)\ell_{\mathrm{CW},n}(\boldsymbol{\gamma})=\ell(\gamma_1^k,\ldots,\gamma_{n-1}^k,\gamma,\gamma_{n+1}^{k-1},\ldots,\gamma_N^{k-1})

subject to γ≥0\boldsymbol{\gamma}\ge0. The minimizer is [26]:

γnk=arg⁡min⁡γ≥0ℓCW,n(γ)=[Hn(γ~k)]+(16)\gamma_n^k=\arg\min_{\gamma\ge0}\ell_{\mathrm{CW},n}(\gamma)=[H_n(\widetilde{\boldsymbol{\gamma}}^k)]_{+} \tag*{(16)}

where γ~k=(γ1k,…,γn−1k,γnk−1,γn+1k−1,…,γNk−1)T\widetilde{\boldsymbol{\gamma}}^k=(\gamma_1^k,\ldots,\gamma_{n-1}^k,\gamma_n^{k-1},\gamma_{n+1}^{k-1},\ldots,\gamma_N^{k-1})^{\mathsf{T}}.

M-SBL

Under the Gaussianity assumption, the posterior distribution of the sources factorizes across measurement vectors as

p(X∣Y,γ)=∏t=1Qϕ(xt;μt,Σx).p(\mathbf{X}\mid\mathbf{Y},\boldsymbol{\gamma})=\prod_{t=1}^{Q}\phi(\mathbf{x}_t;\boldsymbol{\mu}_t,\boldsymbol{\Sigma}_{x}).

The posterior depends on the conditional mean vectors μt∈CN\boldsymbol{\mu}_t\in\mathbb{C}^{N} of xt\mathbf{x}_t-s as well as their joint posterior covariance matrix, Σx∈CN×N\boldsymbol{\Sigma}_{x}\in\mathbb{C}^{N\times N}, defined by

M(γ)=E[X∣Y,γ]=(μ1 ⋯ μQ)=ΓAHΣ−1Y,\mathbf{M}(\boldsymbol{\gamma})=\mathbb{E}[\mathbf{X}\mid\mathbf{Y},\boldsymbol{\gamma}]=(\boldsymbol{\mu}_1\ \cdots\ \boldsymbol{\mu}_Q)=\mathbf{\Gamma}\mathbf{A}^{\mathrm{H}}\boldsymbol{\Sigma}^{-1}\mathbf{Y},
Σx(γ)=cov⁡(xt∣yt,γ)=Γ−ΓAHΣ−1AΓ,\boldsymbol{\Sigma}_{x}(\boldsymbol{\gamma})=\operatorname{cov}(\mathbf{x}_t\mid\mathbf{y}_t,\boldsymbol{\gamma})=\mathbf{\Gamma}-\mathbf{\Gamma}\mathbf{A}^{\mathrm{H}}\boldsymbol{\Sigma}^{-1}\mathbf{A}\mathbf{\Gamma},

where Σ\boldsymbol{\Sigma} is defined by (2). The M-SBL algorithm [11], [27] employs an empirical Bayes (Type-II) approach to estimate the posterior distribution. In the Type-II framework, rather than placing a prior on the hyperparameters γ\boldsymbol{\gamma}, one estimates them directly from the data by minimizing the marginal Type-II scaled negative LLF in (3), thereby obtaining γ^\widehat{\boldsymbol{\gamma}}. Subsequently, the posterior distribution is computed via the plug-in principle as p(X∣Y,γ^)p(\mathbf{X}\mid\mathbf{Y},\widehat{\boldsymbol{\gamma}}), and

X^=M(γ^)=Γ^AHΣ^−1Y,\widehat{\mathbf{X}}=\mathbf{M}(\widehat{\boldsymbol{\gamma}})=\widehat{\mathbf{\Gamma}}\mathbf{A}^{\mathrm{H}}\widehat{\boldsymbol{\Sigma}}^{-1}\mathbf{Y},
Σ^x=Σx(γ^)=Γ^−Γ^AHΣ^−1AΓ^,\widehat{\boldsymbol{\Sigma}}_x=\boldsymbol{\Sigma}_x(\widehat{\boldsymbol{\gamma}})=\widehat{\mathbf{\Gamma}}-\widehat{\mathbf{\Gamma}}\mathbf{A}^{\mathrm{H}}\widehat{\boldsymbol{\Sigma}}^{-1}\mathbf{A}\widehat{\mathbf{\Gamma}},

will serve as the empirical Bayes estimates of the posterior mean vectors and covariance matrix, respectively, where Γ^=diag⁡(γ^)\widehat{\mathbf{\Gamma}}=\operatorname{diag}(\widehat{\boldsymbol{\gamma}}) and Σ^=AΓ^AH+σ2I\widehat{\boldsymbol{\Sigma}}=\mathbf{A}\widehat{\mathbf{\Gamma}}\mathbf{A}^{\mathrm{H}}+\sigma^2\mathbf{I}. Algorithm 1 summarizes the generic M-SBL framework: step 1, solved by EM in [11], can use any solver of (6), such as the proposed SCA algorithms.

Algorithm 1: Generic M-SBL framework

Input: Y\mathbf{Y}, A\mathbf{A}, σ2\sigma^2, KK or γthr\gamma_{\mathrm{thr}}.

  1. Minimize ℓ(γ)\ell(\gamma) over γ≥0\gamma\ge0 to obtain γ^∈R≥0N\hat{\gamma} \in\mathbb{R}_{\ge0}^{N} using an algorithm of your choice.

  2. Compute estimate of activity indices α^=(α^1,…,α^N)T∈{0,1}N\hat{\boldsymbol{\alpha}}=(\hat{\alpha}_1,\ldots,\hat{\alpha}_N)^{\mathsf{T}}\in\{0,1\}^{N} using either the threshold rule in (19) or the KK-top rule in (20).

  3. Prune the signal power estimates as γ^←γ^⊙α^\hat{\gamma}\leftarrow\hat{\gamma}\odot\hat{\boldsymbol{\alpha}}.

  4. Compute the sparse signal matrix as X^=Γ^AHΣ^−1Y\hat{\mathbf{X}}=\hat{\boldsymbol{\Gamma}}\mathbf{A}^{\mathsf{H}}\hat{\boldsymbol{\Sigma}}^{-1}\mathbf{Y}, with Γ^=diag⁡(γ^)\hat{\boldsymbol{\Gamma}}=\operatorname{diag}(\hat{\gamma}) and Σ^=AΓ^AH+σ2I\hat{\boldsymbol{\Sigma}}=\mathbf{A}\hat{\boldsymbol{\Gamma}}\mathbf{A}^{\mathsf{H}}+\sigma^2\mathbf{I}.

Output: α^\hat{\boldsymbol{\alpha}} (or support M^=supp⁡(α^)\hat{\mathcal{M}}=\operatorname{supp}(\hat{\boldsymbol{\alpha}})), X^\hat{\mathbf{X}}, γ^\hat{\gamma}.

The EM-algorithm

In step 1 of Algorithm 1, the M-SBL constructs an EM algorithm to minimize ℓ(γ)\ell(\gamma) by treating (yt,xt)(\mathbf{y}_t,\mathbf{x}_t), t=1,…,Qt=1,\ldots,Q, as the complete data. It is well-known that the EM algorithm suffers from slow convergence, making M-SBL impractical for applications where NN is large.

To highlight the analogy with the SCA algorithms developed in this work, we combine the E- and M-steps of M-SBL into a concise efficient form that avoids computing the posterior mean and covariance estimates at each iteration. Specifically, let γk\gamma^k denote the value of γ\gamma at kthk^{\mathrm{th}} iteration, and write

dnk=dn(γk)=anHbnkandenk=en(γk)=[bnk]HSbnk(17)d_n^k=d_n(\gamma^k)=\mathbf{a}_n^{\mathsf{H}}\mathbf{b}_n^k\quad\text{and}\quad e_n^k=e_n(\gamma^k)=[\mathbf{b}_n^k]^{\mathsf{H}}\mathbf{S}\mathbf{b}_n^k \tag*{(17)}

i.e., as values the coordinate derivative functions defined in (9) and (10) evaluated at γ=γk\gamma=\gamma^k, respectively. Also, write Mk=M(γk)\mathbf{M}^k=\mathbf{M}(\gamma^k) and Σxk=Σx(γk)\boldsymbol{\Sigma}_x^k=\boldsymbol{\Sigma}_x(\gamma^k) for the values of the posterior mean and covariance matrix at γ=γk\gamma=\gamma^k. With the above definitions in mind, we can write [Σxk]nn=γnk−(γnk)2dnk[\boldsymbol{\Sigma}_x^k]_{nn}=\gamma_n^k-(\gamma_n^k)^2d_n^k and [Q−1Mk(Mk)H]nn=(γnk)2enk[\mathbf{Q}^{-1}\mathbf{M}^k(\mathbf{M}^k)^{\mathsf{H}}]_{nn}=(\gamma_n^k)^2e_n^k, and the M-step [11 eq. (18)] can be expressed in a simpler form as

γnk+1=γnk−(γnk)2(dnk−enk)=γnk(1−γnk(dnk−enk)).(18)\gamma_n^{k+1}=\gamma_n^k-(\gamma_n^k)^2(d_n^k-e_n^k)=\gamma_n^k(1-\gamma_n^k(d_n^k-e_n^k)). \tag*{(18)}

Thus, the M-SBL algorithm consists of iterating (18) until convergence. Note that due to multiplicative form of the update, one needs to start from some strictly positive initial point (e.g., γ0=1\gamma^0=1 is proposed in [11]). Since ∇nℓ(γk)=dnk−enk\nabla_n\ell(\gamma^k)=d_n^k-e_n^k by (11), we can interpret (18) as a gradient descent method with coordinate-wise adaptive step size (γnk)2(\gamma_n^k)^2.

Apart from its slow convergence, another limitation of the EM iterations (18) is that they never produce an exactly sparse solution. Indeed, the EM minimization requires strictly positive hyperparameters, since the objective function in the E-step is defined strictly in the domain γ>0\gamma>0 which matches the natural parameter space of the underlying probabilistic model, so the solution in M-step is strictly positive. If γn0>0\gamma_n^0>0 (i.e., nthn^{\mathrm{th}} component of the initial start is strictly positive), then the M-step yields γnk+1>0\gamma_n^{k+1}>0 for all kk. Conversely, if γn0=0\gamma_n^0=0, then γnk=0\gamma_n^k=0 for all kk, i.e., once a component is initialized at zero, it remains zero throughout the EM iterations. Consequently, under positive initialization, M-SBL returns iterates that are dense for every finite kk, although its components may become arbitrarily small as the iterations proceed.

Sparsifying the solution

The (local) minimizer γ^\hat{\gamma} of ℓ(γ)\ell(\gamma) found by any of the CL methods (CWO, EM of M-SBL, or the proposed CL-SCA, CL-FP, or CL-Hyb) may not be sufficiently sparse. For this reason, in Step 3 of Algorithm 1, one prunes small signal powers to zero via γ^←γ^⊙α^\hat{\gamma}\leftarrow\hat{\gamma}\odot\hat{\boldsymbol{\alpha}}, where the activity indices α^\hat{\boldsymbol{\alpha}} are obtained using either of the following rules:

  • The threshold-rule:

α^n=1{γ^n≥γthr}={1,if γ^n≥γthr,0,otherwise(19)\hat{\alpha}_n=\mathbf{1}\{\hat{\gamma}_n\ge\gamma_{\mathrm{thr}}\}= \begin{cases} 1, & \text{if }\hat{\gamma}_n\ge\gamma_{\mathrm{thr}},\\ 0, & \text{otherwise} \end{cases} \tag*{(19)}

where γthr\gamma_{\mathrm{thr}} is a fixed threshold.

  • The top KK-rule:

α^n=1{γn is among the K largest entries of γ^}(20)\hat{\alpha}_n=\mathbf{1}\{\gamma_n\text{ is among the }K\text{ largest entries of }\hat{\gamma}\} \tag*{(20)}

where the sparsity level KK is assumed to be known. The latter requires knowledge (or an estimate) of K=∣M∣K=|\mathcal{M}| while the former requires calibrating a suitable threshold, either using a priori knowledge or via estimation. The threshold can be designed such that a desired trade-off between the probabilities of missed detection and false alarm is achieved.

CL-SCA algorithm

Under the SCA framework, each agent in the optimization focuses on a single variable, γ1,γ2,…,γN\gamma_1,\gamma_2,\ldots,\gamma_N, and the resulting updates are performed iteratively and in parallel.

CL-SCA algorithm

At iteration k+1k+1, by following the SCA framework and linearizing the concave term f(γ)=log⁡∣Σ∣f(\gamma)=\log|\boldsymbol{\Sigma}|, the NN functions to be minimized by the NN agents in parallel are given as

ℓn(γn∣γk)=g(γ1k,…,γn−1k,γn,γn+1k,…,γNk)+dnk(γn−γnk),n∈{1,…,N},(21)\ell_n(\gamma_n\mid\gamma^k)=g(\gamma_1^k,\ldots,\gamma_{n-1}^k,\gamma_n,\gamma_{n+1}^k,\ldots,\gamma_N^k)+d_n^k(\gamma_n-\gamma_n^k),\quad n\in\{1,\ldots,N\}, \tag*{(21)}

where dnkd_n^k is defined in (17). The solution is given below.

Theorem 1. For n∈{1,…,N}n\in\{1,\ldots,N\}, the minimizer of the convex function ℓn(γn∣γk)\ell_n(\gamma_n\mid\gamma^k) over γn≥0\gamma_n\ge0 is

γ^n(γk)=[γnk+1dnk(enkdnk−1)]+(22)\hat{\gamma}_n(\gamma^k)=\left[\gamma_n^k+\frac{1}{d_n^k}\left(\sqrt{\frac{e_n^k}{d_n^k}}-1\right)\right]_+ \tag*{(22)}

where dnkd_n^k and enke_n^k are defined in (17).

Proof. See Appendix B.

The update (22) coincides with the one derived in the conference version [25 Th. 1] of this work, but it is also closely related to the majorization-minimization (MM)-based covariance learning algorithm (CLMM) of [12]: the two were obtained independently and look dissimilar, but they move each coordinate in the same direction and differ only in one scalar multiplier. We defer this discussion to subsection V-B.

Once solutions in (22) are computed for each signal power in parallel, denoted γ^(γk)=(γ^1(γk),…,γ^N(γk))\hat{\gamma}(\gamma^k)=(\hat{\gamma}_1(\gamma^k),\ldots,\hat{\gamma}_N(\gamma^k)), the next iterates of the algorithm are formed by including a smoothing (damping) operation with the previous ones, which is necessary to guarantee convergence, as

Algorithm 2: CL-SCA algorithm
Input : S\mathbf{S}, A\mathbf{A}, σ2\sigma^{2}, step-size sequence {ηk}\{\eta^{k}\}, Imax⁡I_{\max}.
Initialize: γ0=0\gamma^{0}=0, δ=10−3\delta=10^{-3}, k=0k=0.
repeat
1Compute Σk=Adiag⁡(γk)AH+σ2I\boldsymbol{\Sigma}^{k}=\mathbf{A}\operatorname{diag}(\gamma^{k})\mathbf{A}^{\mathrm{H}}+\sigma^{2}\mathbf{I} and Bk=(Σk)−1A=(b1k ⋯ bNk)\mathbf{B}^{k}=(\boldsymbol{\Sigma}^{k})^{-1}\mathbf{A}=(\mathbf{b}_{1}^{k}\ \cdots\ \mathbf{b}_{N}^{k}).
2For all n∈{1,…,N}n\in\{1,\ldots,N\} solve in parallel: γ^n(γk)=[γnk+1dnk(enkdnk−1)]+\widehat{\gamma}_{n}(\gamma^{k})=\left[\gamma_{n}^{k}+\frac{1}{d_{n}^{k}}\left(\sqrt{\frac{e_{n}^{k}}{d_{n}^{k}}}-1\right)\right]_{+} where dnk=anHbnkd_{n}^{k}=\mathbf{a}_{n}^{\mathrm{H}}\mathbf{b}_{n}^{k} and enk=[bnk]HSbnke_{n}^{k}=[\mathbf{b}_{n}^{k}]^{\mathrm{H}}\mathbf{S}\mathbf{b}_{n}^{k}.
3γk+1=γk+ηkpk\gamma^{k+1}=\gamma^{k}+\eta^{k}\mathbf{p}^{k}, where pk=γ^(γk)−γk\mathbf{p}^{k}=\widehat{\gamma}(\gamma^{k})-\gamma^{k}.
4k=k+1k=k+1
5until ∣γk−[γk−∇ℓ(γk)]+∣∞<δ\left|\gamma^{k}-[\gamma^{k}-\nabla\ell(\gamma^{k})]_{+}\right|_{\infty}<\delta or k≥Imax⁡k\geq I_{\max}
Output : γ^=γk\widehat{\gamma}=\gamma^{k}.

Table 2.

γk+1=(1−ηk)γk+ηkγ^(γk)=γk+ηkpk(23)\gamma^{k+1}=(1-\eta^{k})\gamma^{k}+\eta^{k}\widehat{\gamma}(\gamma^{k})=\gamma^{k}+\eta^{k}\mathbf{p}^{k} \tag*{(23)}

where the step-size ηk∈(0,1]\eta^{k}\in(0,1] is introduced to control the length of the update along the update direction

pk=γ^(γk)−γk.(24)\mathbf{p}^{k}=\widehat{\gamma}(\gamma^{k})-\gamma^{k}. \tag*{(24)}

The step-size sequence {ηk}\{\eta^{k}\} can be conveniently chosen as a diminishing sequence, verifying ∑k=0∞ηk=∞\sum_{k=0}^{\infty}\eta^{k}=\infty and ∑k=0∞(ηk)2<+∞\sum_{k=0}^{\infty}(\eta^{k})^{2}<+\infty [9], [28]. However, our convergence analysis suggests a backtracking algorithm that certifies the best-iterate stationary rate. We use γ0=0\gamma^{0}=0 as default initial start. The CL-SCA algorithm is tabulated in algorithm 2.

Lemma 2. A vector γ∈R≥0N\gamma\in\mathbb{R}_{\geq0}^{N}, satisfies the KKT conditions (12) if and only if it is a fixed point of the update map of Theorem 1, i.e., γ^(γ)=γ\widehat{\gamma}(\gamma)=\gamma.

Proof. See Appendix C.

Lemma 1 and Lemma 2 thus provide two fixed-point characterizations of stationarity. Lemma 1 and the SCA update map γ^(⋅)\widehat{\gamma}(\cdot) of Theorem 1 characterize the same set:

γ^(γ)=γ ⟺ γ=[H(γ)]+ ⟺ γ satisfies (12).\widehat{\gamma}(\gamma)=\gamma\ \Longleftrightarrow\ \gamma=[H(\gamma)]_{+}\ \Longleftrightarrow\ \gamma\text{ satisfies (12)}.

This is no coincidence: recalling dn=anHbnd_{n}=\mathbf{a}_{n}^{\mathrm{H}}\mathbf{b}_{n}, en=bnHSbne_{n}=\mathbf{b}_{n}^{\mathrm{H}}\mathbf{S}\mathbf{b}_{n}, and writting rn=en/dnr_{n}=e_{n}/d_{n}, the unprojected displacements of the two maps are

γ^n(γ)−γn=rn−1dn(25)\widehat{\gamma}_{n}(\gamma)-\gamma_{n}=\frac{\sqrt{r_{n}}-1}{d_{n}} \tag*{(25)}
Hn(γ)−γn=rn−1dn=(1+rn)rn−1dn,(26)H_{n}(\gamma)-\gamma_{n}=\frac{r_{n}-1}{d_{n}}=(1+\sqrt{r_{n}})\frac{\sqrt{r_{n}}-1}{d_{n}}, \tag*{(26)}

thus they differ only by the positive factor 1+rn1+\sqrt{r_{n}}. In other words, both maps move every coordinate in the same direction determined by the sign of rn−1r_{n}-1, i.e., of −∇nℓ(γ)=en−dn-\nabla_{n}\ell(\gamma)=e_{n}-d_{n} and vanish simultaneously. As termination criterion we use

∥γk−[γk−∇ℓ(γk)]+∥∞<δ(27)\left\|\gamma^{k}-[\gamma^{k}-\nabla\ell(\gamma^{k})]_{+}\right\|_{\infty}<\delta \tag*{(27)}

where ∇nℓ(γk)=dnk−enk\nabla_{n}\ell(\gamma^{k})=d_{n}^{k}-e_{n}^{k} with some appropriate convergence threshold δ\delta (default δ=10−3\delta=10^{-3}). Note that (27) vanishes if and only if the KKT conditions (12) hold for γk\gamma^{k}. In addition, note that (27) is an algorithm independent criterion2 that we will use also to terminate other competing iterative CL methods (CL-FP, CLMM, M-SBL, CWO). Computing ∇ℓ(γk)\nabla\ell(\gamma^{k}) does not incur any extra costs, since dnkd_{n}^{k} and enke_{n}^{k} required by ∇nℓ(γk)\nabla_{n}\ell(\gamma^{k}) are reused (not recomputed) in Step 2. This is true for all methods considered.

The computational complexity of step 1 is O(NM2)+O(M3+M2N)O(NM^{2})+O(M^{3}+M^{2}N) while the computational complexity of step 2 is O(NM2)O(NM^{2}). Computational complexity of Step 3–4 are O(N)O(N). Since N≥MN\geq M, the complexity of one iteration of CL-SCA algorithm is O(NM2)O(NM^{2}). This is the same complexity per iteration as CWO [20], Algorithm 1, CL-MP [15], Algorithm 1, CLMM (cf. subsection IV-B), or the EM-algorithm (18) of M-SBL. The input to CL-based approaches is S\mathbf{S} (the SCM) with the computational complexity of O(QM2)O(QM^{2}). Thus, the overall complexities of CL-SCA, CLMM, EM algorithm of M-SBL and CWO are O(NM2Iiters+QM2)O(NM^{2}I_{\mathrm{iters}}+QM^{2}), where IitersI_{\mathrm{iters}} is the number of iterations until convergence. Note that CL-MP is a greedy CL-based approach, terminated after KK iterations (when KK is known), and hence its overall complexity is O(NM2K+QM2)O(NM^{2}K+QM^{2}). Thus CL-MP provides faster computations only in the ideal case when KK is known and K<IitersK<I_{\mathrm{iters}}. We provide convergence analysis of the CL-SCA (and CL-FP) algorithm in subsection IV-B.

Stationarity rate of CL-SCA

Define amin⁡2=min⁡n∥an∥2a_{\min}^{2}=\min_{n}\|\mathbf{a}_{n}\|^{2} and amax⁡2=max⁡n∥an∥2a_{\max}^{2}=\max_{n}\|\mathbf{a}_{n}\|^{2} and note that both scalars are well-defined strictly positive constants as an≠0\mathbf{a}_{n}\ne0 for all nn. We say that ∇ℓ\nabla\ell is Lipschitz continuous on a set C⊆R≥0N\mathcal{C}\subseteq\mathbb{R}_{\geq0}^{N} with constant L∇>0L_{\nabla}>0 if

∥∇ℓ(γ)−∇ℓ(γ′)∥2≤L∇∥γ−γ′∥2∀γ,γ′∈C.(28)\|\nabla\ell(\gamma)-\nabla\ell(\gamma')\|_{2}\leq L_{\nabla}\|\gamma-\gamma'\|_{2}\quad\forall\gamma,\gamma'\in\mathcal{C}. \tag*{(28)}

Since Σ(γ)≻0\boldsymbol{\Sigma}(\gamma)\succ0 on an open set containing R≥0N\mathbb{R}_{\geq0}^{N}, ℓ\ell is twice continuously differentiable there, and for convex ℓ\ell a sufficient condition for (28) is ∥∇2ℓ(γ)∥2≤L∇\|\nabla^{2}\ell(\gamma)\|_{2}\leq L_{\nabla} for γ∈C\gamma\in\mathcal{C} (see e.g., [29, Lemma 1.2.2]). Property (28) implies the quadratic upper bound [30 Prop. A.24]:

ℓ(γ′)≤ℓ(γ)+∇ℓ(γ)T(γ′−γ)+L∇2∥γ′−γ∥22∀γ,γ′∈C,(29)\ell(\gamma')\leq\ell(\gamma)+\nabla\ell(\gamma)^{\mathsf{T}}(\gamma'-\gamma)+\frac{L_{\nabla}}{2}\|\gamma'-\gamma\|_{2}^{2}\quad\forall\gamma,\gamma'\in\mathcal{C}, \tag*{(29)}

which is used later in Theorem 2. The next lemma collects the two constants that govern the step-size rule.

Lemma 3. Let

K0={γ∈R≥0N:ℓ(γ)≤ℓ(γ0)}\mathcal{K}_{0}=\{\gamma\in\mathbb{R}_{\geq0}^{N}:\ell(\gamma)\leq\ell(\gamma^{0})\}

denote the initial sublevel set. Then:

(i) K0\mathcal{K}_{0} is compact, and λ‾max⁡(Σ)≤λ‾0\overline{\lambda}_{\max}(\boldsymbol{\Sigma})\leq\overline{\lambda}_{0} with λ‾0=σ−2(M−1)exp⁡{ℓ(γ0)}\overline{\lambda}_{0}=\sigma^{-2(M-1)}\exp\{\ell(\gamma^{0})\} for all γ∈K0\gamma\in\mathcal{K}_{0}. Consequently

d‾=min⁡γ∈K0min⁡1≤n≤Ndn(γ)≥amin⁡2λ‾0>0(30)\overline{d}=\min_{\gamma\in\mathcal{K}_{0}}\min_{1\leq n\leq N}d_{n}(\gamma)\geq\frac{a_{\min}^{2}}{\overline{\lambda}_{0}}>0 \tag*{(30)}

where dn(γ)=anHΣ−1and_n(\gamma)=a_n^{\mathsf{H}}\Sigma^{-1}a_n.

(ii) ∇ℓ\nabla\ell is Lipschitz continuous on all of R≥0N\mathbb{R}_{\ge0}^{N} with constant

L∇=amax⁡2∥A∥22σ4(1+2∥S∥2σ2).(31)L_{\nabla}=\frac{a_{\max}^{2}\lVert A\rVert_{2}^{2}}{\sigma^{4}}\left(1+\frac{2\lVert S\rVert_{2}}{\sigma^{2}}\right). \tag*{(31)}

Proof. See Appendix D.

We can now state the sufficient decrease and stationarity rate. Note that ℓinf⁡=inf⁡γ≥0ℓ(γ)>−∞\ell_{\inf}=\inf_{\gamma\ge0}\ell(\gamma)>-\infty as ℓ(γ)≥Mlog⁡σ2\ell(\gamma)\ge M\log\sigma^{2}.

Theorem 2. If 0<ηk≤ηˉ0<\eta^{k}\le\bar{\eta} for all kk, where

ηˉ=min⁡{1,d2L∇},(32)\bar{\eta}=\min\left\{1,\frac{d^{2}}{L_{\nabla}}\right\}, \tag*{(32)}

then the CL-SCA iterates (23) satisfy γk∈K0\gamma^{k}\in\mathcal{K}_{0} and

ℓ(γk+1)≤ℓ(γk)−d22ηk∥pk∥22(33)\ell(\gamma^{k+1})\le\ell(\gamma^{k})-\frac{d^{2}}{2}\eta^{k}\lVert p^{k}\rVert_{2}^{2} \tag*{(33)}

where dd and L∇L_{\nabla} are as in Lemma 3. Consequently, for every T≥1T\ge1,

min⁡0≤k<T∥pk∥22≤2{ℓ(γ0)−ℓinf⁡}d2∑k=0T−1ηk≤2tr⁡(S)/σ2d2∑k=0T−1ηk.(34)\min_{0\le k<T}\lVert p^{k}\rVert_{2}^{2}\le\frac{2\{\ell(\gamma^{0})-\ell_{\inf}\}}{d^{2}\sum_{k=0}^{T-1}\eta^{k}}\le\frac{2\operatorname{tr}(S)/\sigma^{2}}{d^{2}\sum_{k=0}^{T-1}\eta^{k}}. \tag*{(34)}

If, in addition, inf⁡kηk>0\inf_{k}\eta^{k}>0, then ∥pk∥2→0\lVert p^{k}\rVert_{2}\to0 and every accumulation point of {γk}\{\gamma^{k}\} is KKT-stationary.

Proof. See Appendix E.

For a constant step size η∈(0,ηˉ]\eta\in(0,\bar{\eta}], (34) yields the best-iterate stationarity rate min⁡k<T∥pk∥2=O(T−1/2)\min_{k<T}\lVert p^{k}\rVert_{2}=O(T^{-1/2}), matching the canonical rate of first-order methods on smooth nonconvex problems. In contrast, diminishing schedules ηk=c(k+1)−a\eta^{k}=c(k+1)^{-a} degrade the certified rate to O(T−(1−a)/2)O(T^{-(1-a)/2}) for a∈(1/2,1)a\in(1/2,1) and O((log⁡T)−1/2)O((\log T)^{-1/2}) for a=1a=1, since ∑k<Tηk\sum_{k<T}\eta^{k} then grows only as Θ(T1−a)\Theta(T^{1-a}) or Θ(log⁡T)\Theta(\log T). Moreover, they do not meet the condition inf⁡kηk>0\inf_{k}\eta^{k}>0 under which Theorem 2 guarantees that the residual vanishes along the whole sequence.

Step-size selection

Based on Theorem 2, one could resort to a fixed stepsize (fss) η=ηˉ\eta=\bar{\eta} in (32), which maximizes the guaranteed decrease in (33). However, ηˉ\bar{\eta} depends on dd and L∇L_{\nabla}, which are not known a priori; computable bounds on them give an admissible but overly conservative step size.

Since dnk=anHbnkd_n^{k}=a_n^{\mathsf{H}}b_n^{k} are computed in every iteration of Algorithm 2, a step size satisfying the conditions of Theorem 2 can be found adaptively by the following backtracking rule: maintain the running minimum dk=min⁡s≤kmin⁡ndnsd_k=\min_{s\le k}\min_n d_n^{s}, and halve a trial step ηk≤1\eta^{k}\le1 until

ℓ(γk+ηkpk)≤ℓ(γk)−dk22ηk∥pk∥22.\ell(\gamma^{k}+\eta^{k}p^{k})\le\ell(\gamma^{k})-\frac{d_k^{2}}{2}\eta^{k}\lVert p^{k}\rVert_{2}^{2}.

Since dk≥dd_k\ge d, every accepted step satisfies the sufficient-decrease inequality (33), and the test is passed by every ηk≤ηˉ\eta^{k}\le\bar{\eta}. Hence the loop terminates after at most ⌈log⁡2(1/ηˉ)⌉\lceil\log_{2}(1/\bar{\eta})\rceil halvings, the accepted steps satisfy ηk≥ηˉ/2\eta^{k}\ge\bar{\eta}/2, and Theorem 2 applies in full, including the O(T−1/2)O(T^{-1/2}) rate and ∥pk∥2→0\lVert p^{k}\rVert_{2}\to0, without dd or L∇L_{\nabla} having to be known. Rather than restarting from η=1\eta=1 in every iteration, the search starts from the last accepted step size, and doubles it after two consecutive iterations accepted at the first trial, so that the step can grow again.

SCA via damped fixed-point iterations

The fixed-point characterization γ=[H(γ)]+\gamma=[H(\gamma)]_{+} of Lemma 1 suggests the iteration γk+1=[H(γk)]+\gamma^{k+1}=[H(\gamma^{k})]_{+}. The first observation is that this map is a diagonally scaled projected gradient step:

[H(γ)]+=arg⁡min⁡u≥0∇ℓ(γ)T(u−γ)+12∑n=1Ndn2(un−γn)2(35)[H(\gamma)]_{+}=\arg\min_{u\ge0}\nabla\ell(\gamma)^{\mathsf{T}}(u-\gamma)+\frac{1}{2}\sum_{n=1}^{N}d_n^{2}(u_n-\gamma_n)^{2} \tag*{(35)}

where dn=∇nf(γ)d_n=\nabla_n f(\gamma) defined by (9). This result easily follows because the quadratic problem in (35) is separable in coordinates and its nnth coordinate minimizer is [γn−∇nℓ(γ)/dn2]+[\gamma_n-\nabla_n\ell(\gamma)/d_n^{2}]_{+}, precisely the fixed point map Hn(γ)H_n(\gamma). Thus we define damped fixed point iteration as

γk+1=γk+ηkqk,qk=[H(γk)]+−γk.(36)\gamma^{k+1}=\gamma^{k}+\eta^{k}q^{k},\quad q^{k}=[H(\gamma^{k})]_{+}-\gamma^{k}. \tag*{(36)}

The damped iteration (36) is itself a parallel SCA scheme: it minimizes, per coordinate, the strongly convex quadratic surrogate in (35) (curvature dn2d_n^{2}, gradient matching ∇ℓ\nabla\ell at γk\gamma^{k}), whereas CL-SCA minimizes the nonquadratic surrogate ℓn\ell_n of (21). This interpretation explains why, as shown below, the two algorithms obey the same convergence guarantee under the same constants. The method (36) was proposed in [24 cf. Eq. (50)] under the name PSCA-ML-UD. Here, however, we derived the method as a damped fixed-point iteration and henceforth refer to the algorithm as CL-FP to emphasize this connection. In the next subsection we derive the stationarity rate of CL-FP and discuss similarities and differences with the CL-SCA algorithm. We emphasize that in [24], the convergence rate and step size selection was not addressed and thus results of subsection V-A are new.

Stationarity rate of CL-FP and comparison to CL-SCA

We wish to point out that the undamped map T(γ)=[H(γ)]+T(\gamma)=[H(\gamma)]_{+} is, in general, not a contraction, so that the classical fixed-point theory (Banach) does not apply and damping is not merely cosmetic.

again. Every accepted step still satisfies ηk≥ηˉ/2\eta^{k}\ge\bar{\eta}/2, so the rate guarantee is unaffected. The rule is also inexpensive: evaluating ℓ\ell at a trial point requires the Cholesky factor of Σ\Sigma at that point, which is precisely the factor needed by the update of the next iteration. An accepted first trial thus costs nothing extra, and each rejected trial costs one additional factorization.

Another alternative is to use diminishing step-size (dss), which however does not provide the best possible rate. As default dss-sequence, we use ηk=ηk−1(1−ϵηk−1)\eta^{k}=\eta^{k-1}(1-\epsilon\eta^{k-1}), where ϵ∈(0,1)\epsilon\in(0,1) is a given constant, and η0<1/ϵ\eta^{0}<1/\epsilon. We set η0=0.99\eta^{0}=0.99 and ϵ=0.05\epsilon=0.05 as default values.

To conclude, a constant step size attains the best worst-case rate only if η\eta is tuned close to the unknown constant ηˉ\bar{\eta}. The backtracking rule requires no tuning, retains the O(T−1/2)O(T^{-1/2}) rate (its steps satisfy ηk≥ηˉ/2\eta^{k}\ge\bar{\eta}/2), and takes larger steps whenever the landscape permits. Backtracking is therefore our recommended choice, while the diminishing schedule serves mainly as a baseline for comparisons.

Theorem 3. Let qk=[H(γk)]+−γk\mathbf{q}^{k} = [H(\boldsymbol{\gamma}^{k})]_{+} - \boldsymbol{\gamma}^{k} and let dd, L∇L_{\nabla}, and ηˉ=min⁡{1,d2/L∇}\bar{\eta} = \min\{1,d^{2}/L_{\nabla}\} be as in Lemma 3 and Theorem 2. If 0<ηk≤ηˉ0 < \eta^{k} \le\bar{\eta}, then the iterates of (36) satisfy γk∈K0\boldsymbol{\gamma}^{k} \in\mathcal{K}_{0} and

ℓ(γk+1)≤ℓ(γk)−d22ηk∥qk∥22,(37)\ell(\boldsymbol{\gamma}^{k+1}) \le\ell(\boldsymbol{\gamma}^{k}) - \frac{d^{2}}{2}\eta^{k}\lVert\mathbf{q}^{k}\rVert_{2}^{2}, \tag*{(37)}

and consequently the rate bound (34), the best-iterate rate min⁡k<T∥qk∥2=O(T−1/2)\min_{k<T}\lVert\mathbf{q}^{k}\rVert_{2} = O(T^{-1/2}) for constant η∈(0,ηˉ]\eta\in(0,\bar{\eta}], and when inf⁡kηk>0\inf_{k}\eta^{k} > 0, the convergence ∥qk∥2→0\lVert\mathbf{q}^{k}\rVert_{2} \to0 with every accumulation point KKT-stationary, all hold precisely.

Proof. See Appendix F.

The damped FP iterations, which we refer to as CL-FP algorithm and the earlier CL-SCA are two members of the same family: parallel SCA algorithms whose convex coordinate surrogates match ∇nℓ\nabla_{n}\ell at the current iterate and have curvature 2dn22d_{n}^{2} (CL-SCA) and dn2d_{n}^{2} (CL-FP) at a stationary point; the CL-FP surrogate is quadratic, hence strongly convex with modulus d2d^{2} on K0\mathcal{K}_{0}. They also share identical guarantees: (a) the same safe damping bound ηˉ\bar{\eta}, (b) the same sufficient-decrease constant d2/2d^{2}/2, (c) the same O(T−1/2)O(T^{-1/2}) rate, and (d) the same per-iteration computational complexity. Their residuals, p=γ^(γ)−γ\mathbf{p} = \hat{\boldsymbol{\gamma}}(\boldsymbol{\gamma}) - \boldsymbol{\gamma} in (24) and q=[H(γ)]+−γ\mathbf{q} = [H(\boldsymbol{\gamma})]_{+} - \boldsymbol{\gamma} in (36), respectively, verify

qn=(1+en/dn) pn(38)q_{n} = (1+\sqrt{e_{n}/d_{n}})\,p_{n} \tag*{(38)}

whenever neither projection is active. Thus, ∣pn∣≤∣qn∣|p_{n}| \le|q_{n}| always holds. The residual norms, ΔSCA(γ)=∥γ^(γ)−γ∥2\Delta_{\mathrm{SCA}}(\boldsymbol{\gamma}) = \lVert\hat{\boldsymbol{\gamma}}(\boldsymbol{\gamma})-\boldsymbol{\gamma}\rVert_{2} and ΔFP(γ)=∥[H(γ)]+−γ∥2\Delta_{\mathrm{FP}}(\boldsymbol{\gamma}) = \lVert[H(\boldsymbol{\gamma})]_{+}-\boldsymbol{\gamma}\rVert_{2}, are equivalent stationarity measures: ΔSCA(γ)≤ΔFP(γ)≤(1+rˉ)ΔSCA(γ)\Delta_{\mathrm{SCA}}(\boldsymbol{\gamma}) \le\Delta_{\mathrm{FP}}(\boldsymbol{\gamma}) \le(1+\sqrt{\bar{r}})\Delta_{\mathrm{SCA}}(\boldsymbol{\gamma}) with rˉ=max⁡γ∈K0max⁡nen/dn<∞\bar{r} = \max_{\boldsymbol{\gamma}\in\mathcal{K}_{0}}\max_{n}e_{n}/d_{n} < \infty. The two maps differ, however, in their local behavior near a KKT point γ⋆\boldsymbol{\gamma}^{\star}: there en/dn→1e_{n}/d_{n} \to1 on the support, so the FP step is asymptotically exactly twice the SCA step, and the local Jacobians on the support (under strict complementarity) are

JSFP=I−DS[∇2ℓ]SS,JSSCA=I−12DS[∇2ℓ]SS.J_{\mathcal{S}}^{\mathrm{FP}} = I - D_{\mathcal{S}}[\nabla^{2}\ell]_{\mathcal{S}\mathcal{S}}, \qquad J_{\mathcal{S}}^{\mathrm{SCA}} = I - \frac{1}{2}D_{\mathcal{S}}[\nabla^{2}\ell]_{\mathcal{S}\mathcal{S}}.

where DS=diag⁡(1/dn(γ⋆)2)n∈SD_{\mathcal{S}} = \operatorname{diag}(1/d_{n}(\boldsymbol{\gamma}^{\star})^{2})_{n\in\mathcal{S}} and S=supp⁡(γ⋆)={n∈{1,…,N}:γn⋆>0}\mathcal{S} = \operatorname{supp}(\boldsymbol{\gamma}^{\star}) = \{n \in\{1,\ldots,N\}:\gamma_{n}^{\star}>0\}. Therefore, the undamped SCA map is locally convergent whenever the eigenvalues of the scaled Hessian lie in (0,4)(0,4), while the undamped FP map requires the twice-smaller interval (0,2)(0,2): CL-SCA has double the local stability margin, where the full step ηk=1\eta^{k}=1 is often accepted by CL-SCA but destabilizes the FP iteration on the same data. This also confirms our empirical observation that CL-SCA tolerates roughly twice the damping factor of the FP iteration.

Finally, since Theorem 3 holds with the same constants dd and L∇L_{\nabla} as Theorem 2, the safe constant step size ηˉ\bar{\eta}, the diminishing step-size rule, and the backtracking rule of Subsection IV-C apply to the FP iteration without modification. In practice, however, the FP displacement exceeds the SCA displacement by the factor 1+en/dn1+\sqrt{e_{n}/d_{n}} (as noted in (38)), so a fixed step tuned for CL-SCA is typically too large for CL-FP, whereas the backtracking rule adapts to this automatically.

multiplierresidual
EM of M-SBL (18)γn2dn\gamma_{n}^{2}d_{n}rn−1r_{n}-1
CL-FP (13)(1+rn)/dn(1+\sqrt{r_{n}})/d_{n}rn−1\sqrt{r_{n}}-1
CL-SCA (22)1/dn1/d_{n}rn−1\sqrt{r_{n}}-1
CLMM (39)γn+σ2/ν\gamma_{n}+\sigma^{2}/\nurn−1\sqrt{r_{n}}-1

Table 1. The four update maps as one family: γn↦γn+(multiplier)×(residual)\gamma_{n}\mapsto\gamma_{n}+(\text{multiplier})\times(\text{residual}), before projection onto γn≥0\gamma_{n}\geq0.

Relation to the MM-based algorithm

The CLMM [12] method majorizes both terms of ℓ(γ)\ell(\boldsymbol{\gamma}): the concave log (1) by the same linearization used in (21), and the convex g(γ)g(\boldsymbol{\gamma}) by the matrix upper bound of [31 Prop. 4], applied after absorbing part of the noise floor into the signal powers so that the bound remains tight where γn=0\gamma_{n}=0. This requires a majorization constant ν≥λmax⁡(AAH)\nu\geq\lambda_{\max}(\mathbf{A}\mathbf{A}^{\mathrm{H}}) (denoted η\eta in [12] but renamed here to avoid a clash with step size ηk\eta^{k}). After some algebra, and using notations in this paper, the CLMM update rewrites as

γnk+1=[γnk+(γnk+σ2/ν)(rnk−1)]+,(39)\gamma_{n}^{k+1} = \left[\gamma_{n}^{k}+\left(\gamma_{n}^{k}+\sigma^{2}/\nu\right)\left(\sqrt{r_{n}^{k}}-1\right)\right]_{+}, \tag*{(39)}

which is precisely (25) with the multiplier 1/dnk1/d_{n}^{k} replaced by γnk+σ2/ν\gamma_{n}^{k}+\sigma^{2}/\nu. Together with (18) and (13), all four update maps considered in this paper are then members of a single family, each of the form γn↦γn+(multiplier)×(residual)\gamma_{n}\mapsto\gamma_{n}+(\text{multiplier})\times(\text{residual}) before projection, as summarized in tbl:I.

The residual vanishes exactly at rn=1r_{n}=1, i.e. at en=dne_{n}=d_{n}, so on the support all four maps stop at the same points. At the boundary γn=0\gamma_{n}=0 they do not, and the multiplier is what decides it. For CL-FP, CL-SCA and CLMM the multiplier is bounded away from zero ((1+rn)/dn(1+\sqrt{r_{n}})/d_{n}, 1/dn1/d_{n}, and γn+σ2/ν≥σ2/ν>0\gamma_{n}+\sigma^{2}/\nu\geq\sigma^{2}/\nu> 0, respectively), so a coordinate at γn=0\gamma_{n}=0 is left unchanged only when rn≤1r_{n}\leq1, which is precisely the KKT condition (12). Lemma 2 therefore extends precisely to CLMM, whose fixed points are again the KKT points of (6). The EM multiplier γn2dn\gamma_{n}^{2}d_{n}, in contrast, vanishes at γn=0\gamma_{n}=0, so every coordinate with γn=0\gamma_{n}=0 is fixed irrespective of the sign of ∇nℓ\nabla_{n}\ell: the fixed points of (18) strictly contain the KKT points, the spurious ones being those with γn=0\gamma_{n}=0 and en>dne_{n}>d_{n}. This is also why (18) needs no projection: its multiplicative form cannot leave the nonnegative orthant.

Moreover, the two multipliers of CL-SCA and CLMM can be compared exactly. By (44) we have 1/dn=γn+1/(γnen)1/d_{n}=\gamma_{n}+1/(\gamma_{n}e_{n}), so both are of the form γn\gamma_{n} plus a positive quantity, and since ∑nananH⪰σ2I\sum_{n}\mathbf{a}_{n}\mathbf{a}_{n}^{\mathrm{H}}\succeq\sigma^{2}I gives anHan≤∥an∥2/σ2\mathbf{a}_{n}^{\mathrm{H}}\mathbf{a}_{n}\leq\lVert\mathbf{a}_{n}\rVert^{2}/\sigma^{2} while ν≥λmax⁡(AAH)≥∥an∥2\nu\geq\lambda_{\max}(\mathbf{A}\mathbf{A}^{\mathrm{H}})\geq\lVert\mathbf{a}_{n}\rVert^{2},

σ2ν≤σ2∥an∥2≤1anHcn,(40)\frac{\sigma^{2}}{\nu}\leq\frac{\sigma^{2}}{\lVert\mathbf{a}_{n}\rVert^{2}}\leq\frac{1}{\mathbf{a}_{n}^{\mathrm{H}}\mathbf{c}_{n}}, \tag*{(40)}

so that the CLMM multiplier never exceeds the CL-SCA one, at every coordinate and every iterate. In this precise sense, CLMM is an intrinsically damped CL-SCA iteration, which explains why it is monotone with no step size while the parallel update (23) requires the damping ηk\eta^{k}: the damping of CLMM is built into its majorizer, and ν\nu is its price. The gap in (40) is exactly the looseness of ν\nu. With the choice ν=tr⁡(AAH)\nu=\operatorname{tr}(\mathbf{A}\mathbf{A}^{\mathrm{H}}) used in [12] and equal-norm atoms, ν=N∥an∥2\nu=N\lVert\mathbf{a}_{n}\rVert^{2}, starting from γn0=0\gamma_n^0=0, the CLMM step is thus shorter than the CL-SCA step by a factor NN. This does not translate into a proportional loss of speed, however, since (39) is multiplicative in the shifted variable γˉn=γn+σ2/ν\bar{\gamma}_n=\gamma_n+\sigma^2/\nu, for which it reads γˉnk+1=rnk γˉnk\bar{\gamma}_n^{k+1}=\sqrt{r_n^k}\,\bar{\gamma}_n^k. A conservative ν\nu therefore costs a logarithmic rather than a linear number of additional iterations.

Two remarks complete the comparison. First, both surrogates contain the same linear term dnkγnd_n^k\gamma_n of (21), since both methods linearize the same concave term. They differ only in the convex term gg, which CL-SCA keeps exact along the coordinate (via the Sherman–Morrison identity), whereas CLMM majorizes it to obtain a surrogate that is separable in all NN coordinates. The CL-SCA surrogate is thus tighter, but only along one coordinate with the others frozen, whereas the CLMM surrogate is a joint majorizer. Second, the comparison above concerns the undamped map γ^(γk)\hat{\gamma}(\gamma^k), i.e., (22) with ηk=1\eta^k=1, not the damped iteration of Algorithm 2.

Convergence analysis and a new Hybrid method

Convergence is assessed with two complementary measures. The objective gap ℓ(γk)−ℓ⋆\ell(\gamma^k)-\ell^\star, where ℓ⋆\ell^\star is the smallest objective value recorded over a 1500-iteration reference run, is plotted on a logarithmic axis to resolve the behavior near stationarity: a locally linearly convergent method appears as a straight line whose slope is its contraction rate. Since the raw objective is used, the gap also exposes the non-monotone transient of the diminishing step-size variants. The normalized running-minimum loss ℓnormk=min⁡s≤kℓ(γs)/ℓ(γ0)\ell_{\mathrm{norm}}^k=\min_{s\leq k}\ell(\gamma^s)/\ell(\gamma^0) starts from one for every run and is monotone for all methods. It measures time-to-target and is the view in which iteration counts and wall-clock times are reported.

All methods are initialized at γ0=1\gamma^0=1, since zero coordinates remain fixed under the EM update, and a common initialization ensures that methods converging to the same stationary point converge to the same level in both figures. We compare CWO [20], Alg. 1, EM-based solver of M-SBL [11], and CLMM [12] which uses ν=∥A∥F2\nu=\lVert A\rVert_F^2. We also consider a variant CLMM-2 which uses ν=∥A∥22\nu=\lVert A\rVert_2^2 (instead of the Frobenius norm) which by (40) and ν≥λmax⁡(AAH)=∥A∥22\nu\geq\lambda_{\max}(AA^{\mathrm{H}})=\lVert A\rVert_2^2 provides the largest step size and thus a better local rate. Finally, we consider the proposed variants: CL-SCA-dss/CL-FP-dss use the diminishing step-size sequence with η0=0.99\eta_0=0.99 and ϵ=0.05\epsilon=0.05, CL-SCA-fss uses η=0.6\eta=0.6 and CL-FP-fss uses η=0.35\eta=0.35. These were hand-tuned step-sizes (chosen as large as possible) that worked for our set-up with dimension M=20M=20. The hybrid CL-Hyb applies CL-SCA-fss for the first five iterations and CL-FP-fss thereafter, with the same tuned step sizes. CL-SCA-bt and CL-Hyb-bt are the corresponding tuning-free variants: every step size is selected by the backtracking rule of Subsection IV-C, and CL-Hyb-bt switches from the SCA to the FP proposal after five iterations, as CL-Hyb does. Since near a KKT point the FP displacement is about twice the SCA displacement, an FP step η\eta acts locally like an SCA step 2η2\eta; at the switch, CL-Hyb-bt therefore halves the last accepted step size, so that its first FP trial has the same effective length as the last SCA step. In order to be fair, all methods are implemented by ourselves in Python/NumPy with identical linear-algebra routines and optimized for best performance. For CWO we also use the random permutation strategy which is reported to improve its speed [21].

Simulation setting: For each trials, AA is a random Bernoulli matrix, with elements generated as [A]mn∈{±12±j12}[A]_{mn}\in\{\pm\frac{1}{\sqrt{2}}\pm\mathrm{j}\frac{1}{\sqrt{2}}\}, so that ∥an∥22=M\lVert a_n\rVert_2^2=M while the support M\mathcal{M} is drawn uniformly without replacement from {1,…,N}\{1,\ldots,N\}. The noise variance is fixed σ2=1\sigma^2=1 and the KK-nonzero signal powers of the Gaussian sources are uniformly distributed between [−15,0][-15,0] in dB scale and generated independently for each trial.

Figure 1 reports both measures for K=30K=30, M=20M=20, N=300N=300, and Q=50Q=50 over 20 MC runs. The per-run target ℓref\ell_{\mathrm{ref}} in the bottom panel is the objective value reached by ten CWO cycles. This time-to-target metric compares progress in objective value only: ten CWO cycles are a heuristic budget that does not imply stationarity.

Several observations can be drawn. First, the two baselines are far slower than the proposed methods. The EM iterations of M-SBL reduce the gap by less than a factor of 20 over 120 iterations, from 60 to 3.2, and never reach ℓref\ell_{\mathrm{ref}} within 250 iterations; CLMM decays faster but still slowly (gap 6.3×10−36.3\times10^{-3} at k=120k=120) and does not reach the target either. CLMM-2 improves over CLMM and achieves gap 2.53×10−32.53\times10^{-3} at k=120k=120. By contrast, the fixed-step and backtracking variants drive the gap below 10−510^{-5} within 55 iterations, and the diminishing-step variants within 100.

Second, the fixed step size gives a substantial gain over the diminishing schedule. At k=50k=50 the median gap of CL-SCA-fss is 1.8×10−51.8\times10^{-5} against 2.6×10−42.6\times10^{-4} for CL-SCA-dss, and that of CL-FP-fss is 8.4×10−68.4\times10^{-6} against 8.6×10−58.6\times10^{-5} for CL-FP-dss, reductions by factors of 14 and 10 that exceed two orders of magnitude by k=100k=100. The dss curves are also markedly non-monotone during the first ten iterations, which the running-minimum view hides by construction. Both effects agree with Section IV-B: a diminishing sequence shrinks the accumulated step length that drives the convergence rate.

Third, the two fixed-step methods are complementary. At k=10k=10 the CL-SCA-fss gap is an order of magnitude smaller than that of CL-FP-fss (3.3×10−13.3\times10^{-1} versus 3.8), whereas from k≈35k\approx35 the ordering reverses. This agrees with the relation between their displacements: when the projection is inactive, the FP step equals (1+ϵn/dn)(1+\sqrt{\epsilon_n/d_n}) times the SCA step. Far from stationarity ϵn/dn\epsilon_n/d_n can be large, so the FP proposal is more aggressive and needs a smaller damping factor (η=0.35\eta=0.35 versus 0.6); near stationarity ϵn/dn→1\epsilon_n/d_n\to1 on the support, and the FP step becomes about twice the SCA step.

This motivates CL-Hyb, which uses the more stable SCA update for five iterations and then switches to FP. Since both updates satisfy the same sufficient-decrease inequality with the same constants (cf. Section IV-B), the convergence guarantees carry over. CL-Hyb tracks CL-SCA-fss through the transient and then inherits the faster FP decay: at k=50k=50 its gap is 3.9×10−63.9\times10^{-6}, against 8.4×10−68.4\times10^{-6} for CL-FP-fss and 1.8×10−51.8\times10^{-5} for CL-SCA-fss.

Fourth, backtracking yields a further large gain without any tuning. After a slower start, where the sufficient-decrease test enforces small steps, CL-Hyb-bt attains the smallest gap of all methods from k≈15k\approx15. At k=50k=50 the gaps of CL-SCA-bt and CL-Hyb-bt are 5.8×10−75.8 \times10^{-7} and 2.1×10−82.1 \times10^{-8}, i.e., 31 and 185 times smaller than those of CL-SCA-fss and CL-Hyb, and they reach the numerical floor of the gap (≈5×10−12\approx5 \times10^{-12}) by k≈100k \approx100 and k≈80k \approx80, respectively, against k≈120k \approx120 for CL-Hyb. The accepted steps are typically larger than the hand-tuned constants.

Fifth, the running-minimum panel translates these gains into runtime. CL-Hyb-bt reaches ℓref\ell_{\mathrm{ref}} in 30 iterations and 3.0 ms on average, and CL-FP-fss in 44 iterations and 3.9 ms, whereas M-SBL and CLMM do not reach it within 250 iterations (>28.5> 28.5 ms and >21.8> 21.8 ms). CWO needs only ten cycles but 8.4 ms, so CL-Hyb-bt in this setting attains the same objective level in near one third of the time despite using three times as many iterations. The reason is the cost per iteration: CL-SCA/CL-FP update the full vector γ^\hat{\boldsymbol{\gamma}} in one vectorized parallel step, whereas CWO cycles through the NN coordinates sequentially.

Finally, we computed the probability of missdetection (PMDP_{\mathrm{MD}}) under the top-KK rule, defined as the MC average of ∣M∖M^∣/K\lvert\mathcal{M}\setminus\hat{\mathcal{M}}\rvert/K. All CL-SCA, CL-FP and CL-Hyb variants and CWO give PMD=0.267P_{\mathrm{MD}}=0.267, consistent with their converging to the same stationary point, whereas M-SBL stalls at a higher loss and yields PMD=0.293P_{\mathrm{MD}}=0.293. CLMM also attains 0.267 although it does not reach ℓref\ell_{\mathrm{ref}}, indicating that the support is identified well before full convergence.

Application to JADCE in GFRA

JADCE in GFRA is a central problem in mMTC, where many devices with sporadic traffic access the uplink. Recent work shows that CL methods can outperform conventional CS approaches [15, 20, 21, 22, 23]. In contrast to CS methods, whose performance is limited when the number of active devices exceeds the pilot length, CL methods can relax this limitation and achieve comparable accuracy with substantially shorter pilots [20, 22].

We consider an uplink, single-cell massive random access scenario with NN single-antenna machine-type devices (MTDs) communicating with a BS equipped with QQ antennas. For device identification, each device nn is preassigned a unique pilot (signature) sequence an=(a1n,…,aMn)T\mathbf{a}_n=(a_{1n},\ldots,a_{Mn})^{\mathsf{T}} which is known at the BS. The device traffic is assumed to be sporadic, that is, in each coherence interval only K≪NK\ll N devices are randomly active. In mMTC settings, the total number of devices is typically much larger than the pilot length (N≫MN\gg M).

The received data follow the MMV model (1), where Y∈CM×Q\mathbf{Y}\in\mathbb{C}^{M\times Q} contains the observations over MM pilot symbols and QQ BS antennas, and A=(a1⋯aN)∈CM×N\mathbf{A}=(\mathbf{a}_1\cdots\mathbf{a}_N)\in\mathbb{C}^{M\times N} collects the device pilot sequences. The effective channel matrix X=(x~1⋯x~N)T∈CN×Q\mathbf{X}=(\tilde{\mathbf{x}}_1\cdots\tilde{\mathbf{x}}_N)^{\mathsf{T}}\in\mathbb{C}^{N\times Q} has rows

x~n=γnhn,γn=αnβnρn.(41)\tilde{\mathbf{x}}_n=\sqrt{\gamma_n}\mathbf{h}_n,\qquad\gamma_n=\alpha_n\beta_n\rho_n. \tag*{(41)}

where hn∈CQ\mathbf{h}_n\in\mathbb{C}^{Q} is the small-scale channel vector, αn∈{0,1}\alpha_n\in\{0,1\} is the activity indicator, βn>0\beta_n>0 is the large-scale fading coefficient (LSFC), and ρn\rho_n is the transmit power. Since only K≪NK\ll N devices are active, X\mathbf{X} is KK-row-sparse, with support M={n∈[N]:αn=1}\mathcal{M}=\{n\in[N]:\alpha_n=1\}. Under uncorrelated Rayleigh fading, the entries of hn\mathbf{h}_n are modeled as i.i.d. CN(0,1)\mathcal{CN}(0,1). Thus, each received antenna snapshot has covariance as in (2) and the corresponding scaled negative LLF is the CL objective in (3). JADCE is then performed using Algorithm 1 with any CL solver in Step 1.

The number of active devices ∣M∣=K\lvert\mathcal{M}\rvert=K is assumed to be fixed (non-random, deterministic variable) and known. Hence the estimated support M^\hat{\mathcal{M}} is obtained by the top-KK rule, yielding ∣M^∣=K\lvert\hat{\mathcal{M}}\rvert=K. Thus it is sufficient to use PMD as the performance metric since ∣M∖M^∣=∣M^∖M∣\lvert\mathcal{M}\setminus\hat{\mathcal{M}}\rvert=\lvert\hat{\mathcal{M}}\setminus\mathcal{M}\rvert, and thus (empirical) probability of false alarm (PFAP_{\mathrm{FA}}) contain the same information up to normalization.

Simulation setting follows that of subsection V-C, i.e., random Bernoulli matrix A\mathbf{A}, γn∼Unif⁡[−15,0]\gamma_n\sim\operatorname{Unif}[-15,0] in dB scale, σ2=1\sigma^2=1, and M\mathcal{M} (with ∣M∣=K\lvert\mathcal{M}\rvert=K) is drawn uniformly without replacement from {1,…,N}\{1,\ldots,N\} for each MC trial. Note that we assume no power-control, i.e., ρn=1\rho_n=1 in (41). To evaluate the JADCE framework in Algorithm 1, we compare different solvers for Step 1: the proposed CL-Hyb-bt, the EM solver of M-SBL [11], CLMM-2, CWO [20 Alg. 1], and CL-MP [15 Alg. 1]. For all methods, channel estimates are computed by Step 4 of Algorithm 1. For CL-MP, knowledge of KK is used to stop after KK selected atoms. We terminate each algorithm using (27) with δ=10−2\delta= 10^{-2}. This criterion is algorithm-independent: it is a function of the current iterate γk\gamma^{k} alone, and it vanishes if and only if γk\gamma^{k} satisfies the KKT conditions. Consequently, all methods are stopped once they attain the same level of proximity to the KKT conditions, which makes the comparison of running times fair. The maximum number of iterations is capped to 500 for all methods. The initial start is γ0=1\gamma^{0} = 1 for M-SBL and γ0=0\gamma^{0} = 0 for other methods.

First we study the impact of the pilot length MM, number of BS antennas QQ, and sparsity level KK on JADCE performance. Figure 2 plots PMDP_{\mathrm{MD}} versus QQ for K∈{20,30,40}K \in\{20, 30, 40\} and M=20,30,50M = 20, 30, 50 from bottom to top. We observe that CL-MP performs well for small KK, but degrades as KK increases, especially for M=20M = 20 and M=30M = 30. Overall, CL-Hyb-bt, CLMM-2, and CWO achieve nearly identical missed-detection performance, while EM-based M-SBL is slightly worse, with a more visible gap for short pilots, e.g., M=20M = 20.

Probability of miss detection versus the number of antennas for three pilot lengths and three sparsity levels

Figure 2. Probability of miss detection vs. the number of antennas QQ when M=20M = 20 (bottom panel), M=30M = 30 (middle panel) and M=50M = 50 (top panel). Number of MC trials: 10000; stopping tolerance for all algorithms: δ=10−2\delta= 10^{-2}.

Figure 3 reports the runtimes for M=20M = 20 and M=50M = 50 averaged over QQ and MC trials. CL-Hyb-bt is consistently faster than CWO, roughly by a factor of two. CL-MP is the fastest: it is up to about three and a half times faster for M=20M = 20 and K=20K = 20, and about twice as fast for M=20M = 20 and K=40K = 40. This is expected, since CL-MP is a greedy method that terminates after exactly KK iterations when KK is known. Finally, EM-based M-SBL is more than one order of magnitude slower than the proposed CL-Hyb-bt method, mainly because it requires several hundred iterations to converge.

Figure 4 shows the channel estimation performance for a pilot length of M=30M = 30. Here, we only compare CL-Hyb-bt and CL-MP. As can be observed, only in the settings where CL-MP provides slightly better AD performance (K=20K = 20 and M=30M = 30 as shown in the middle panel of Figure 2), its channel estimation performance is slightly better than that of CL-Hyb-bt. For K=40K = 40, CL-Hyb-bt provides clearly improved performance while for K=30K = 30 the differences in channel estimation performance are marginal. We have not included the CWO, CLMM-2, or EM approaches in this figure, as their curves overlap with that of CL-Hyb-bt.

Channel estimation NMSE versus the number of antennas $Q$

Figure 4. Channel estimation NMSE vs. the number of antennas QQ for different numbers of active devices KK when M=30M = 30. Number of MC trials: 10000; stopping tolerance: δ=10−2\delta= 10^{-2}.

Conclusions

We developed three parallel SCA algorithms for covariance learning in the M-SBL framework. CL-SCA preserves the convex part of the objective and linearizes the concave part, yielding closed-form parallel coordinate updates. CL-FP is derived from a projected fixed-point form of the KKT conditions and corresponds to SCA with a strictly convex quadratic surrogate. For both, we established sufficient decrease, an O(T−1/2)O(T^{-1/2}) best-iterate stationarity rate, and under standard step-size conditions, stationarity of all limit points. Furthermore, we derived a backtracking rule that retains this rate without step-size tuning. Local analysis showed that CL-SCA is more stable in the transient phase and CL-FP is faster near stationarity, which motivated the hybrid CL-Hyb.

Experiments on JADCE in GFRA showed that the proposed methods match the detection performance of CWO at substantially lower runtime and are more than an order of magnitude faster than M-SBL. CL-Hyb-bt converged fastest and gave the best accuracy–complexity trade-off among the CL methods. Future work includes joint estimation of γ\gamma and σ2\sigma^2, robust CL-SCA/-FP extensions to non-Gaussian losses, and unfolding the iterations into a network.

Appendix

Proof of Lemma 1

In [26 Eq. (27)], it was shown that if γn>0\gamma_n > 0, then setting ∇nℓ(γ)=0\nabla_n\ell(\gamma) = 0 yields the estimating equation

γn=Hn(γ),Hn(γ)=cnHScn(anHcn)2−1anHcn.(42)\gamma_n = H_n(\gamma),\qquad H_n(\gamma) = \frac{\mathbf{c}_n^{\mathrm{H}}\mathbf{S}\mathbf{c}_n}{(\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n)^2} - \frac{1}{\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n}. \tag*{(42)}

Applying the Sherman-Morrison formula3 to Σ\n=Σ−γnananH\boldsymbol{\Sigma}_{\backslash n} = \boldsymbol{\Sigma} - \gamma_n\mathbf{a}_n\mathbf{a}_n^{\mathrm{H}}, we notice that vectors cn\mathbf{c}_n and bn\mathbf{b}_n are parallel:

cn=bn1−γndn.(43)\mathbf{c}_n = \frac{\mathbf{b}_n}{1-\gamma_n d_n}. \tag*{(43)}

It follows from (43) that

anHcn=dn1−γndn⇒1anHcn=1dn−γn.(44)\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n = \frac{d_n}{1-\gamma_n d_n} \Rightarrow\frac{1}{\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n} = \frac{1}{d_n} - \gamma_n. \tag*{(44)}

Proof of Theorem 1

The convex term g(γ)=tr⁡(Σ−1S)g(\gamma) = \operatorname{tr}(\boldsymbol{\Sigma}^{-1}\mathbf{S}) can expressed as

g(γ)=tr⁡((γnananH+Σ\n)−1S)=tr⁡(Σ\n−1S)−γn1+γnanHΣ\n−1antr⁡(Σ\n−1ananHΣ\n−1S)=tr⁡(Σ\n−1S)−γnanHΣ\n−1SΣ\n−1an1+γnanHΣ\n−1an=tr⁡(Σ\n−1S)−γncnHScn1+γnanHcn.(45)\begin{aligned} g(\gamma) &= \operatorname{tr}\left((\gamma_n\mathbf{a}_n\mathbf{a}_n^{\mathrm{H}}+\boldsymbol{\Sigma}_{\backslash n})^{-1}\mathbf{S}\right) \\ &= \operatorname{tr}(\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{S})-\frac{\gamma_n}{1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{a}_n}\operatorname{tr}\left(\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{a}_n\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{S}\right) \\ &= \operatorname{tr}(\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{S})-\frac{\gamma_n\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{S}\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{a}_n}{1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{a}_n} \\ &= \operatorname{tr}(\boldsymbol{\Sigma}_{\backslash n}^{-1}\mathbf{S})-\frac{\gamma_n\mathbf{c}_n^{\mathrm{H}}\mathbf{S}\mathbf{c}_n}{1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n}. \tag*{(45)} \end{aligned}

where cn\mathbf{c}_n is defined in (8) (and also recall (43)). Note that in the second identity, we used the Sherman-Morrison formula. Then, by taking the derivative of (46), we can write en(γ)e_n(\gamma) as

en(γ)=−∇ng(γ)=cnHScn(1+γnanHcn)2.(46)e_n(\gamma)=-\nabla_n g(\gamma)=\frac{\mathbf{c}_n^{\mathrm{H}}\mathbf{S}\mathbf{c}_n}{(1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n)^2}. \tag*{(46)}

Let bnk=(Σk)−1an\mathbf{b}_n^k=(\boldsymbol{\Sigma}^k)^{-1}\mathbf{a}_n and cnk\mathbf{c}_n^k be defined as

cnk=(Σ\nk)−1an=(Σk−γnkananH)−1an.(47)\mathbf{c}_n^k=(\boldsymbol{\Sigma}_{\backslash n}^k)^{-1}\mathbf{a}_n=(\boldsymbol{\Sigma}^k-\gamma_n^k\mathbf{a}_n\mathbf{a}_n^{\mathrm{H}})^{-1}\mathbf{a}_n. \tag*{(47)}

i.e., as values of vectors (8) evaluated at γ=γk\gamma=\gamma^k where Σk=Adiag⁡(γk)AH+σ2I\boldsymbol{\Sigma}^k=A\operatorname{diag}(\gamma^k)A^{\mathrm{H}}+\sigma^2I. With the above notations and with the help of (46) and (9), we can write (21) compactly as

ℓn(γn∣γk)=−γn[cnk]HScnk1+γnanHcnk+γndnk(48)\ell_n(\gamma_n\mid\gamma^k)=-\frac{\gamma_n[\mathbf{c}_n^k]^{\mathrm{H}}\mathbf{S}\mathbf{c}_n^k}{1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n^k}+\gamma_n d_n^k \tag*{(48)}

where dnk=dn(γk)=anHbnkd_n^k=d_n(\gamma^k)=\mathbf{a}_n^{\mathrm{H}}\mathbf{b}_n^k. Above we ignored additive constants in (49) not dependent on γn\gamma_n. Taking the derivative of ℓn(γn∣γk)\ell_n(\gamma_n\mid\gamma^k) in (49) and setting it to zero yields the equation

0=∇nℓn(γn∣γk)=−[cnk]HScnk(1+γnanHcnk)2+dnk,0=\nabla_n\ell_n(\gamma_n\mid\gamma^k)=-\frac{[\mathbf{c}_n^k]^{\mathrm{H}}\mathbf{S}\mathbf{c}_n^k}{(1+\gamma_n\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n^k)^2}+d_n^k,

which has a single root:

γ~n(γk)=[cnk]HScnkdnk(anHcnk)2−1anHcnk.(49)\widetilde{\gamma}_n(\gamma^k)=\sqrt{\frac{[\mathbf{c}_n^k]^{\mathrm{H}}\mathbf{S}\mathbf{c}_n^k}{d_n^k(\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n^k)^2}}-\frac{1}{\mathbf{a}_n^{\mathrm{H}}\mathbf{c}_n^k}. \tag*{(49)}

This expression is not convenient due to the term cnkc_n^k as it requires the computation of all the inverses (Σnk)−1(\Sigma_n^k)^{-1} for each coordinate n=1,…,Nn=1,\ldots,N.

Equations (44) and (45) hold for all γ\gamma, so also at γ=γk\gamma=\gamma^k, meaning that

1anHcnk−1dnk=γnkand[cnk]HScnk(anHcnk)2=enk(dnk)2(50)\frac{1}{a_n^{\mathrm H}c_n^k}-\frac{1}{d_n^k}=\gamma_n^k \quad\text{and}\quad \frac{[c_n^k]^{\mathrm H}Sc_n^k}{(a_n^{\mathrm H}c_n^k)^2}=\frac{e_n^k}{(d_n^k)^2} \tag*{(50)}

where enk=en(γk)e_n^k=e_n(\gamma^k) by (17) is enk=[bnk]HSbnke_n^k=[b_n^k]^{\mathrm H}Sb_n^k. Then substituting (51) into (50) allows us to write the root in an equivalent form

γ~n(γk)=γnk+enk(dnk)3−1dnk=γnk+1dnk(enkdnk−1)(51)\widetilde{\gamma}_n(\gamma^k)=\gamma_n^k+\sqrt{\frac{e_n^k}{(d_n^k)^3}}-\frac{1}{d_n^k} =\gamma_n^k+\frac{1}{d_n^k}\left(\sqrt{\frac{e_n^k}{d_n^k}}-1\right) \tag*{(51)}

If γ~n≥0\widetilde{\gamma}_n\geq0, the unconstrained minimizer is feasible (optimal), while if γ~n<0\widetilde{\gamma}_n<0, then ∇nℓn(γn)>0\nabla_n\ell_n(\gamma_n)>0 for all γn>γ~n\gamma_n>\widetilde{\gamma}_n, in particular for all γn≥0\gamma_n\geq0. Thus the solution is γ^n(γk)=max⁡(γ~n(γk),0)\widehat{\gamma}_n(\gamma^k)=\max(\widetilde{\gamma}_n(\gamma^k),0) as given in (22).

Proof of Lemma 2

Recall from (11) that ∇nℓ(γ)=dn−en\nabla_n\ell(\gamma)=d_n-e_n while the update map of Theorem 1 can be expressed as

γ^n(γ)=[γn+endn3−1dn]+.\widehat{\gamma}_n(\gamma)=\left[\gamma_n+\sqrt{\frac{e_n}{d_n^3}}-\frac{1}{d_n}\right]_+.

Fix nn and suppose γ^(γ)=γ\widehat{\gamma}(\gamma)=\gamma. If γn>0\gamma_n>0, the projection in γ^n\widehat{\gamma}_n is inactive, so en/dn3=1/dn\sqrt{e_n/d_n^3}=1/d_n, i.e., en=dne_n=d_n, and thus ∇nℓ(γ)=0\nabla_n\ell(\gamma)=0. If γn=0\gamma_n=0, then γ^n=0\widehat{\gamma}_n=0 requires en/dn3≤1/dn\sqrt{e_n/d_n^3}\leq1/d_n, i.e., en≤dne_n\leq d_n, and hence ∇nℓ(γ)≥0\nabla_n\ell(\gamma)\geq0. Thus (12) holds. Conversely, if γn>0\gamma_n>0 and ∇nℓ(γ)=0\nabla_n\ell(\gamma)=0, then en=dne_n=d_n and (22) returns γ^n=γn\widehat{\gamma}_n=\gamma_n. If γn=0\gamma_n=0 and ∇nℓ(γ)≥0\nabla_n\ell(\gamma)\geq0, then en≤dne_n\leq d_n and (22) returns γ^n=0\widehat{\gamma}_n=0. Hence γ^(γ)=γ\widehat{\gamma}(\gamma)=\gamma.

Proof of Lemma 3

(i) For γ∈K0\gamma\in\mathcal{K}_0, dropping the nonnegative trace term gives log⁡∣Σ∣≤ℓ(γ)≤ℓ(γ0)\log|\Sigma|\leq\ell(\gamma)\leq\ell(\gamma^0). Since every eigenvalue of Σ\Sigma is at least σ2\sigma^2, ∣Σ∣≥λmax⁡(Σ)σ2(M−1)|\Sigma|\geq\lambda_{\max}(\Sigma)\sigma^{2(M-1)} and the bound λmax⁡(Σ)≤λˉ0\lambda_{\max}(\Sigma)\leq\bar{\lambda}_0 follows. Moreover, since

anH(Adiag⁡(γ)AH)an=∑mγm∣amHan∣2≥γn∥an∥4,a_n^{\mathrm H}(A\operatorname{diag}(\gamma)A^{\mathrm H})a_n=\sum_m\gamma_m|a_m^{\mathrm H}a_n|^2\geq\gamma_n\|a_n\|^4,

the Rayleigh quotient gives

λmax⁡(Σ)≥anHΣan∥an∥2≥σ2+γn∥an∥2.\lambda_{\max}(\Sigma)\geq\frac{a_n^{\mathrm H}\Sigma a_n}{\|a_n\|^2}\geq\sigma^2+\gamma_n\|a_n\|^2.

Thus, 0≤γn≤(λˉ0−σ2)/∥an∥20\leq\gamma_n\leq(\bar{\lambda}_0-\sigma^2)/\|a_n\|^2 on K0\mathcal{K}_0, so K0\mathcal{K}_0 is bounded, and it is closed by continuity of ℓ\ell, hence compact. Finally,

anHΣ−1an≥∥an∥2λmax⁡(Σ)≥amin⁡2λˉ0a_n^{\mathrm H}\Sigma^{-1}a_n\geq\frac{\|a_n\|^2}{\lambda_{\max}(\Sigma)}\geq\frac{a_{\min}^2}{\bar{\lambda}_0}

for all γ∈K0\gamma\in\mathcal{K}_0 and all nn.

(ii) Differentiating (11) once more, with Ψ=AHΣ−1A\Psi=A^{\mathrm H}\Sigma^{-1}A and Φ=AHΣ−1SΣ−1A\Phi=A^{\mathrm H}\Sigma^{-1}S\Sigma^{-1}A (both positive semidefinite, [Ψ]nn=dn[\Psi]_{nn}=d_n, [Φ]nn=en[\Phi]_{nn}=e_n), a direct computation gives

[∇2ℓ(γ)]nm=−∣[Ψ]nm∣2+2Re⁡{[Ψ]nm[Φ]nm∗}(52)[\nabla^2\ell(\gamma)]_{nm}=-|[\Psi]_{nm}|^2+2\operatorname{Re}\{[\Psi]_{nm}[\Phi]_{nm}^*\} \tag*{(52)}

i.e., ∇2ℓ=2Re⁡(Ψ⊙Φ∗)−Ψ⊙Ψ∗\nabla^2\ell=2\operatorname{Re}(\Psi\odot\Phi^*)-\Psi\odot\Psi^*. By the triangle inequality and ∥Re⁡(C)∥2≤∥C∥2\|\operatorname{Re}(C)\|_2\leq\|C\|_2 (note that the spectral norm is invariant to the sign of its argument, so the minus sign in front of Ψ⊙Ψ∗\Psi\odot\Psi^* is irrelevant),

∥∇2ℓ(γ)∥2≤2∥Ψ⊙Φ∗∥2+∥Ψ⊙Ψ∗∥2.(53)\|\nabla^2\ell(\gamma)\|_2\leq2\|\Psi\odot\Phi^*\|_2+\|\Psi\odot\Psi^*\|_2. \tag*{(53)}

Each term is now bounded by the Schur-multiplier inequality: for Hermitian CC and positive semidefinite BB, ∥C⊙B∥2≤(max⁡n[B]nn)∥C∥2\|C\odot B\|_2\leq(\max_n[B]_{nn})\|C\|_2. Applying it with (C,B)=(M,N∗)(C,B)=(M,N^*) and (C,B)=(Ψ,Φ∗)(C,B)=(\Psi,\Phi^*) (both Φ∗\Phi^* and Ψ∗\Psi^* are positive semidefinite), and using ∥CB∥2≤∥C∥2∥B∥2\|CB\|_2\leq\|C\|_2\|B\|_2 and Σ⪰σ2I\Sigma\succeq\sigma^2I, which holds for every γ∈R≥0N\gamma\in\mathbb{R}_{\geq0}^N, and gives

∥Ψ∥2≤∥A∥22σ2,[Ψ]nn≤∥an∥2σ2,[Φ]nn≤∥S∥2∥an∥2σ4,\|\Psi\|_2\leq\frac{\|A\|_2^2}{\sigma^2},\qquad [\Psi]_{nn}\leq\frac{\|a_n\|^2}{\sigma^2},\qquad [\Phi]_{nn}\leq\frac{\|S\|_2\|a_n\|^2}{\sigma^4},

yields

∥∇2ℓ(γ)∥2≤2∥S∥2amax⁡2σ4⋅∥A∥22σ2+amax⁡2σ2⋅∥A∥22σ2=L∇\|\nabla^2\ell(\gamma)\|_2\leq 2\frac{\|S\|_2a_{\max}^2}{\sigma^4}\cdot\frac{\|A\|_2^2}{\sigma^2} +\frac{a_{\max}^2}{\sigma^2}\cdot\frac{\|A\|_2^2}{\sigma^2} =L_{\nabla}

uniformly on R≥0N\mathbb{R}_{\geq0}^N.

Proof of Theorem 2

First we claim that for every γ∈R≥0N\gamma\in\mathbb{R}_{\geq0}^N, with p=γ^(γ)−γ\mathbf{p}=\widehat{\gamma}(\gamma)-\gamma and dn=dn(γ)d_n=d_n(\gamma),

∇ℓ(γ)Tp≤−∑n=1Ndn2pn2⟺∑n=1N(∇nℓ(γ)pn−dn2pn2)≤0(54)\nabla\ell(\gamma)^{\mathsf T}\mathbf{p}\leq-\sum_{n=1}^{N}d_n^2p_n^2 \Longleftrightarrow \sum_{n=1}^{N}\left(\nabla_n\ell(\gamma)p_n-d_n^2p_n^2\right)\leq0 \tag*{(54)}

Indeed, write en=en(γ)≥0e_n=e_n(\gamma)\geq0, rn=en/dnr_n=e_n/d_n (recall dn>0d_n>0), and sn=1+dnpns_n=1+d_np_n. Since ∇nℓ(γ)=dn−en=dn(1−rn)\nabla_n\ell(\gamma)=d_n-e_n=d_n(1-r_n) and dnpn=sn−1d_np_n=s_n-1, each summand in (55) satisfies

(dn−en)pn+dn2pn2=(1−rn)(sn−1)+(sn−1)2=(sn−1)(sn−rn),(d_n-e_n)p_n+d_n^2p_n^2=(1-r_n)(s_n-1)+(s_n-1)^2 =(s_n-1)(s_n-r_n),

which is nonpositive whenever sns_n lies between rnr_n and 11. From the update γ^n=[γn+en/dn3−1/dn]+\widehat{\gamma}_n=[\gamma_n+\sqrt{e_n/d_n^3}-1/d_n]_+, we notice that pn=γ^n−γn={en/dn3−1/dn,−γn}p_n=\widehat{\gamma}_n-\gamma_n=\{\sqrt{e_n/d_n^3}-1/d_n,-\gamma_n\}. Multiplying by dn>0d_n>0 and adding one gives

sn=1+dnpn=max⁡{rn,1−γndn},s_n=1+d_np_n=\max\{\sqrt{r_n},1-\gamma_nd_n\},

where the first branch corresponds to an inactive projection and the second to γ^n=0\widehat{\gamma}_n=0. If sn=rns_n=\sqrt{r_n}, then sns_n is the geometric mean of rnr_n and 11 and hence lies between them. Otherwise rn<sn=1−γndn≤1\sqrt{r_n}<s_n=1-\gamma_nd_n\leq1, so that rn≤rn<sn≤1r_n\leq\sqrt{r_n}<s_n\leq1. Summing over nn proves (55). Furthermore, for γk∈K0\gamma^k\in\mathcal{K}_0, since dn(γk)≥d‾d_n(\gamma^k)\geq\underline{d} by Lemma 3 gives ∇ℓ(γk)Tpk≤−d‾ 2∥pk∥22\nabla\ell(\gamma^k)^{\mathsf T}\mathbf{p}^k\leq-\underline{d}^{\,2}\|\mathbf{p}^k\|_2^2.

Assume γk∈K0\gamma^k\in\mathcal{K}_0. Since γk+1=γk+ηkpk\gamma^{k+1}=\gamma^k+\eta^k\mathbf{p}^k, with pk=γ^(γk)−γk\mathbf{p}^k=\widehat{\gamma}(\gamma^k)-\gamma^k, lies on the segment between γk\gamma^k and γ^(γk)\widehat{\gamma}(\gamma^k), the quadratic upper bound (29) gives

ℓ(γk+1)≤ℓ(γk)+ηk∇ℓ(γk)Tpk+L∇2(ηk)2∥pk∥22≤ℓ(γk)−ηk(d‾ 2−L∇ηk2)∥pk∥22≤ℓ(γk)−d‾ 22ηk∥pk∥22,(55)\begin{aligned} \ell(\gamma^{k+1})\leq\ell(\gamma^k)+\eta^k\nabla\ell(\gamma^k)^{\mathsf T}\mathbf{p}^k+\frac{L_{\nabla}}{2}(\eta^k)^2\|\mathbf{p}^k\|_2^2 \\ &\leq\ell(\gamma^k)-\eta^k\left(\underline{d}^{\,2}-\frac{L_{\nabla}\eta^k}{2}\right)\|\mathbf{p}^k\|_2^2 \\ &\leq\ell(\gamma^k)-\frac{\underline{d}^{\,2}}{2}\eta^k\|\mathbf{p}^k\|_2^2, \tag*{(55)} \end{aligned}

where the 2nd inequality uses previous assertion, and the last uses ηk≤d‾ 2/L∇\eta^k\leq\underline{d}^{\,2}/L_{\nabla}. Since γ0∈K0\gamma^0\in\mathcal{K}_0, (56) also proves inductively that every iterate remains in K0\mathcal{K}_0. Note that summing (33) over k=0,…,T−1k=0,\ldots,T-1 and telescoping yields

d22∑k=0T−1ηk∥pk∥22≤ℓ(γ0)−ℓ(γT)≤ℓ(γ0)−ℓinf⁡,(56)\frac{d^2}{2}\sum_{k=0}^{T-1}\eta^k\lVert p^k\rVert_2^2 \le\ell(\gamma^0)-\ell(\gamma^T)\le\ell(\gamma^0)-\ell_{\inf}, \tag*{(56)}

and bounding the weighted average from below by its smallest term gives (34). For γ0=0\gamma^0=0, note ℓ(0)=tr⁡(S)/σ2+Mlog⁡σ2\ell(0)=\operatorname{tr}(\mathbf{S})/\sigma^2+M\log\sigma^2 and ℓinf⁡≥Mlog⁡σ2\ell_{\inf}\ge M\log\sigma^2. Thus ℓ(0)−ℓinf⁡≤tr⁡(S)/σ2\ell(0)-\ell_{\inf}\le\operatorname{tr}(\mathbf{S})/\sigma^2. If inf⁡kηk>0\inf_k\eta^k>0, the summability of ηk∥pk∥22\eta^k\lVert p^k\rVert_2^2 forces ∥pk∥2→0\lVert p^k\rVert_2\to0. Every accumulation point γ⋆\gamma^\star then satisfies γ^(γ⋆)=γ⋆\widehat{\gamma}(\gamma^\star)=\gamma^\star by continuity of the update map, and is KKT-stationary by Lemma 2.

Proof of Theorem 3

We claim that for every γ∈R≥0N\gamma\in\mathbb{R}_{\ge0}^N, with q=[H(γ)]+−γ\mathbf{q}=[H(\gamma)]_+-\gamma and gn=[∇ℓ(γ)]n=dn−eng_n=[\nabla\ell(\gamma)]_n=d_n-e_n,

∇ℓ(γ)Tq≤−∑n=1Ndn2qn2.(57)\nabla\ell(\gamma)^{\mathsf{T}}\mathbf{q}\le-\sum_{n=1}^{N}d_n^2q_n^2. \tag*{(57)}

Fix nn. If the projection is inactive, then qn=Hn(γ)−γn=−gn/dn2q_n=H_n(\gamma)-\gamma_n=-g_n/d_n^2 by (14), so gnqn=−gn2/dn2=−dn2qn2g_nq_n=-g_n^2/d_n^2=-d_n^2q_n^2, with equality. If the projection is active and γn>0\gamma_n>0, then qn=−γnq_n=-\gamma_n and Hn(γ)<0H_n(\gamma)<0, i.e., gn>γndn2>0g_n>\gamma_nd_n^2>0, hence gnqn=−γngn<−γn2dn2=−dn2qn2g_nq_n=-\gamma_ng_n<-\gamma_n^2d_n^2=-d_n^2q_n^2. If the projection is active and γn=0\gamma_n=0, then qn=0q_n=0 and the term vanishes. Summing over nn proves (57), and for γ∈K0\gamma\in\mathcal{K}_0 invoking dn(γ)≥dd_n(\gamma)\ge d gives ∇ℓ(γ)Tq≤−d2∥q∥22\nabla\ell(\gamma)^{\mathsf{T}}\mathbf{q}\le-d^2\lVert\mathbf{q}\rVert_2^2.

Proceed by induction, assume γk∈K0\gamma^k\in\mathcal{K}_0 (true for k=0k=0). Since γk+1\gamma^{k+1} lies on the segment [γk,[H(γk)]+]⊂R≥0N[\gamma^k,[H(\gamma^k)]_+]\subset\mathbb{R}_{\ge0}^N, on which ∇ℓ\nabla\ell is L∇L_{\nabla}-Lipschitz by Lemma 3(ii), the descent lemma and (57) with dn(γk)≥dd_n(\gamma^k)\ge d give

ℓ(γk+1)≤ℓ(γk)+ηk∇ℓ(γk)Tqk+L∇2(ηk)2∥qk∥22≤ℓ(γk)−ηk(d2−L∇ηk2)∥qk∥22≤ℓ(γk)−d22ηk∥qk∥22,\begin{aligned} \ell(\gamma^{k+1})\le\ell(\gamma^k)+\eta^k\nabla\ell(\gamma^k)^{\mathsf{T}}\mathbf{q}^k+\frac{L_{\nabla}}{2}(\eta^k)^2\lVert\mathbf{q}^k\rVert_2^2 \\ &\le\ell(\gamma^k)-\eta^k\left(d^2-\frac{L_{\nabla}\eta^k}{2}\right)\lVert\mathbf{q}^k\rVert_2^2 \\ &\le\ell(\gamma^k)-\frac{d^2}{2}\eta^k\lVert\mathbf{q}^k\rVert_2^2, \end{aligned}

where the last step uses ηk≤d2/L∇\eta^k\le d^2/L_{\nabla}. In particular ℓ(γk+1)≤ℓ(γk)≤ℓ(γ0)\ell(\gamma^{k+1})\le\ell(\gamma^k)\le\ell(\gamma^0), so γk+1∈K0\gamma^{k+1}\in\mathcal{K}_0, closing the induction and proving (37). The rest follows as in proof of Theorem 2.

References

  1. [1]M. F. Duarte and Y. C. Eldar, “Structured compressed sensing: From theory to applications,” IEEE Trans. Signal Process., vol. 59, no. 9, pp. 4053–4085, 2011.DOI
  2. [2]J. A. Tropp, A. C. Gilbert, and M. J. Strauss, “Algorithms for simultaneous sparse approximation. Part I: greedy pursuit,” Signal Processing, vol. 86, no. 8, pp. 572–588, 2006.
  3. [3]J. A. Tropp, “Algorithms for simultaneous sparse approximation. Part II: convex relaxation,” Signal Processing, vol. 86, pp. 589–602, 2006.DOI
  4. [4]J. Chen and X. Huo, “Theoretical results on sparse representations of multiple-measurement vectors,” IEEE Trans. Signal Process., vol. 54, no. 12, pp. 4634–4643, 2006.DOI
  5. [5]Y. C. Eldar and H. Rauhut, “Average case analysis of multichannel sparse recovery using convex relaxation,” IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 505–519, 2010.arxiv.org/abs/0904.0494
  6. [6]J. D. Blanchard, M. Cermak, D. Hanle, and Y. Jin, “Greedy algorithms for joint sparse recovery,” IEEE Trans. Signal Process., vol. 62, no. 7, pp. 1694–1704, 2014.DOI
  7. [7]M. E. Tipping, “Sparse bayesian learning and the relevance vector machine,” J. Mach. Learn. Res., vol. 1, no. Jun, pp. 211–244, 2001.
  8. [8]D. P. Wipf and B. D. Rao, “Sparse bayesian learning for basis selection,” IEEE Trans. Signal Process., vol. 52, no. 8, pp. 2153–2164, 2004.DOI
  9. [9]G. Scutari, F. Facchinei, P. Song, D. P. Palomar, and J.-S. Pang, “Decomposition by partial linearization: Parallel optimization of multi-agent systems,” IEEE Trans. Signal Process., vol. 62, no. 3, pp. 641–656, 2013.DOI
  10. [10]S. F. Cotter, B. D. Rao, K. Engan, and K. Kreutz-Delgado, “Sparse solutions to linear inverse problems with multiple measurement vectors,” IEEE Trans. Signal Process., vol. 53, no. 7, pp. 2477–2488, 2005.DOI
  11. [11]D. P. Wipf and B. D. Rao, “An empirical Bayesian strategy for solving the simultaneous sparse approximation problem,” IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3704–3716, 2007.DOI
  12. [12]M. Esfandiari, E. Olila, and D. P. Palomar, “Majorization-minimization covariance learning algorithm for sparse signal recovery,” in 2026 34th European Signal Processing Conference (EUSIPCO), 2026, pp. 1–5.
  13. [13]M. Al-Shoukairi, P. Schiter, and B. D. Rao, “A GAMP-based low complexity sparse Bayesian learning algorithm,” IEEE Trans. Signal Process., vol. 66, no. 2, pp. 294–308, 2017.DOI
  14. [14]A. Hashemi, C. Cai, Y. Gao, S. Ghosh, K.-R. Müller, S. S. Nagarajan, and S. Haufe, “Joint learning of full-structure noise in hierarchical bayesian regression models,” IEEE Trans. Med. Imag., vol. 43, no. 2, pp. 610–624, 2022.DOI
  15. [15]L. Marata, E. Olila, and H. Alves, “Activity detection for massive random access using covariance-based matching pursuit,” IEEE Trans. Veh. Technol., vol. 74, no. 11, pp. 17 292–17 303, 2025.arxiv.org/abs/2405.02741
  16. [16]R. R. Pote and B. D. Rao, “Theory and practice of light-weight sequential sbl algorithm: An alternative to OMP,” IEEE Trans. Signal Process., 2025.DOI
  17. [17]L. Liu, E. G. Larsson, W. Yu, P. Popovski, C. Stefanovic, and E. De Carvalho, “Sparse signal processing for grant-free massive connectivity: A future paradigm for random access protocols in the internet of things,” IEEE Signal Process. Mag., vol. 35, no. 5, pp. 88–99, 2018.DOI
  18. [18]L. Liu and W. Yu, “Massive connectivity with massive MIMO-Part I: Device activity detection and channel estimation,” IEEE Trans. Signal Process., vol. 66, no. 11, pp. 2933–2946, 2018.DOI
  19. [19]Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection for massive connectivity,” IEEE Signal Process., vol. 66, no. 7, pp. 1890–1904, 2018.DOI
  20. [20]A. Fengler, S. Haghightashoor, P. Jung, and G. Caire, “Non-Bayesian activity detection, large-scale fading coefficient estimation, and unsourced random access with a massive MIMO receiver,” IEEE Trans. Inf. Theory, vol. 67, no. 5, pp. 2925–2951, 2021.DOI
  21. [21]Z. Chen, F. Sohrabi, Y.-F. Liu, and W. Yu, “Covariance based joint activity and data detection for massive random access with massive MIMO,” in ICC 2019, 2019, pp. 1–6.DOI
  22. [22]——, “Phase transition analysis for covariance-based massive random access with massive MIMO,” IEEE Trans. Inf. Theory, vol. 68, no. 3, pp. 1696–1715, 2021.
  23. [23]X. Wang, E. Olila, and S. A. Vorobyov, “Robust activity detection for massive random access,” IEEE Signal Process., vol. 73, pp. 3513–3527, 2025.
  24. [24]B. Tan and Y. Cui, “Fast MLE and MAPE-based device activity detection for grant-free access via PSCA and PSCA-Net,” IEEE Trans. Wireless Commun., vol. 24, no. 6, pp. 5066–5083, 2025.DOI
  25. [25]E. Olila, M. Esfandiari, and D. P. Palomar, “Joint activity detection and channel estimation for massive random access using SBL and SCA,” in 2026 IEEE SPAWC, Athens, Greece, Sep 6–9, 2026, pp. 1–5.
  26. [26]T. Yardibi, J. Li, P. Stoica, M. Xue, and A. B. Baggeroer, “Source localization and sensing: A nonparametric iterative adaptive approach based on weighted least squares,” IEEE Trans. Aerosp. Electron. Syst., vol. 46, no. 1, pp. 425–443, 2010.
  27. [27]D. Wipf and S. Nagarajan, “Beamforming using the relevance vector machine,” in Proceedings of the 24th international conference on Machine learning, 2007, pp. 1023–1030.DOI
  28. [28]G. Scutari and Y. Sun, “Parallel and distributed successive convex approximation methods for big-data optimization,” in Multi-Agent Optimization: Cetraro, Italy 2014. Springer, 2018, pp. 141–308.arxiv.org/abs/1805.06963
  29. [30]D. P. Bertsekas, Nonlinear Programming, 2nd ed. Belmont, MA: Athena Scientific, 1999.
  30. [31]Y. Sun, P. Babu, and D. P. Palomar, “Robust estimation of structured covariance matrix for heavy-tailed elliptical distributions,” IEEE Trans. Signal Process., vol. 64, no. 14, pp. 3576–3590, 2016.

Paper details

vlnc:W_xk7fzp47
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents