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 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 follow the generative model , , where is a fixed (known) overcomplete matrix () and is an unobserved zero mean white noise random vector, i.e., . Matrix is called the dictionary or measurement matrix, and its column vectors are referred to as atoms. The unobserved random signal vectors , are assumed to be jointly sparse, i.e., most of their elements are zero, and all -s share the same support. Letting denote the matrix of measurement vectors, we can write the model in matrix form as
where matrices and contain the signal and noise vectors as columns, respectively. Given signals, the key assumption underlying the MMV model is that the signal matrix is -rowsparse, i.e., at most rows of contain non-zero entries. The row support of is the index set of rows containing non-zero elements:
where . Since is -rowsparse, i.e., , joint estimation of -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 and possibly , given only the data , the dictionary , and possibly the sparsity level .
In Sparse Bayesian Learning (SBL) [7], [8], the signal vectors -s are modeled as i.i.d. circular Gaussian random vectors with independent elements and zero mean. Additionally, -s are assumed to be statistically independent of the noise vectors -s. The noise vectors are assumed to be i.i.d. Gaussian with . This implies that , where the positive definite Hermitian (PDH) covariance matrix has the form
where the signal covariance matrix is a diagonal matrix and is a vector of signal powers with only non-zero elements, i.e., . We assume to be known. In many applications, the noise variance 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 . We let
denote the probability density function (up to an irrelevant normalizing constant) of the multivariate circular Gaussian distribution with mean vector and covariance matrix . Here, denotes the matrix determinant. Then, the scaled negative LLF of the data is
where is a convex continuously differentiable function in and is a concave continuously differentiable function, defined as,
where denotes the matrix trace, and is the sample covariance matrix (SCM) of the data. We then study the nonconvex optimization problem
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 as deterministic and promote row sparsity through -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 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.
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 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 , matching one cycle of CWO [20 Alg. 1], and one iteration of CL-MP [15 Alg. 1], M-SBL [11] or CLMM [12].
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.
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 best-iterate stationarity rate after 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).
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.
We provide a unified fixed-point view of CL-SCA, CL-FP, CLMM, and EM as updates (Table I), showing that the fixed points of the first three are exactly the KKT points, whereas EM’s vanishing multiplier at creates spurious fixed points on the boundary.
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

