PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient SCA Algorithms for Sparse Bayesian Learning

Esa Ollila, Majdoddin Esfandiari, Daniel P. Palomar, Xinjue Wang

arXiv:2610.34888v1eess.SP

TL;DR

EM-based M-SBL is a slow solver for the sparse Bayesian covariance-learning problem. The paper develops parallel SCA and fixed-point algorithms, combines them in CL-Hyb, and reports that CL-Hyb-bt matches the best CL solvers’ accuracy at substantially lower runtime and is more than an order of magnitude faster than M-SBL.

  • Problem

    EM-based M-SBL is known to converge slowly, especially in large-scale problems.

    Source: A. Relevant Prior Work · p. 2

  • Method

    The paper develops parallel CL-SCA and damped fixed-point CL-FP algorithms, then combines their local advantages in CL-Hyb.

    Source: §VII · p. 10

  • Results

    In JADCE in GFRA, the proposed methods match CWO’s detection performance at substantially lower runtime, and CL-Hyb-bt has the best accuracy–complexity trade-off among the CL methods.

    Source: §VII · pp. 10–11

  • Takeaways & Limitations

    CL-SCA is more stable in the transient phase, while CL-FP is faster near stationarity, motivating their combination in CL-Hyb.

    Source: §VII · p. 10

Abstract

from arXiv · show

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 $\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.

I. INTRODUCTION

The paper studies sparse support recovery in a multiple-measurement-vector model, where jointly sparse signals share a support and are modeled using Type-II sparse Bayesian learning. It motivates covariance-learning algorithms in part by the slow convergence of EM-based M-SBL, especially for large problems.

I. INTRODUCTION

  • The MMV model uses jointly sparse signal vectors that share a support, and support recovery seeks that common row support from the measurements and dictionary.Joint estimation can offer computational advantages and improved reconstruction accuracy.Source: §I · p. 1
  • SBL models the signal vectors as independent Gaussian vectors with diagonal signal covariance, whose nonzero powers identify the shared support.The paper assumes known positive noise variance.Source: §I · p. 1
  • The paper formulates covariance learning as minimizing the data’s negative log-likelihood and studies the resulting nonconvex optimization problem.It develops efficient algorithms using successive convex approximation.Source: §I · pp. 1–2

A. Relevant Prior Work

  • EM-based M-SBL is known to converge slowly, particularly in large-scale problems, and positive initialization prevents exact zeros in finite iterates.Other Type-II approaches include covariance learning, GAMP-based implementations, and variational methods.Source: A. Relevant Prior Work · p. 2

B. Contributions

The paper develops parallel covariance-learning algorithms and analyzes their convergence, then combines their local advantages in a hybrid method. In device activity detection, the hybrid with backtracking attains CWO’s missed-detection performance at roughly half its runtime and is more than an order of magnitude faster than M-SBL.

B. Contributions

  • CL-SCA preserves the convex part of the surrogate objective, linearizes the concave part, and gives closed-form parallel coordinate updates at O(NM^2) per iteration.Its per-iteration cost matches one cycle of CWO and one iteration of CL-MP, M-SBL, or CLMM.Source: B. Contributions · p. 2
  • CL-FP is a damped fixed-point iteration derived from the KKT conditions, with per-iteration cost equal to CL-SCA’s.The paper provides rate and step-size analysis for this iteration.Source: B. Contributions · p. 2
  • Both update maps have exactly the CL problem’s KKT points as fixed points; damped iterates achieve an O(T^-1/2) best-iterate stationarity rate.When damping factors are bounded away from zero, the residual vanishes along the sequence and every limit point is a KKT point.Source: B. Contributions · p. 2
  • CL-Hyb uses CL-SCA early and switches to CL-FP, combining CL-SCA’s allowance for twice the step size with CL-FP’s faster behavior near stationarity.The hybrid retains the convergence guarantees shared by the two updates.Source: B. Contributions · p. 2

II. FIRST ORDER CHARACTERIZATION OF THE PROBLEM

  • The paper’s unified fixed-point view identifies exact KKT fixed points for CL-SCA, CL-FP, and CLMM, while EM can have spurious boundary fixed points.The paper also characterizes the CL problem’s KKT conditions through a fixed-point equation.Source: B. Contributions · p. 2, §II · p. 3

B. Contributions

  • CL-Hyb-bt attains CWO’s missed-detection performance at roughly half its runtime and is more than an order of magnitude faster than M-SBL.It converges fastest among the optimization-based methods in both iterations and runtime.Source: B. Contributions · pp. 2–3

III. M-SBL

M-SBL estimates signal powers by minimizing the marginal Type-II negative log-likelihood, then uses the estimates to compute the posterior distribution. Its EM solver is slow and, with positive initialization, does not produce exactly sparse finite iterates.

III. M-SBL

  • Under Gaussianity, the posterior distribution of the sources factorizes across measurement vectors.The posterior is described using conditional means and a joint posterior covariance matrix.Source: §III · p. 3
  • M-SBL estimates hyperparameters by minimizing the marginal Type-II negative log-likelihood, then computes the posterior distribution using the estimated powers.The posterior mean is ΓA^HΣ^-1Y.Source: §III · p. 3

A. The EM-algorithm

  • The EM solver is slow, especially for large problems, and positive initialization leaves its finite iterates dense, though components may become arbitrarily small.Its multiplicative update requires strictly positive hyperparameters.Source: A. The EM-algorithm · p. 4

B. Sparsifying the solution

The paper sparsifies estimated signal powers after covariance learning, using either a fixed threshold or a top-K rule. CL-SCA updates coordinate-wise convex surrogates in parallel, with damping and a backtracking option supporting its convergence guarantees.

B. Sparsifying the solution

  • The solution is pruned by zeroing small powers using either a fixed threshold or the K largest entries, with the top-K rule requiring known or estimated K.Threshold selection can target a desired missed-detection and false-alarm trade-off.Source: B. Sparsifying the solution · p. 4

A. CL-SCA algorithm

  • CL-SCA linearizes the concave log-determinant term to form convex per-coordinate surrogates whose minimizers are computed in parallel.The coordinate minimizers have closed-form updates.Source: A. CL-SCA algorithm · p. 4
  • Damping blends the proposed update with the previous iterate, and the step size controls the update length.A backtracking rule certifies the best-iterate stationarity rate without step-size tuning.Source: A. CL-SCA algorithm · p. 5
  • A fixed point of the CL-SCA update map is a KKT point, and each iteration costs O(NM^2).The gradient-based termination criterion vanishes if and only if the KKT conditions hold.Source: A. CL-SCA algorithm · p. 5

B. Stationarity rate of CL-SCA

The section establishes sufficient-decrease and stationarity guarantees for CL-SCA under step-size conditions. A constant step achieves an O(T^-1/2) best-iterate rate, while diminishing steps weaken the certified rate.

B. Stationarity rate of CL-SCA

  • If the step sizes are bounded away from zero, the residual vanishes and every accumulation point is KKT-stationary.The result is stated as a consequence of the sufficient-decrease and stationarity analysis.Source: B. Stationarity rate of CL-SCA · p. 6
  • With a constant step size η ∈ (0, ¯η], CL-SCA achieves the best-iterate stationarity rate min_{k<T} ||p_k||_2 = O(T^-1/2).The bound matches the canonical rate stated for first-order methods on smooth nonconvex problems.Source: B. Stationarity rate of CL-SCA · p. 6
  • For diminishing schedules η_k = c(k + 1)^-a, the certified rate degrades to O(T^-(1-a)/2) for a ∈ (1/2, 1) and O((log T)^-1/2) for a = 1.The passage attributes the weaker rates to the slower growth of the cumulative step sizes.Source: B. Stationarity rate of CL-SCA · p. 6

C. Step-size selection

The section compares fixed and diminishing step-size choices and recommends backtracking. Its adaptive steps retain the O(T^-1/2) rate without requiring prior knowledge of the constants governing a safe step.

C. Step-size selection

  • Backtracking retains the O(T^-1/2) rate without tuning because accepted steps satisfy η_k ≥ ¯η/2.The rule starts from the last accepted step and can increase it after consecutive first-trial acceptances.Source: C. Step-size selection · p. 6
  • The backtracking test terminates after at most ⌈log2(1/¯η)⌉ halvings, and rejected trials cost one additional factorization.An accepted first trial costs nothing extra because its Cholesky factor is also needed for the next iteration.Source: C. Step-size selection · p. 6
  • Backtracking is recommended over a tuned constant step because ¯η depends on unknown constants, while the diminishing schedule does not provide the best possible rate.The accepted steps can grow when the landscape permits.Source: C. Step-size selection · p. 6

V. SCA VIA DAMPED FIXED-POINT ITERATIONS

CL-FP is a damped projected fixed-point iteration that can also be interpreted as a parallel SCA method. It shares CL-SCA’s convergence guarantees, while its local stability margin is smaller.