Figure 1. Convergence for , , , (20 MC runs) Top: median objective gap . Bottom: normalized running-minimum loss for representative runs, drawn until reaching the target (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 (x-axis) to at the bottom panel.

Figure 3. Running time versus the number of active devices for (a) and (b), averaged over and 1000 MC trials per . All optimization-based methods use the stopping criterion (27) with .
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 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 , , , , and denote its Hermitian transpose, trace, determinant, and spectral norm. The entry in the th row and th column of is denoted by , and its largest eigenvalue is denoted by . The Euclidean norm of a vector is denoted by , and denotes the element-wise projection of onto the nonnegative orthant. The symbol denotes the Hadamard (element-wise) product. denotes the indicator function.
First order characterization of the problem
Write
as the covariance matrix of when the contribution from the th signal is removed. Define
for . Note that and depend on through but to keep notations short, we have dropped this notation. Write as a shorthand notation. Then the coordinate derivatives and of functions and are
and note that as and for all . For notational simplicity we often write and , dropping the dependency of . With the above definitions, the th coordinate function of the gradient of can be expressed as:
The KKT condition for the constrained case is
Next result characterizes the solution to (6).
Lemma 1. Let and let have coordinate functions
Then satisfies the KKT conditions (12) if and only if it verifies the fixed-point equation
In particular, every local minimizer of over , and hence the minimizer , verifies (15), and on the support the projection is inactive, so .
Proof. See Appendix A.
The CWO algorithm is closely related with fixed point map. Namely, in cycle , coordinate is updated by minimizing
subject to . The minimizer is [26]:
where .
M-SBL
Under the Gaussianity assumption, the posterior distribution of the sources factorizes across measurement vectors as
The posterior depends on the conditional mean vectors of -s as well as their joint posterior covariance matrix, , defined by
where 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 , one estimates them directly from the data by minimizing the marginal Type-II scaled negative LLF in (3), thereby obtaining . Subsequently, the posterior distribution is computed via the plug-in principle as , and
will serve as the empirical Bayes estimates of the posterior mean vectors and covariance matrix, respectively, where and . 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: , , , or .
Minimize over to obtain using an algorithm of your choice.
Compute estimate of activity indices using either the threshold rule in (19) or the -top rule in (20).
Prune the signal power estimates as .
Compute the sparse signal matrix as , with and .
Output: (or support ), , .
The EM-algorithm
In step 1 of Algorithm 1, the M-SBL constructs an EM algorithm to minimize by treating , , as the complete data. It is well-known that the EM algorithm suffers from slow convergence, making M-SBL impractical for applications where 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 denote the value of at iteration, and write
i.e., as values the coordinate derivative functions defined in (9) and (10) evaluated at , respectively. Also, write and for the values of the posterior mean and covariance matrix at . With the above definitions in mind, we can write and , and the M-step [11 eq. (18)] can be expressed in a simpler form as
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., is proposed in [11]). Since by (11), we can interpret (18) as a gradient descent method with coordinate-wise adaptive step size .
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 which matches the natural parameter space of the underlying probabilistic model, so the solution in M-step is strictly positive. If (i.e., component of the initial start is strictly positive), then the M-step yields for all . Conversely, if , then for all , 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 , although its components may become arbitrarily small as the iterations proceed.
Sparsifying the solution
The (local) minimizer of 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 , where the activity indices are obtained using either of the following rules:
The threshold-rule:
where is a fixed threshold.
The top -rule:
where the sparsity level is assumed to be known. The latter requires knowledge (or an estimate) of 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, , and the resulting updates are performed iteratively and in parallel.
CL-SCA algorithm
At iteration , by following the SCA framework and linearizing the concave term , the functions to be minimized by the agents in parallel are given as
where is defined in (17). The solution is given below.
Theorem 1. For , the minimizer of the convex function over is
where and 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 , 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 : , , , step-size sequence , . | |
| Initialize: , , . | |
| repeat | |
| 1 | Compute and . |
| 2 | For all solve in parallel: where and . |
| 3 | , where . |
| 4 | |
| 5 | until or |
| Output : . |
Table 2.
where the step-size is introduced to control the length of the update along the update direction
The step-size sequence can be conveniently chosen as a diminishing sequence, verifying and [9], [28]. However, our convergence analysis suggests a backtracking algorithm that certifies the best-iterate stationary rate. We use as default initial start. The CL-SCA algorithm is tabulated in algorithm 2.
Lemma 2. A vector , satisfies the KKT conditions (12) if and only if it is a fixed point of the update map of Theorem 1, i.e., .
Proof. See Appendix C.
Lemma 1 and Lemma 2 thus provide two fixed-point characterizations of stationarity. Lemma 1 and the SCA update map of Theorem 1 characterize the same set:
This is no coincidence: recalling , , and writting , the unprojected displacements of the two maps are
thus they differ only by the positive factor . In other words, both maps move every coordinate in the same direction determined by the sign of , i.e., of and vanish simultaneously. As termination criterion we use
where with some appropriate convergence threshold (default ). Note that (27) vanishes if and only if the KKT conditions (12) hold for . 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 does not incur any extra costs, since and required by are reused (not recomputed) in Step 2. This is true for all methods considered.
The computational complexity of step 1 is while the computational complexity of step 2 is . Computational complexity of Step 3–4 are . Since , the complexity of one iteration of CL-SCA algorithm is . 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 (the SCM) with the computational complexity of . Thus, the overall complexities of CL-SCA, CLMM, EM algorithm of M-SBL and CWO are , where is the number of iterations until convergence. Note that CL-MP is a greedy CL-based approach, terminated after iterations (when is known), and hence its overall complexity is . Thus CL-MP provides faster computations only in the ideal case when is known and . We provide convergence analysis of the CL-SCA (and CL-FP) algorithm in subsection IV-B.
Stationarity rate of CL-SCA
Define and and note that both scalars are well-defined strictly positive constants as for all . We say that is Lipschitz continuous on a set with constant if
Since on an open set containing , is twice continuously differentiable there, and for convex a sufficient condition for (28) is for (see e.g., [29, Lemma 1.2.2]). Property (28) implies the quadratic upper bound [30 Prop. A.24]:
which is used later in Theorem 2. The next lemma collects the two constants that govern the step-size rule.
Lemma 3. Let
denote the initial sublevel set. Then:
(i) is compact, and with for all . Consequently
where .
(ii) is Lipschitz continuous on all of with constant
Proof. See Appendix D.
We can now state the sufficient decrease and stationarity rate. Note that as .
Theorem 2. If for all , where
then the CL-SCA iterates (23) satisfy and
where and are as in Lemma 3. Consequently, for every ,
If, in addition, , then and every accumulation point of is KKT-stationary.
Proof. See Appendix E.
For a constant step size , (34) yields the best-iterate stationarity rate , matching the canonical rate of first-order methods on smooth nonconvex problems. In contrast, diminishing schedules degrade the certified rate to for and for , since then grows only as or . Moreover, they do not meet the condition 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) in (32), which maximizes the guaranteed decrease in (33). However, depends on and , which are not known a priori; computable bounds on them give an admissible but overly conservative step size.
Since 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 , and halve a trial step until
Since , every accepted step satisfies the sufficient-decrease inequality (33), and the test is passed by every . Hence the loop terminates after at most halvings, the accepted steps satisfy , and Theorem 2 applies in full, including the rate and , without or having to be known. Rather than restarting from 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 of Lemma 1 suggests the iteration . The first observation is that this map is a diagonally scaled projected gradient step:
where defined by (9). This result easily follows because the quadratic problem in (35) is separable in coordinates and its th coordinate minimizer is , precisely the fixed point map . Thus we define damped fixed point iteration as
The damped iteration (36) is itself a parallel SCA scheme: it minimizes, per coordinate, the strongly convex quadratic surrogate in (35) (curvature , gradient matching at ), whereas CL-SCA minimizes the nonquadratic surrogate 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 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 , so the rate guarantee is unaffected. The rule is also inexpensive: evaluating at a trial point requires the Cholesky factor of 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 , where is a given constant, and . We set and as default values.
To conclude, a constant step size attains the best worst-case rate only if is tuned close to the unknown constant . The backtracking rule requires no tuning, retains the rate (its steps satisfy ), 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 and let , , and be as in Lemma 3 and Theorem 2. If , then the iterates of (36) satisfy and
and consequently the rate bound (34), the best-iterate rate for constant , and when , the convergence 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 at the current iterate and have curvature (CL-SCA) and (CL-FP) at a stationary point; the CL-FP surrogate is quadratic, hence strongly convex with modulus on . They also share identical guarantees: (a) the same safe damping bound , (b) the same sufficient-decrease constant , (c) the same rate, and (d) the same per-iteration computational complexity. Their residuals, in (24) and in (36), respectively, verify
whenever neither projection is active. Thus, always holds. The residual norms, and , are equivalent stationarity measures: with . The two maps differ, however, in their local behavior near a KKT point : there 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
where and . Therefore, the undamped SCA map is locally convergent whenever the eigenvalues of the scaled Hessian lie in , while the undamped FP map requires the twice-smaller interval : CL-SCA has double the local stability margin, where the full step 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 and as Theorem 2, the safe constant step size , 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 (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.
| multiplier | residual | |
| EM of M-SBL (18) | ||
| CL-FP (13) | ||
| CL-SCA (22) | ||
| CLMM (39) |
Table 1. The four update maps as one family: , before projection onto .
Relation to the MM-based algorithm
The CLMM [12] method majorizes both terms of : the concave log (1) by the same linearization used in (21), and the convex 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 . This requires a majorization constant (denoted in [12] but renamed here to avoid a clash with step size ). After some algebra, and using notations in this paper, the CLMM update rewrites as
which is precisely (25) with the multiplier replaced by . Together with (18) and (13), all four update maps considered in this paper are then members of a single family, each of the form before projection, as summarized in tbl:I.
The residual vanishes exactly at , i.e. at , so on the support all four maps stop at the same points. At the boundary they do not, and the multiplier is what decides it. For CL-FP, CL-SCA and CLMM the multiplier is bounded away from zero (, , and , respectively), so a coordinate at is left unchanged only when , 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 , in contrast, vanishes at , so every coordinate with is fixed irrespective of the sign of : the fixed points of (18) strictly contain the KKT points, the spurious ones being those with and . 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 , so both are of the form plus a positive quantity, and since gives while ,
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 : the damping of CLMM is built into its majorizer, and is its price. The gap in (40) is exactly the looseness of . With the choice used in [12] and equal-norm atoms, , starting from , the CLMM step is thus shorter than the CL-SCA step by a factor . This does not translate into a proportional loss of speed, however, since (39) is multiplicative in the shifted variable , for which it reads . A conservative 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 of (21), since both methods linearize the same concave term. They differ only in the convex term , 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 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 , i.e., (22) with , not the damped iteration of Algorithm 2.
Convergence analysis and a new Hybrid method
Convergence is assessed with two complementary measures. The objective gap , where 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 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 , 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 . We also consider a variant CLMM-2 which uses (instead of the Frobenius norm) which by (40) and 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 and , CL-SCA-fss uses and CL-FP-fss uses . These were hand-tuned step-sizes (chosen as large as possible) that worked for our set-up with dimension . 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 acts locally like an SCA step ; 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, is a random Bernoulli matrix, with elements generated as , so that while the support is drawn uniformly without replacement from . The noise variance is fixed and the -nonzero signal powers of the Gaussian sources are uniformly distributed between in dB scale and generated independently for each trial.
Figure 1 reports both measures for , , , and over 20 MC runs. The per-run target 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 within 250 iterations; CLMM decays faster but still slowly (gap at ) and does not reach the target either. CLMM-2 improves over CLMM and achieves gap at . By contrast, the fixed-step and backtracking variants drive the gap below within 55 iterations, and the diminishing-step variants within 100.
Second, the fixed step size gives a substantial gain over the diminishing schedule. At the median gap of CL-SCA-fss is against for CL-SCA-dss, and that of CL-FP-fss is against for CL-FP-dss, reductions by factors of 14 and 10 that exceed two orders of magnitude by . 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 the CL-SCA-fss gap is an order of magnitude smaller than that of CL-FP-fss ( versus 3.8), whereas from the ordering reverses. This agrees with the relation between their displacements: when the projection is inactive, the FP step equals times the SCA step. Far from stationarity can be large, so the FP proposal is more aggressive and needs a smaller damping factor ( versus 0.6); near stationarity 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 its gap is , against for CL-FP-fss and 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 . At the gaps of CL-SCA-bt and CL-Hyb-bt are and , 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 () by and , respectively, against 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 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 ( ms and 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 in one vectorized parallel step, whereas CWO cycles through the coordinates sequentially.
Finally, we computed the probability of missdetection () under the top- rule, defined as the MC average of . All CL-SCA, CL-FP and CL-Hyb variants and CWO give , consistent with their converging to the same stationary point, whereas M-SBL stalls at a higher loss and yields . CLMM also attains 0.267 although it does not reach , 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 single-antenna machine-type devices (MTDs) communicating with a BS equipped with antennas. For device identification, each device is preassigned a unique pilot (signature) sequence which is known at the BS. The device traffic is assumed to be sporadic, that is, in each coherence interval only devices are randomly active. In mMTC settings, the total number of devices is typically much larger than the pilot length ().
The received data follow the MMV model (1), where contains the observations over pilot symbols and BS antennas, and collects the device pilot sequences. The effective channel matrix has rows
where is the small-scale channel vector, is the activity indicator, is the large-scale fading coefficient (LSFC), and is the transmit power. Since only devices are active, is -row-sparse, with support . Under uncorrelated Rayleigh fading, the entries of are modeled as i.i.d. . 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 is assumed to be fixed (non-random, deterministic variable) and known. Hence the estimated support is obtained by the top- rule, yielding . Thus it is sufficient to use PMD as the performance metric since , and thus (empirical) probability of false alarm () contain the same information up to normalization.
Simulation setting follows that of subsection V-C, i.e., random Bernoulli matrix , in dB scale, , and (with ) is drawn uniformly without replacement from for each MC trial. Note that we assume no power-control, i.e., 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 is used to stop after selected atoms. We terminate each algorithm using (27) with . This criterion is algorithm-independent: it is a function of the current iterate alone, and it vanishes if and only if 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 for M-SBL and for other methods.
First we study the impact of the pilot length , number of BS antennas , and sparsity level on JADCE performance. Figure 2 plots versus for and from bottom to top. We observe that CL-MP performs well for small , but degrades as increases, especially for and . 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., .

Figure 2. Probability of miss detection vs. the number of antennas when (bottom panel), (middle panel) and (top panel). Number of MC trials: 10000; stopping tolerance for all algorithms: .
Figure 3 reports the runtimes for and averaged over 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 and , and about twice as fast for and . This is expected, since CL-MP is a greedy method that terminates after exactly iterations when 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 . 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 ( and as shown in the middle panel of Figure 2), its channel estimation performance is slightly better than that of CL-Hyb-bt. For , CL-Hyb-bt provides clearly improved performance while for 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.

Figure 4. Channel estimation NMSE vs. the number of antennas for different numbers of active devices when . Number of MC trials: 10000; stopping tolerance: .
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 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 and , 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 , then setting yields the estimating equation
Applying the Sherman-Morrison formula3 to , we notice that vectors and are parallel:
It follows from (43) that
Proof of Theorem 1
The convex term can expressed as
where 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 as
Let and be defined as
i.e., as values of vectors (8) evaluated at where . With the above notations and with the help of (46) and (9), we can write (21) compactly as
where . Above we ignored additive constants in (49) not dependent on . Taking the derivative of in (49) and setting it to zero yields the equation
which has a single root:
This expression is not convenient due to the term as it requires the computation of all the inverses for each coordinate .
Equations (44) and (45) hold for all , so also at , meaning that
where by (17) is . Then substituting (51) into (50) allows us to write the root in an equivalent form
If , the unconstrained minimizer is feasible (optimal), while if , then for all , in particular for all . Thus the solution is as given in (22).
Proof of Lemma 2
Recall from (11) that while the update map of Theorem 1 can be expressed as
Fix and suppose . If , the projection in is inactive, so , i.e., , and thus . If , then requires , i.e., , and hence . Thus (12) holds. Conversely, if and , then and (22) returns . If and , then and (22) returns . Hence .
Proof of Lemma 3
(i) For , dropping the nonnegative trace term gives . Since every eigenvalue of is at least , and the bound follows. Moreover, since
the Rayleigh quotient gives
Thus, on , so is bounded, and it is closed by continuity of , hence compact. Finally,
for all and all .
(ii) Differentiating (11) once more, with and (both positive semidefinite, , ), a direct computation gives
i.e., . By the triangle inequality and (note that the spectral norm is invariant to the sign of its argument, so the minus sign in front of is irrelevant),
Each term is now bounded by the Schur-multiplier inequality: for Hermitian and positive semidefinite , . Applying it with and (both and are positive semidefinite), and using and , which holds for every , and gives
yields
uniformly on .
Proof of Theorem 2
First we claim that for every , with and ,
Indeed, write , (recall ), and . Since and , each summand in (55) satisfies
which is nonpositive whenever lies between and . From the update , we notice that . Multiplying by and adding one gives
where the first branch corresponds to an inactive projection and the second to . If , then is the geometric mean of and and hence lies between them. Otherwise , so that . Summing over proves (55). Furthermore, for , since by Lemma 3 gives .
Assume . Since , with , lies on the segment between and , the quadratic upper bound (29) gives
where the 2nd inequality uses previous assertion, and the last uses . Since , (56) also proves inductively that every iterate remains in . Note that summing (33) over and telescoping yields
and bounding the weighted average from below by its smallest term gives (34). For , note and . Thus . If , the summability of forces . Every accumulation point then satisfies by continuity of the update map, and is KKT-stationary by Lemma 2.
Proof of Theorem 3
We claim that for every , with and ,
Fix . If the projection is inactive, then by (14), so , with equality. If the projection is active and , then and , i.e., , hence . If the projection is active and , then and the term vanishes. Summing over proves (57), and for invoking gives .
Proceed by induction, assume (true for ). Since lies on the segment , on which is -Lipschitz by Lemma 3(ii), the descent lemma and (57) with give
where the last step uses . In particular , so , closing the induction and proving (37). The rest follows as in proof of Theorem 2.
References
- [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]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]J. A. Tropp, “Algorithms for simultaneous sparse approximation. Part II: convex relaxation,” Signal Processing, vol. 86, pp. 589–602, 2006.DOI
- [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]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]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]M. E. Tipping, “Sparse bayesian learning and the relevance vector machine,” J. Mach. Learn. Res., vol. 1, no. Jun, pp. 211–244, 2001.
- [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]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]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]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]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]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]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]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]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]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]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]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]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]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]——, “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]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]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]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]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]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]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
- [30]D. P. Bertsekas, Nonlinear Programming, 2nd ed. Belmont, MA: Athena Scientific, 1999.
- [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.