V. SCA VIA DAMPED FIXED-POINT ITERATIONS

  • CL-FP uses a damped projected fixed-point update, which minimizes a strongly convex quadratic surrogate per coordinate.The surrogate has curvature d_n^2 and matches the gradient of ℓ at the current iterate.Source: §V · p. 6

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

  • The undamped fixed-point map is not generally a contraction, so damping is not merely cosmetic.A fixed step tuned for CL-SCA is typically too large for CL-FP, while backtracking adapts automatically.Source: A. Stationarity rate of CL-FP and… · pp. 6–7
  • For constant η ∈ (0, ¯η], the best-iterate rate is min_{k<T} ∥q_k∥² = O(T^-1/2); when inf_k η_k > 0, ∥q_k∥² → 0 and every accumulation point is KKT-stationary.Source: A. Stationarity rate of CL-FP and… · p. 7
  • CL-FP and CL-SCA share the same safe damping bound, sufficient-decrease constant, stationarity rate, and per-iteration computational complexity.Their residuals are equivalent stationarity measures, with Δ_SCA(γ) ≤ Δ_FP(γ) ≤ (1 + √¯r)Δ_SCA(γ).Source: A. Stationarity rate of CL-FP and… · p. 7
  • CL-SCA has double the local stability margin: its scaled-Hessian eigenvalues may lie in (0, 4), versus (0, 2) for undamped CL-FP.The passage notes that a full step often works for CL-SCA but can destabilize CL-FP on the same data.Source: A. Stationarity rate of CL-FP and… · p. 7

B. Relation to the MM-based algorithm

CL-SCA uses a tighter coordinate-wise surrogate than CLMM’s separable joint majorizer, while CLMM’s built-in damping makes its update monotone without a tuned step size. In the convergence experiments, CL-Hyb-bt reaches the reference objective faster than the compared methods, and the proposed CL variants and CWO share the same reported miss-detection rate.

B. Relation to the MM-based algorithm

  • CL-SCA and CLMM fixed points satisfy the KKT condition at zero coordinates, but EM also has spurious fixed points with γn = 0 and en > dn.EM’s multiplier vanishes at γn = 0, so such coordinates remain fixed regardless of the gradient sign.Source: B. Relation to the MM-based algorithm · p. 7
  • CLMM’s multiplier never exceeds CL-SCA’s, making CLMM intrinsically damped and monotone without a step size; its majorization constant ν is the price of that damping.With the stated trace choice and equal-norm atoms, the CLMM step from γ0 = 0 is shorter by a factor N; a conservative ν costs a logarithmic rather than linear number of additional iterations.Source: B. Relation to the MM-based algorithm · pp. 7–8
  • CL-SCA keeps the convex term exact along one coordinate with the others frozen, whereas CLMM majorizes it to form a surrogate separable across all coordinates.Both surrogates share the same linear term from linearizing the concave log-determinant term; CL-SCA’s surrogate is tighter along its coordinate, while CLMM’s is a joint majorizer.Source: B. Relation to the MM-based algorithm · p. 8

C. Convergence analysis and a new Hybrid method

  • The objective gap uses the raw objective and can reveal non-monotone transients, while the normalized running-minimum loss is monotone and supports time-to-target comparisons.The reference objective is the smallest value recorded over a 1500-iteration run; the running-minimum measure starts at one for each run.Source: C. Convergence analysis and a new… · p. 8
  • At k = 50, CL-Hyb’s gap is 3.9 × 10−6, compared with 8.4 × 10−6 for CL-FP-fss and 1.8 × 10−5 for CL-SCA-fss.CL-Hyb uses CL-SCA for five iterations before switching to FP; the shared sufficient-decrease inequality carries over the convergence guarantees.Source: C. Convergence analysis and a new… · p. 8
  • At k = 50, CL-SCA-bt and CL-Hyb-bt gaps are 5.8 × 10−7 and 2.1 × 10−8, respectively; both reach the numerical gap floor near 5 × 10−12 by about k = 100 and k = 80.The passage reports these gaps as 31 and 185 times smaller than those of CL-SCA-fss and CL-Hyb, respectively; accepted steps are typically larger than the hand-tuned constants.Source: C. Convergence analysis and a new… · p. 9
  • 30 iterations and 3.0 ms: CL-Hyb-bt reaches the reference objective, versus 44 iterations and 3.9 ms for CL-FP-fss; M-SBL and CLMM do not reach it within 250 iterations.CWO reaches the target in 8.4 ms despite needing only ten cycles; CL-SCA and CL-FP update the full vector in one parallel step, unlike CWO’s sequential coordinate cycles.Source: C. Convergence analysis and a new… · p. 9
  • PMD is 0.267 for all CL-SCA, CL-FP, and CL-Hyb variants and CWO, versus 0.293 for M-SBL; CLMM also has PMD 0.267 despite not reaching the reference objective.The passage reports that CLMM’s support is identified well before full convergence.Source: C. Convergence analysis and a new… · p. 9

VI. APPLICATION TO JADCE IN GFRA

The paper evaluates covariance-learning solvers for joint activity detection and channel estimation in grant-free random access, then summarizes the proposed algorithms’ convergence properties. CL-Hyb-bt combines their complementary behavior and is reported to offer a strong accuracy–runtime trade-off.

VI. APPLICATION TO JADCE IN GFRA

  • The application evaluates activity detection and channel estimation in an uplink massive-random-access setting with sparse device activity and pilot-based observations.The simulations use random Bernoulli pilots, no power control, and compare solvers under a shared KKT-proximity stopping criterion.Source: §VI · pp. 9–10
  • CL-Hyb-bt, CLMM-2, and CWO achieve nearly identical missed-detection performance, while M-SBL is slightly worse, especially with short pilots.CL-MP performs well at small K but degrades as K increases; the comparison assumes a fixed, known number of active devices.Source: §VI · pp. 9–10, Figure 2 · p. 10
  • More than one order of magnitude faster than M-SBL, CL-Hyb-bt runs at roughly half the runtime of CWO and is the fastest optimization-based method.The runtime comparison uses an algorithm-independent stopping criterion based on proximity to KKT conditions.Source: §VI · p. 10, Figure 3 · p. 11
  • For channel estimation at M = 30, CL-Hyb-bt is clearly better than CL-MP at K = 40, marginally different at K = 30, and slightly worse at K = 20.At K = 20, CL-MP also has slightly better activity-detection performance; several other methods’ channel-estimation curves overlap CL-Hyb-bt.Source: §VI · p. 10, Figure 4 · p. 11

VII. CONCLUSIONS

  • CL-SCA and CL-FP have sufficient-decrease and O(T^-1/2) best-iterate stationarity guarantees; CL-Hyb is motivated by CL-SCA’s transient stability and CL-FP’s faster near-stationary behavior.The paper also proposes future work on joint γ and σ² estimation, robust extensions to non-Gaussian losses, and unfolding the iterations into a network.Source: §VII · pp. 10–11

APPENDIX

The appendix connects the projected fixed-point map to the CL problem’s KKT conditions and derives the coordinate update used by CL-SCA. The update is obtained by minimizing a coordinate surrogate and projecting its minimizer onto the nonnegative domain.

A. Proof of Lemma 1

  • The projected fixed-point map equals the current vector exactly when the KKT conditions hold, coordinate by coordinate.Positive coordinates require zero gradient; zero coordinates require a nonnegative gradient.Source: A. Proof of Lemma 1 · p. 11

B. Proof of Theorem 1

  • The surrogate’s compact expression uses quantities evaluated at the current covariance matrix, avoiding a separate inverse computation for every coordinate.The derivation uses the Sherman–Morrison formula to rewrite the coordinate expression.Source: B. Proof of Theorem 1 · pp. 11–12
  • The CL-SCA coordinate update is the nonnegative projection of the surrogate’s unconstrained minimizer.When that minimizer is negative, the constrained solution is zero.Source: B. Proof of Theorem 1 · pp. 11–12

C. Proof of Lemma 2

The appendix proves that the CL-FP update map’s fixed points coincide with the CL problem’s KKT points. It also establishes boundedness and smoothness properties on the relevant objective sublevel set.

C. Proof of Lemma 2

  • A fixed point of the CL-FP update satisfies the KKT conditions, and every KKT point is a fixed point.For positive coordinates the gradient is zero; at zero coordinates it is nonnegative.Source: C. Proof of Lemma 2 · p. 12

D. Proof of Lemma 3

  • The objective sublevel set is compact, and the gradient has bounded curvature there.The proof bounds the coordinates using the covariance eigenvalue bound and derives a Hessian bound using positive-semidefinite matrix quantities.Source: D. Proof of Lemma 3 · p. 12

E. Proof of Theorem 2

The proofs establish quantitative descent for the CL-SCA and CL-FP directions and use it to derive sufficient decrease for damped iterations. Summability then yields a best-iterate stationarity bound and, with damping bounded away from zero, KKT limit points.

E. Proof of Theorem 2

  • The CL-SCA direction has a quantitative descent bound, which yields sufficient decrease when the damping step is small enough.The proof uses a lower bound on the coordinate derivatives over the objective sublevel set.Source: E. Proof of Theorem 2 · p. 12
  • Telescoping the decrease inequality gives the best-iterate stationarity bound; when damping is bounded away from zero, the residual vanishes and every limit point is KKT.The proof also establishes that iterates remain in the objective sublevel set.Source: E. Proof of Theorem 2 · p. 13

F. Proof of Theorem 3

  • The CL-FP direction likewise satisfies a quantitative descent bound, supporting sufficient decrease for its damped iterates.The proof applies the descent lemma on the segment between the current iterate and its projected fixed-point update.Source: F. Proof of Theorem 3 · p. 13
Loading 2610.34888v1…