Block Sparse Bayesian Learning: A Diversified Scheme
Authors: Yanhao Zhang
Zhihan Zhu
Yong Xia
Venue: NeurIPS 2024 poster (2024)
Keywords: Compressed Sensing
Diversified Block Sparse Prior
Sparse Bayesian Learning
Lagrange Dual Ascent.
Primary area: probabilistic_methods

Abstract: This paper introduces a novel prior called Diversified Block Sparse Prior to characterize the widespread block sparsity phenomenon in real-world data. By allowing diversification on intra-block variance and inter-block correlation matrices, we effectively address the sensitivity issue of existing block sparse  learning methods to pre-defined block information, which enables adaptive block estimation while mitigating the risk of overfitting. Based on this, a diversified block sparse Bayesian learning method (DivSBL) is proposed, utilizing EM algorithm and dual ascent method for hyperparameter estimation. Moreover, we establish the global and local optimality theory of our model. Experiments validate the advantages of DivSBL over existing algorithms.

Block Sparse Bayesian Learning: A Diversified Scheme
Yanhao Zhang Zhihan Zhu School of Mathematical Sciences, Beihang University Beijing. 100191
Yong Xia
{yanhaozhang, zhihanzhu, yxia) edu.. cn
Abstract
This paper introduces a novel prior called Diversified Block Sparse Prior to charac- terize the widespread block sparsity phenomenon in real-world data. By allowing diversification on intra-block variance and inter-block correlation matrices, we effectively address the sensitivity issue of existing block sparse learning methods to pre-defined block information, which enables adaptive block estimation while mitigating the risk of overfitting. Based on this, diversified block sparse Bayesian learning method (DivSBL) is proposed, utilizing EM algorithm and dual ascent method for hyperparameter estimation. Moreover, establish the global and local optimality theory of our model. Experiments validate the advantages of DivSBL. over existing algorithms.
1 Introduction
Sparse recovery through Compressed Sensing (CS), with its powerful theoretical foundation and broad practical applications, has received much attention [ The basic model is considered as
Øx.
(1)
where y E R Mxx1 is the measurement (or response) vector and + E R M is a known design matrix, satisfying the Unique Representation Property (URP) condition 2 RN >> M) is the sparse vector to be recovered. In practice, x often exhibits transform sparsity, becoming sparse in transform domain such Wavelet, Fourier, etc. Once the signal is compressible in linear basis V, in other words, x Vw where w exhibits sparsity, and 4 satisfies Restricted Isometry Constants (RIP) [] then we can simply replace x by Vw in ( and solve it the same way. Classic algorithms for compressive sensing and sparse regression include Lasso 44. Sparse Bayesian Learning (SBL)
[5] Basis Pursuit (BP) 6 Orthogonal Matching Pursuit(OMP) 7 etc. Recently, there have been
approaches that involve solving CS problems through deep learning g D [0].
However, deeper research into sparse learning has shown that relying solely the sparsity of is insufficient, especially with limited samples [I [2]. Widely encountered real-world data, such as image and audio, often exhibit clustered sparsity in transformed domains [13] This phenomenon,
known as block sparsity, means the sparse non-zero entries of x appear in blocks [1]. Recent years, block sparse models have gained attention machine learning, including sparse training 14)
adversarial learning [15), image restoration [66] 14, (audio) signal processing [17 [8] and many
other areas. Generally, the block structure with g blocks defined by
J1 F1...Ty Fdl Fdh ... Fel +dg
UN d,
where di - 1...9) represent the size of each block, which are not necessarily identical. Suppose only kik < g) blocks are non-zero, indicating that x is block sparse. Up to now, several methods have been proposed to recover block sparse signals. They are mainly divided into two categories. *Corresponding author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Block-based
Classical algorithms for processing block sparse scenarios include Group-Lasso Blocks are assumed be static with fixed 19 20 2T. Group Basis Pursuit [22]. Block-OMP
preset size. Furthermore, Temporally-SBI. (TSBL) 23 and Block-SBI. (BSBL. [24 25 based on Bayesian models, provide refined estimation of correlation matrices within blocks. However, they assume elements within one block tend to be either zero or non-zero simultaneously. Although they can estimate intra-block correlation with high accuracy in block-level recovery, they require preset choices of suitable block sizes and patterns, which are too rigid for many practical applications.
Pattern-based StructOMP [26] is pattern-based greedy algorithm allowing structures, which is generalization of group sparsity. Another classic model named Pattern coreeldC SBL (PC-SBL) 27 (8), does not have a predefined requirement for block size as well. utilizes a Bayesian model to couple the signal variances. Building upon PC-SBI., Burst PC-SBL, proposed in (2) is employed for the estimation of mMIMO channels. While pattern- algorithms address the issue of explicitly specifying block patterns in block-based algorithms, these models provide coarse characterization of the intra-block correlation, leading to loss of structural information within the blocks.
In this paper, we introduce a diversified block sparse Bayesian framework that incorporates diversity in both variance within the same block and intra-block correlation among different blocks. Our model not only inherits the advantages of block-based methods on block-level estimation, but also addresses the longstanding issues associated with such algorithms: the diversified scheme reduces sensitivity to predefined block size specified block location, hence accommodates general block sparse data. Based on this model, we develop the DivSBL. algorithm. and also analyze both the global minimum and local minima of the constrained cost function (likelihood). The subsequent experiments illustrate the superiority of proposed diversified scheme when applied to real-life block sparse data.
2 Diversified block sparse Bayesian model
We consider the block sparse signal recovery, or compressive sensing question in the noisy case
Øx n,
where n ~ -0,,3~11 1)) represents the measurement noise, and / is the precise scalar. Other symbols have the same interpretations (I). The signal exhibits block-sparse structure in 2 yet the block partition is unknown. For clarity in description, we assume that all blocks have equal size L, with the total dimension denoted as N gL. Henceforth, presume that the signal x follows the structure:
2111 LLL F21
22L
Lg
Lg
In Sections 2.1.1 and 5.2 we clarify that this assumption is made without loss of generality. In fact, our algorithm can automatically adjust to an appropriate size, expanding or contracting as needed.
2.1 Diversified block sparse prior
The Diversified Block Sparse prior is proposed in the following scheme. Each block x; E RA is assumed to follow multivariate Gaussian prior
p (x:: [G,, B.)) N (0, G,B.G.,, Vi - .9.
(5)
in which, G; represents the Diversified Variance matrix, and B, represents the Diversified Correlation matrix, with detailed formulations in Sections 2.1.1 and 2.1.2 Therefore, the prior distribution of the entire signal x is denoted as
P (x: GG. B ) N 10, En),
(6)
where Σg = diag (GB,G,, G,B,G,, ... G,B.G,),. The dependency in this hicrarchical model is shown in F
2.1.1 Diversified intra-blodd variance
We first execute diversification on variance. In 5). G2 is defined as
G, A diagl Vii vrL)
and B, E L is positive definite matrix capturing the correlation within the i-th block. According to the definition of Pearson correlation, the covariance term G.B.G. in (5) can be specified as

---

Demonstration Rationale
Left: When true black located within the pieset
Spars vector to be recovened
When block locared the presst block.
Covariznee typerparcnniees
Noise level
comesponding
G,B.G.
(-0) or zero positions in x; will be automatically leamed as non-zero
defined Block
values through
posterior inference,
block.
Tree Block
4
X4.
Bg
The gold dashed line shows the preset block, and the black shadow repre- sents the actual position of the block with its true size.
Figure 2:
Figure 1: Directed acyclic graph of diversified block sparse hierarchical structure. Except for Measurements (blue nodes), which are known, all other nodes are parameters estimate.
Piay via
PLLY Vie. PaL T5 /TE
where P kVs T.) the el- ements in correlation matrix B, serv- ing visualization of covariance with displayed structural information.
Pá Vaviava
762
G,B.G.
ULIVAL
Now it is evident why assuming equal block sizes L insensitive, For the sake of clarity. we denote the true size of the i-th block as L.p. As illustrated in Figure when the true block falls within the preset block, the variances 7/-. corresponding to the non-zero positions x; will be learned as non-zero values through posterior inference, while the variances at zero positions will automatically be learned as zero. When the true block is positioned across the preset block, several blocks of the predefined size L covered by the actual block will be updated together, and likewise, variances will be learned as either zero or non-zero. this way, both of the size and location the blocks will be automatically learned through posterior inference the variances.
2.1.2 Diversified inter-block correlation
Due to limited data and excessive parameters in intra-block correlation matrices B;(V),, previous works correct their estimation by imposing strong correlated constraints B; B(vi to overcome overfitting 24.. Recognizing that correlation matrices among different blocks should be diverse yet still exhibit some correlation, we apply a weak-cordelated constraint to diversify B, in the model.
Here we introduce novel weak constraints on B,, specifically.
BB) w (B) Vi =-=1 1,.....00 !
where v) R + R is the weak constraint function and B is obtained from the strong constraints B, (Vi), as detailed Section 3.22 Weak constraints (8) only capture the distinct correlation structure but also avoid overfitting issue arising from the complete independence among different B;
Furthermore, the constraints imposed here not only maintain the global minimum property of our algorithm, as substantiated in Section 4 but also effectively enhance the convergence rate of the algorithm. There actually gl([+1) 1)/2 constraints the strong correlated constraints B, B(vi), while with (8), the number of constraints significantly decreases to g. yielding acceleration on the convergence rate. The experimental result is shown in Appendix A
In summary, the prior based on 6 and 8 defined as diversified block sparse prior.
2.1.3 Connections to classical models
Note that the classical Sparse Bayesian Learning models, Relevance Vector Machine (RVM) 5 and Block Sparse Bayesian Learning (BSBL) (23), special cases of our model.

---

Connection to RVM Taking B; as identity matrix, diversified block sparse prior (6) degenerates RVM model
immediately
p (=);)) = =N (0, 7) Vi 1, N,
(9)
which means ignoring the correlation structure.
Connection to BSBL
When G; is scalar matrix v7al, I, the formulation 5
becomes
(x {m, B, = N (0, B,), Vi = 1.:=1,... 1, 1,....9. ,
(10)
which is exactly BSBL model. In this case, all elements within block share common variance %
2.2 Posterior estimation
By observation model (3. the Gaussian likelihood is
ply x: 3) -N
(11)
With prior (6 and likelihood (II). the diversified block sparse posterior distribution of x can be derived based on Bayes' theorem as
p(x y: (G,, B, N (H, E),
(12)
where
11 BE4" y:
(13)
Σ = ED + 1. Φb)
(14)
After estimating all hyperparameters in ie, θ (G, (B.)..1 3). the Maximum A Posterior (MAP) estimation of x is formulated as
described in
Section 3
MAP j..
(15)
3 Bayesian inference: DivSBL algorithm
3.1 EM formulation
To estimate θ {(G.)) (B,) 1: 3), either Type-II Maximum Likelihood 30 or Expectation- Maximization (EM) formulation 31 can be employed. Following EM procedure, our goal is to maximize p(y: θ), or equivalently log p(y; 0). Defining objective function as L(O), the problem can be expressed
max θ
((0) y-- " log det Ey.
(16)
where E, = 8- + + Eg
Then, treating x as hidden variable in E-step, we have Q function as Q(+) =z [logp(y, x: 0)]
Th.
= =2 plog((y x]] Exyy: [log (x: (B.)).
Q + Q( (B.))=))
(17)
where (--1 denotes the parameter estimated in the latest iteration. As indicated in 17.. we have divided Q function into two parts: Q(3) - - (logerr--lopp x; 8)] depends solely on B, and Q((G, ( [B.)_.) & e [log p (x; (G (B.) only on (G,) and (_))_-
Therefore, the parameters of these two Q functions can be updated separately.
In M-step, we need to maximize the above Q functions to obtain the estimation of e. As shown in Appendix B the updating formula for Tij. B, can be obtained as follow!
4A2 kg
(18)
T
4Aii T2y)
Using MATLAB notation, je' & u((i 1)L (L), M(ii 1)L 11 1)L iL))

---

B; = G. E + e (n')² m
G
(19)
where Tiş and Ai are expressed Tış (B ) diag W W-)) (E' + +²(m)))), Aij
(Br') E'' + nt (n²)²
and diagl /aa. Ry-1, 0, "ij+i,"" vLL) The jj
update formula of is derived the same way as 23].
The learning rule given by
M
3 lyy Lul tr ΣΦ"
(20)
3.2 Diversified correlation matrices by dual ascent
Now we propose the algorithm for solving the correlation matrix estimation problem satisfying ( As mentioned in Section 2.1.2 previous studies have employed strong constraints B, B(Vi), i.e.
B = B;
E [ p (1')²) G
G.
(21)
9 1=1
In diversified scheme, we apply weak-correlated constraints ( to diversify B, Therefore, the problem of maximizing the Q function with respect to B, becomes
max
Q( (G.)==)
B,
(22)
s.t.
3 (B,) + (B) Vi = 1, 9..
which is equivalent to (in the sense that both share the same optimal solution)
min 1
2 log det Eo +
2 [E (=+++"))))
t. 3 (B.) - (B)
1, 99
where B is already derived in (1)). Therefore, by solving (P) will obtain diversified solution for correlation matrices B, Vi. The constraint function va can be further categorized into two cases:
explicit constraints and hidden constraints.
Explicit constraints with complete dual ascent Explicit functions such as the Frobenius norm, the logarithm of the determinant, etc., are good choices for sb. An efficient way solve this constrained optimization is to solve its dual problem (mostly refers to Lagrange dual (32)). Choosing vi(-) as log det((), the detailed solution process is outlined in Appendix C And the update formulas for B; and multiplier A (dual variable) are given by
G
Σ
+ 1 (4²)² G.¹
B
(23)
+ 21
X+1 = X + af (log det B - log det B),
(24)
in which at represents the step size in the k-th iteration for updating the multiplier X; (i = 1,... ... 9)
Convergence is only guaranteed if the step size satisfies Σ a oo and _ (a < xo [32
In our experiment, we choose diminishing step size 1 1/k to ensure the convergence of the algorithm. The procedure, using dual ascent to diversify B,, summarized in Algorithm 2 in Appendix C
Hidden constraints with one-step dual ascent The weak correlated function à can also be chosen
as hidden constraint without an explicit expression. Specifically, the solution to sub-problem (22
equipped with hidden constraints corresponds exactly one-step dual ascent in 23 24
We
summarize the proposition as follows:
Proposition 3.1. Define explicit weak constraint function Ç 18n - R. For the constrained optimization problem:
min Q( (..)._))
S. t.
<(B)) = (B), Vi = 1,
5

---

the stationary point (B.+)) Rem (=)) of the Lagrange function under given multipliers (X }2 satisfies:
TB.Q(BB 1 -
Then there exists a constrained optimization problem with hidden weak constraint v R= - RR
min
Q( ( (G,))=)
B.
t.
-
vi= vi=1,-..
such that ((B) ((B++1)0
1 1 is a KKT pair of the above optimization problem.
Compared to explicit formulation, hidden weak constraints, while ensuring diversification correla- tion, significantly accelerate the algorithm's speed by requiring only one-step dual ascent for updating. Here, we set ((-) as log det(-), actually solving the optimization problem under corresponding hidden constraint vs. The comparison of computation time between explicit and hidden constraints, proof of
Proposition 3.1 and further explanations hidden constraints are provided in Appendix D
Considering that it's sufficient to model elements of a block as first order Auto- aato-Reeression (AR) process (24] in which the intra-block correlation matrix is a Toeplitz matrix, we employ this strategy for B, After estimating B, by dual ascent, we then apply Toeplitz correction to B; as
B. = Toeplitz ([ (I.
where mi is the approximate AR coefficient, mo ma (25) represents the average of elements along the main diag- onal of B,, and my represents the average of elements along the main sub-diagonal of B;
In conclusion, the Diversified SBL (DivSBL) algorithm is summarized as Algorithm below.
Algorithm DivSBL Algorithm
1: Input:
Measurement matrix response y, initialized variance 7, prior's 's covariance Es, noise's variance 3, and multipliers X
Refer to Appendix L for initialization sensitivity.
Output: Posterior mean MAP posterior covariance Σ, variance ý, correlation B,, noise B.
3: repeat
4: if mean(7)))< threshold then
5: Prune 7/. from the model (set Yt =0).
I| Zero out small energy for efficiency.
6: Set the corresponding μ² = 0, E' 01
7:
end if
8:
Update "iky by (8
Update diversified variance. Avoid overfitting. Diversified correlation.
Update B by (21
10:
Update B,, A by
11:
Execute Toeplitz correction for B, using 25
12:
Update μ and Σ by 13 14)
13:
Update / using 20
until convergence criterion met
15:
MAP
μ.
Use posterior mean as estimate.
Global minimum and local minima
For the sake of simplicity, denote the true signal Xmue which the sparsest among all feasible solutions. The block sparsity of the true signal is denoted as Ko. indicating the presence of Ko blocks. Let G A diag (VTri, ). B A diag .B..... Bg). thus Eg GBG. Additionally, we assume that the measurement matrix & satisfies the URP condition We employed various techniques to overcome highly non -onniincar structure of y in diversified block sparse prior (5). resulting in following global and local optimality theorems.
4.1 Analysis of global minimum
By introducing a negative sign to the cost function (66). we have the following result on the property of global minimum and the threshold for block sparsity Ko-
'Tee necessity of each step for updating B, in line 9-11 of Algorithm I is detailed in Appendix

---

Table 1: Reconstruction enrrr (NMSE) and Cor- relation (meandsst) for synthetic signals. Our algorithm is marked in blue, and the best- performing metries are displayed in bold.
Algoritlum
NMSE
Corr
Homoseddattc
Baane
Stridl
Drat
122
canos
BSBI. PC-SBL
0.0002::000099
0.9936:10.0034
0.0450=0.0188
0.9784=200090
SBL
0.0223==0.0199
0.9825=0000062
Group Lasso
0.0215::0.00522
0.9925:10.0020
Resorstructinn MASIE
Group BPDN
0.0378:10.0087
0.9812:10.0044
StrictOMP
0.0508=0.0157
0.9700=0.0073
DivSBL
0,009400.0053
0.9955=000026
Heteroscedastic
BSBL PC-SBL
0.0245=0.0125
0.9683=000047
0.04211:00019
0.9798:10.0082
Raaen
Bicss
SBL
0.0274.10.009
0.9673.10.0040
Group Lasso
(
Group BPDN
0.0857=00.013
0.9608=0.0096
StructOMP
0.0419=000123
0.9803:1000001
Figure 3: The consistency of multiple experiments with ho- moscedastic signals for (a) NMSE (b) Correlation, with
DivSBL.
0.0086
0.9958 0.0020
heterosccdastic signals for (c) NMSE and (d) Correlation.
Theorem 4.1. As 3 - Do and Kg < 1M/1) the unique global minimum 3 - (fr1,..., Rot.)
yields recovery & by 13 that is equal to Xune. regardless of the estimated B, (Vi).
The proof draws inspiration from 23 and is detailed in Appendix E
Theorem 4.1 shows that, in noiseless case, achieving the global minimum of variance enables exact recovery the true signal, provided the block sparsity of the signal adheres to the given upper bound.
4.2 Analysis of local minima
We provide two lemmas firstly. The proofs are detailed in Appendices F and
Lemma 4.2. For any semi-definite positive symmetric matrix Z M M the constraint Z
DE, 2" + +B--I is convex with respect to Z and (V7 VT).
Lemma 4.3. y JTEy'y = c (VP
b for any constant C, where b a --'u. P é (u & Φ diag (vec(B)). and a vector satisfying yTu yu==C
It's clear that P a full row rank matrix, i.e, r(P) M...M.GGGN. Given the above lemmas, we arrive at the following result, which is proven in Appendix
Theorem 4.4. Every local minimum of the cost function (6) with respect to y satisfies l| & VM, irrespective of the estimated B, (Vi) and B.
Theorem 4.4 establishes upper bound the sparsity level of any local minimum for the cost function in terms of the parameter Therefore, together with Theorem 4.1 these results ensure the sparsity of the final solution obtained.
5 Experiments
In this section, we compare DivSBL with the following six algorithms I. Block-based algorithms: (1) BSBL, (2) Group Lasso,
(3) Group BPDN. 2. matter--based algorithms: (4) PC-SBL, (5) StructOMP. 3. Sparse learning (without structural information): (6) SBL. Results are averaged
over 100 500 random (based computational scale), with SNR ranging from 15-25 dB
Matllb codes for our algorithm available at att.pp///gtauuo.cm///ehhhoon/ggs
7

---

except the test for varied noise levels. 'Normalized Mean Squared Error (NMSE)', defined as || Tiree / Fimell2 and 'Correlation (Corr)' (cosine similarity) are used to compare algorithms.
5.1 Synthetic signal data
We initially on synthetic signal data, including homoscedastic (provided by [24] and heteroscedas- tic data, where block size, location, non-zero quantity, and signal variance are randomly generated. mimicking real-world data patterns. The reconstruction results provide in Appendix [.1 Table shows that DivSBL. achieves the lowest NMSE and the highest Correlation on both scenarios. To more intuitively demonstrate the statistically significant improvements of the conclusion, we provide box plots of the experimental results on both homoscedastic and heteroscedastic data in Figure
Unlike many frequentist approaches that require more complex debiasing methods to construct confidence intervals, the Bayesian approach offers a straightforward way to obtain credible intervals for point estimates. For more results related to Bayesian methods, please refer to Appendix [.2]
5.2 The robustness of pre-defined block sizes
As mentioned in Section I block-based algorithms require presetting block sizes, and their perfor- mance is sensitive to these parameters, posing challenges in practice. This experiment assesses the robustness of block-based algorithms with predefined block sizes. The test setup is shown in Figure
We vary preset block sizes and conduct 100 experiments for all algorithms. Confidence intervals in Figure 4 depict reconstruction error for statistical significance.
Three blocks with sizes of 100, 40, and 30, respectively. The block sizes differ significnnly, with heing relatively large, positions random.
Environment:
DNSBL
BSBL
Lasso Group
NMSE
Demonstration Rationale
(1) DIvSBL: The optimal block size for DivSBL is in the runge which aligns closely size of the signal compared to other block-bated algoeithms.
block
(2)
algorithms: They
mmore hissed) optimal block sizes. Even at their optiaal block
the result behind DivSBL, Their improvement
element-wise recovery
100
150
200
250
300
350
500
Block
Figure 4: NMSE variation with changing preset block sizes.
Resolves the longstanding sensitivity issue of block-based algorithms. DivSBL demonstrates strong robustness to the preset block sizes, effectively addressing the sensitivity issue that block-based algorithms commonly encounter with respect to block sizes.
Figure visualizes the posterior variance learning on the signal demonstrate DivSBL's ability to adaptively identify the true blocks. The algorithms are tested with preset block sizes of 20 (small), 50 (medium), and 125 (large), respectively, to show how each algorithm learns the blocks when block structure is misspecified. As expected in Section 2.1 and Figure 2. DivSBL is able adaptively find the true block through diversification learning and remains robust to the preset block size.
Exhibits enhanced recovery capability in challenging scenarios. The optimal block size for DivSBL is around 20-50, which more consistent with the true block sizes. This indicates that when true block sizes are large and varied, DivSBL can effectively capture richer information within each block by setting larger block sizes, thereby significantly improving the recovery performance. In contrast, other algorithms do not perform well DivSBL, even at their optimal block sizes.
'NMSE quantifies the numerical closeness two vectors, while correlation measures the accuracy of estimating target support set and the level of recovery similarity within that set (also utilized in (33)) Therefore, employing both metrics together
comprehensively reflect the structural sparse recovery of the target.

---

Original Skgre 50
Orig nal
DivSBI Variance
(Verennc ))
20
L 500
(Variance )
(Variance
20
Signal
Original Signal 80
DivSaL Vartance )
PC-SBL (Varlance
L 125
BABL
n)
125
(8) PC-SBL SDL
Figure 5: Variance learning
Table 2: Reconstruction errors (NMSE + std) under different noise levels (sample rate=0.25).
SNR
BSBL
PC-SBL
SBL
Group BPDN
Group Lasso
StructOMP
DivSBL
10
0,235 1: 0.052
0.283
0.049
0.391 +: 0.064
0.223 1: 0.055
0.215 1 0.055
0.437 : 0.129
0.191 1: 0.076
0,300
0.058
0.139 : 0.057
0.167 0.043
0.074
0.016
20
0,046 1 0.010
0.107 0.028
0,180 1: 0.018
0.122 1: 0.062
0.111 1. 0.062
0.067 1 0.020
0.035 1. 0.010
0.025 0.006
0.068 0.027
0.167 0.018
0.113 + 0.057
0.102 + 0.057
0.030 - 0.012
0.019 + 0.005
30
0,015 + 0.006
0,046 0.023
0,160 = 0.016
0.103 = 0.054
0,093 + 0.053
0.019 = 0.011
0.010 + 0.004
0,011 0.004
0.032 0.017
0.155 0.019
0.100 : 0.070
0.08% + 0.070
0.013 = 0.0U8
0.009 : 0.003
0.009 1 0.004
0.027 0.020
0,155 0.015
0.095 1 0.061
0,084 1 0.060
0.010 0.006
0.007
0.002
0.008 + 0.005
0.025 - 0.016
0,153 + 0.015
0.099 1 0.053
0.087 1 0.052
0.011 = 0.010
0.006 + 0.002
0.008 0.004
0.015
0.063
1 0.062
1 0.006
0.007 0.003
5.3 1D audioSet
As shown in Figure 14 audio signals exhibit block sparse structures in discrete cosine transform (DCT) basis, which is well-suited for assessing block sparse algorithms. In this subsection, we carry out experiments reconstruction results are present in [ In the main text, we focus on analyzing DivSBL's sensitivity to sample rate, evaluating its performance across different noise levels, and investigating its phase transition properties.
real-world audios, which are randomly chosen in AudioSer [34]. The
The sensitivity of sample rate The algorithms are tested on audio sets to investigate the sensitivity of sample rate (M/N) varied from 0.25 to 0.55. The result is visualized in Figure [6] Notably, DivSBL emerges as the top performer across diverse sampling rates, showing a consistent dB enhancement NMSE compared to the best-performing algorithm among others.
The performance under various noise levels We assess each algorithm as Signal-to-Noise Ratio (SNR) varied from 10 50 and include the standard deviation from 100 random experiments on audio sets. Here, we present the performance under the minimum sampling rate 0.25 tested before, which represents a challenging recovery scenario. As shown in Table [ the performance of all algorithms improves with higher SNR. Notably, DivSBL consistently leads across all SNR levels.
Phase Transition This audio data contains approximately 90 non-zero elements in DCT domain (K 90), which constitutes about 20% of the total dimensionality (N = 480). Therefore, we start the test with a sampling rate of a same 20%. In this scenario, M/ K is roughly 1 and increases with the sampling rate. Concurrently, the signal-to-noise ratio (SNR) varies gradually from 10 to 50.
The phase transition diagram in Figure shows that DivSBL performs well at more extreme sampling rates and is better suited for lower SNR conditions.

---

Audio OCT damaah
DH-B8L
C00L
PO-SBL
Group
Group RPCA
SeuzOMP
Figure 6: Phase transition diagram under different SNR and measurements.
5,4 2D image reconstruction
In 2DD image experiments, we utilize standard set of grayscale images compiled from sources As depicted in Figure [7] the images exhibit block sparsity in discrete wavelet domain. In Section 5.3 we' shown DivSBL's leading performance across diverse sampling rates. Here, use 0.5 sample rate and the reconstruction errors are in Table 3 and Appendix K DivSBL's reconstructions surpass others, with an average improvement 9.8 % on various images.
Table Reconstructed error (Square root of NMSE + std) of the test images.
Algorithm
Monarch
BSBL
0.139 0.004 0.156 0.006
0.137
0.004
0.179
0.007
0.146
0.007
0,142
1 0.004
0,272 1: 0.009
0.125 :: 0.007
PC-SBL
0.133 0.013 0.150
= 0.012
0.134
0.013
0.013
0,159
0.014
0.137
0.013
0.137 + 0.013
0.208 1 0.010
0.126 + 0.014
SBL
0.225 0.121
0.247
0.144
0.129
0,260
- 0.114
0.238 = 0.125
0.228 + 0.119 0.458
+ 0.106
0.175 = 0.099
GLasso
0.017
0.134
0,141
0.135
0.016
0.216
0.124
0.017
GBPDN
0.138 0.017 0.153
0.017
0.134
0.011
0.159
- 0.019
0.133
= 0.019
0.135
1 0.017
0,218
1 0.022
0,123
: 0.017
0.013
0.014
0.016
DivSBI.
0.117 0.007
0.142
0.006
0.114 0,005
0.008
0.120
0.006
0.120
+ 0.005
0.203 + 0.008
0.101 = 0.007
Original Signal
PC-SBI.
Greup (g) Group
StaaaIIP
Figure 7: Reconstruction results for Parrot, Monarch and House images.
In Figure 7 we display the final reconstructions of Parrot, Monarch and House images as examples. DivSBL capable of preserving the finer features of the parrot, such cheek, eye, etc., and recovering the background smoothly with minimal error stripes. As for Monarch and House images, nearly every reconstruction introduces undesirable artifacts and stripes, while images restored by DivSBL show the least amount of noise patterns, demonstrating the most effective restoration.
6 Conclusions
This paper established a new Bayesian learning model by introducing diversified block sparse prior, to effectively capture the prevalent block sparsity observed in real-world data. The novel Bayesian model effectively solved the sensitivity issue in existing block sparse learning methods, allowing for adaptive block estimation and reducing the risk of overfitting, The proposed algorithm DivSBL, based on this model, enjoyed solid theoretical guarantees on both convergence and sparsity theory. Experimental results demonstrated its state-of-thed of-the-art performance multimodal data. Future works include exploration on more effective weak constraints for correlation matrices, and applications on supervised learning tasks such regression and classification.
Available http://dspp wwwps///wtow////o/oooooooo DDw.aa/////oMMMoooaaaoooooooo http://sce.xddee http:/cwww..iiic..aa////tttt//// wttp.///www.aattt////////////// Exps..btn
10

---

Acknowledgments and Disclosure of Funding
This research was supported by National Key R&D Program of China under grant 2021 YFA 0033000
The authors would like to thank all the reviewers for their helpful comments. Their suggestions have helped us enhance our experiments to present more comprehensive demonstration of the effectiveness of DivSBL.
References
David L Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289-1306 2006.
[2] Irina F Gorodnitsky and Bhaskar D Rao. Sparse signal reconstruction from limited data using FOCUSS: re-weighted minimum norm algorithm. IEEE Transactions on Signal Processing, 45(3):000666,, 1997.
[3] Emmanuel J Candes and Terence Tao. Decoding by linear programming, IEEE Transactions on Information Theory, 51(12):4203 4215, 2005.
[4] Robert Tibshirani. Regression shrinkage and selection via the LASSO. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
[5] Michael Tipping. Sparse Bayesian learning and the relevance vector machine. Journal of Machine Learning Research, (JJu))22112244 2001.
[6] Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1))129-15) 159, 2001.
[7] Yagyensh Chandra Pati, Ramin Rezaiffar, and Perinkulam Sambamurthy Krisnaprasad. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar Conference on Signals, Systems and Computers, 44-44, IEEE, 1993.
[8] Pei Peng. Shirin Jalali, and Xin Yuan. Auto-encoders for compressed sensing. In NeurlPS 2019 Workshop Solving Inverse Problems with Deep Networks, 2019.
[9] Ajil Jalal, Liu Liu, Alexandros G Dimakis, and Constantine Caramanis. Robust compressed sensing using generative models. Advances in Neural Information Processing Systems, 33:713-727, 2020.
[10] Ajil Jalal, Marius Arvinte, Giannis Daras, Eric Price, Alexandros G Dimakis, and Jon Tamir. Robust compressed sensing MRI with deep generative priors, Advances in Neural Information Processing Systems, 34:14938-18 14954, 2021.
[11] Yonina C Eldar, Patrick Kuppinger, and Helmut Boleskei. Block-sparse signals: Uncertainty relations and efficient recovery. IEEE Transactions Signal Processing, 58()):3042-3054 2010.
[12] David L Donoho, lain Johnstone, and Andrea Montanari. Accurate prediction of phase transitions in compressed sensing via a connection to minimax denoising. IEEE Transactions on Information Theory, 3366)3339-3333,, 2013.
[13] Charlie Nash, Jacob Menick, Sander Dieleman, and Peter Battaglia. Generating images with sparse representations. In International Conference on Machine Learning, 7958-7968. PMLR, 2021.
[14] Peng Jiang, Lihan Hu, and Shihui Song. Exposing and exploiting fine-grained block structures for fast and accurate sparse training. Advances in Neural Information Processing Systems, 35:38345-38357, 2022.
[15] Darshan Thaker, Paris Giampouras, and René Vidal. Reverse engineering Ip attacks: block-sparse optimization approach with recovery guarantees. In International Conference on Machine Learning, 21253-21271. PMLR, 2022.
[16] Yuchen Fan, Jiahui Yu, Yiqun Mci, Yulun Zhang, Yun Fu, Ding Liu, and Thomas S Huang. Neural sparse representation for image restoration. Advances in Neural Information Processing Systems, 33:15394-15504, 2020.
[17] Mehdi Korki, Jingxin Zhang, Cishen Zhang, and Hadi Zayyani. Block-sparse impulsive noise reduction in OFDM systems A novel iterative Bayesian approach. IEEE Transactions Communications, 64(1):271-
284, 2015.

---

[18] Aditya Sant, Markus Leinonen, and Bhaskar D Rao. Block-sparse signal recovery via general total variation regularized sparse Bayesian learning. IEEE Transactions on Signal Processing, 70:1056-1071, 2022.
[19] Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Sociery Series B: Statistical Methodology, 68(1):49 4:4967, 2006.
[20] Sahand Negahban and Martin J Wainwright. Joint support recovery under high-dimensional scaling: Benefits and perils of -egulaaaulaiizzaiinn Advances in Neural Information Processing Systems, 21:1161- 1168, 2008.
[21] Yasutoshi Ida, Yasuhiro Fujiwara, and Hisashi Kashima. Fast sparse group LASSO. Advances Neural Information Processing Systems, 32, 2019.
[22] Ewout Van den Berg and Michael P Friedlander. Sparse optimization with least-squares constraints. SIAM Journal on Optimization, 1201 1229, 2011.
[23] Zhilin Zhang and Bhaskar D Rao. Sparse signal recovery with temporally correlated source vectors using sparse Bayesian learning. IEEE Journal of Selected Topics in Signal Processing, 5(5):912-926, 2011.
[24] Zhilin Zhang and Bhaskar Rao. Extension of SBL algorithms for the recovery of black sparse signals with intra- block correlation. IEEE Transactions on Signal Processing. 61(8):2009-20) 2015, 2013.
[25] Zhilin Zhang and Bhaskar D Rao, Recovery of block sparse signals using the framework of block sparse Bayesian learning. In 2012 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 3345-3348. IEEE, 2012.
[26] Junzhou Huang, Tong Zhang, and Dimitris Metaxas. Learning with structured sparsity. In Proceedings of the 26th Annual International Conference Machine Learning, 417-424, 2009.
[27] Jun Fang, Yanning Shen, Hongbin Li, and Pu Wang. Pattem-coupled sparse Bayesian learning for recovery of block-sparse signals. IEEE Transactions on Signal Processing, 6302):300-372, 2014.
[28] Lu Wang, Lifan Zhao, Susanto Rahardja, and Guoan Bi. Alternative to extended block sparse Bayesian learning and its relation to pattern- coopledd sparse Bayesian learning. IEEE Transactions Signal Processing, 66( (0))2))99-2777) 2018.
[29] Jisheng Dai. An Liu, and Hing Cheung So. Non-uniform burst-sparsity learning for massive MIMO channel estimation, IEEE Transactions on Signal Processing, 67(4):1075-1085) 2018
[30] David JC MacKay. Bayesian interpolation. Neural Computation, 4(3):415-447, 1992.
[31] Arthur P Dempster, Nan M I Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the
EM algorithm. Journal of the royal statistical society: series B (methodological), 39(1):1-22, 1977.
[32] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge University Press, 2004.
[33] Yubei Chen, Dylan Paiton, and Bruno Olshausen. The sparse manifold transform. Advances in Neural Information Processing Systems, 31, 2018
[34] Jort F Gemmeke, Daniel PW Bllis, Dylan Freedman, Aren Jansen, Wade Lawrence, R Channing Moore, Manoj Plakal, and Marvin Ritter. Audio set: An ontology and labeled dataset for audio events. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 776-780. IEEE, 2017.
[35] Timothy CY Chan, Rafid Mahmood, and Ian Yihang Zhu. Inverse optimization: Theory and applications. Operations Research, 2023. https://ooi.orr/100. /0..1887/ppe..2022.000
[36] Xinyang Yi and Constantine Caramanis. Regularized FM algorithms: A unified framework and statistical guarantees. Advances in Neural Information Processing Systems, 28, 2015.
[37] David P Wipf, Julia P Owen, Hagai T Attias, Kensuke Sekihara, and Srikantan S Nagarajan. Robust Bayesian estimation of the location, orientation, and time course of multiple correlated neural sources using MEG. Neurolmage, 4964166416 2010.
[38] Shane F Cotter, Bhaskar D Rao, Kjersti Engan, and Kenneth Kreutz-Delgado. Sparse solutions to linear inverse problems with multiple measurement vectors. IEEE Transactions Signal Processing, 53(7):2477-2488, 2005.
[39] Ralph Tyrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
12

---

[40] David G Luenberger and Yinyu Ye. Linear and nonlinear programming, volume 1 116. Springer, 2008.
[41] Carlos M Carvalho, Nicholas G Polson, and James G Scott. Handling spansity via the Horseshoe. In Artificial Intelligence and Statistics, 73-80. PMLR, 2009.
[42] Veronika Ročková and Edward George. The spike-and-slab LASSO. Journal of the American Statistical Association, ):331444, 2018.
[43] Daniela Calvetti, Erkki Somersalo, and A Strang. Hicrachical Bayesian models and sparsity: Ia-magic. Inverse Problems, 35(3):335000)) 2019.
13

---

A Experimental result of diversifying correlation matrices
0.6
0.6
BSBL
BSBL
Diff-BSBL
Diff-SSBL
0.5
DIVSEL (without divensified correlation)
0.5
DNSBB (without diversifed correlation)
DIVSEL
0.4
0.4
NMSE
NMSE
0.3
0.2
0.1
0
100
200
300
400
500
10
Iteration
Iteration
complete itention
(b) The iserations
Figure 8: NMSE with iteration number.
Below, we will explain the necessity of the three steps for updating B in DivSBL:
(1) Firstly, the purpose of the first step, estimating B under strong constraint, is avoid overfitting. As shown by the green line (Diff-BSBL) in Figure [ algorithm without strong constraints tend to worsen NMSE after several iterations due to overfitting.
(2) Since the strong constraint in (1) forces all blocks to have the same correlation, leads to the loss of specificity in correlation matrices within different blocks. Therefore, the motivation for the second step, applying weak constraints, to make the correlations within blocks similar to some extent while preserving their individual specificities. As the black line in Figure 8 ( (DivSBL-without diversified correlation) shows, DivSBL without weak constraints fails to capture the specificity within blocks, resulting in loss of accuracy and slower speed compare DivSBL.
(3) The third step, Toeplitzization, inherits the advantages of BSBL, allowing the correlation matrices to have reasonable structure.
Overall, while BSBL utilizes single variance and a shared correlation matrix within each block, DivSBL incorporates diversification into both variance and correlation matrix modeling, making it more flexible and enhancing its performance.
B Derivation of hyperparameters updating formulas
In this paper, lowercase and uppercase bold symbols are employed to represent vectors and matrices, respectively. det(A) (A) denotes the determinant of matrix A. tr(A) means the trace of A. Matrix diag(A A (A,,..,, 1..... A represents the block diagonal matrix with the matrices {A:]== placed along the main diagonal, and Diag(A) represents the extraction of the diagonal elements from matrix to create vector. We observe that
Q( (B.) - Exly;:r-1 (log Eoo + x Eox)
10
= log Enl
2 tr [E (x + +1p4)))
(26)
in which En be reformulated as
Σg = diag GG, ... ,GG,GG, -D_ (
0
G,B.G. Is 0)
0
D
I
( (VTTP, + Bd w w L 0 0), (27)
0
14

---

where
D-: diag G, ... B.r -LL.B B-11B,11,H GGB.Ggg
P [ أ2ح ,
W diag( VTl v.j-1, Vij+t. v
and the Kronecker delta function here, denoted by ōij, is defined as
1, =
5. 0, otherwise.
Hence, Eg is split into two components in (27 with the second term of the summation only
depending on G; and B,, and the first part D_ being entirely unrelated to them. Then, we can update each B, and G, independently, allowing us to learn diverse B, and G; for different blocks.
The gradient of (26) with respect to V can be expressed
0 - log Col)
0 tr En 1 mp
+
0/76
V
The first term results in
0 log Æol)
0/7 Y6
T6
and the second term yields
a(- 7 tr
2 (E + an )]
=t (P. + n (T))))))
2 0/i
=t [ G (
where 2e E LR represents the i-th block in μ. and Σ RLLL denotes the i-th block in Using A (M- + A2 = A,MA, A,, the formula above can be further transformed into
0 ir Σ (Σ (E+14+))
B
P3
(n G
δ 0/7
VT
+ tr
B
(I
Pj
E
3 Au
T
70
7ij
in which, Tíy and Ai are independent of VTa, and their expressions are
Ts [B, O diag( W - (E' =²(())))
A, = (B, )ز3 (I' + (4')
Thus, the derivative of Q(@) with respect to Viy reads aQ(e)
1 Aij
Tūj-
(28)
a a/70
Vhs
Y
It is important that the variance should be non-negative. So by setting
28 equal zero,
obtain the update formulation of "i as
4A
(29)
T + 4Ai TTy)²
As for the gradient of (26) with respect to B,, we have
aQ 1 [
B
B G +
ØB.
2
Setting it equal to zero, the learning rule for B; is given by
B.=G, Σ
(1 T G
(30)
Using MATLAB notation, je' & u((i 1)L 1 iL), E M(i 1)L 1: : (i +)
+1:
15

---

C
The procedure for solving the constrained optimization problem
To clarify the dual problem of P we firstly express
Lagrange function
(( (1 - log det Eo + 2 tr 2 (2 + up
+
X (log det B; - log det B).
(31)
Since the constraints in P are equalities, we do not impose any requirements on the multipliers {Ar)i- The primal and dual problems terms of L are given by
min max
(B (A)
max
min
[( (A.R)))
(D)
(A.)
(B.
respectively. Although the objective here is non-convex, dual ascent method takes advantage of the fact that the dual problem is always convex [32), and we can get lower bound of (P) by solving (D).
Specifically, dual ascent method employs gradient ascent on the dual variables. As long as the step
sizes chosen properly, the algorithm would converge local maximum. We will demonstrate how to choose the step sizes in the following paragraph.
According to this framework, we first solve the inner minimization problem of the dual problem DD. Keeping the multipliers {>:) fixed, the inner problem
B++1 E arg min B.
C((B. (1 = arg min ((B;;A)); B.
(32)
where the superscript implies the k-th iteration. According to the first-order optimality condition, the primal solution for (32) is follows:
G
Σ + 1 (mt)²) G
B
B
(33)
+ 2
Subsequently, the outer maximization problem for the multiplier A, (dual variable) can addressed using the gradient ascent method. The update formulation is obtained by
X + V (B (m))
X (B, X a det B log det B),
(34)
in which, o represents the step size in the k-th iteration for updating the multiplier X; = 1 1...g). Convergence is only guaranteed if the step size satisfies Σ a o and > (a
[32]
Therefore, we choose a diminishing step size 1/k to ensure the convergence. The procedure, using dual ascent method diversify B, is summarized Algorithm follows:
Algorithm 2 Diversifying B;
1: Input: Initialized X R, 0, the common birra-blok correlation B obtained from
21
2: Output: B,, 1, 1,.... 99-
3: Set iteration count k
4: repeat
5: Set step size a. = 1/k:
6: Update BA++1 using 33
Update + using 34
k:= h
9: until log det B - log det B S.c.
D The computing time and the explanation of one-step dual ascent
Computing time our algorithm based on Bayesian learning and involves covariance structures estimation, it is slower compared to heuristic algorithm StructOMP and solvers like CVX and SPGLI
16

---

(group Lasso, group BPDN). Here, we provide curves of NMSE versus CPU time for DivSBL, DivSBL (with complete dual ascent), and BSBL better visualize the speed of the algorithms. In Figure g DivSBL shows larger NMSE reductions at each time step compared to both BSBL and fully iterative DivSBI..
One-step dual ascent It has been observed that imposing strong constraints B, leads to slow convergence, while not applying any constraints results overfitting (24).
DivSBL DivSBL/Wlth complete dual ascent) BSBL
Therefore, by establishing weak constraints and employing dual ascent to solve the constrained optimization problem (P). we achieve diversifi- cation intra-block correlation matrices, which are more aligned with real-life modeling. Since the convergence speed of dual ascent is fastest in the initial few steps and sub-problems are unnec- essary be solved accurately, our initial moti- vation was to consider allowing it to iterate only once, which yielded promising experimental re- sults, as shown in the Figure
NMSF
0.6
0.4
0.2
0.15
0.3
0.45
0.75
time(s)
Figure 9: Comparison of Computation Time
We consider providing further theoretical and intuitive explanations. From another perspective, the tuple (B++ x satisfying the update formula (3 24 in the text is, in fact, KKT pair of certain constrained optimization problem, which is summarized in Proposition 3.1
Proof of Proposition 3.1
Proof. Construct a weak constraint function & =." + R such that:
VB (
d (B +1)+ (BB
Such a function vb always exists. In fact, we can always construct polynomial function ab that satisfies the given conditions (Hermitte interpolation polynomial). The finite conditions function values and derivatives correspond to a system of linear equations for the coefficients of the polynomial function. Since the degree of the polynomial function is arbitrary, we can always ensure that the system of linear equations has solution by increasing the degree.
Since BB, Q( ) (G.) AB = 0, we have: 11g 12 ( (B
VB, Q
(B (B)
Thus. ((B++)) 1 (1+12)) forms KKT pair of the above optimization problem.
From the proposition above, it can be observed that the tuple (B xx) satisfying equation 23 24 is, fact, a KKT point of certain weakly constrained optimization problem. Therefore, although we do not precisely solve the constrained optimization problem under the weak constraint ((-) (i.e.. log det(-) in the main text), we accurately solve the constrained optimization problem under the weak constraint (-). Even though this weak constraint ei(-) is unknown, it certainly exists and may be better than the original weak constraint ((-). This perspective aligns with the concept of inverse optimization (35. Interestingly, the technique here provides application case for inverse optimization. From this viewpoint, we are still optimizing Q function with the weak constraint ())., and the subproblems under the weak constraint v'(-) are accurately solved. Therefore, similar to the constrained E.M algorithm, it can still generate a sequence of solutions, which explains the experimental results mentioned above.
Meanwhile, the above method can also viewed as regularized EM algorithm (36 The update formula 23 corresponds to the exact solution of the regularized Q function Q (B, [G
17

---

Σ, (((BB) - (())), while equation 24 utilizes gradient descent to update the regularization
parameters.
E Proof of Theorem 4.1
Proof. The posterior estimation of the block sparse signal is given by & = BE +
E0- +
x
& tyy, where En diag G, C, B,
and
G, didgg diag(vTm.
v.
Let v = (fu... nu, fg... >gg))" which is obtained by globally minimizing 35 for given B, (Vi).
min C(y) y E" Σyyy y log det By.
(35)
Inspired by (37, rewrite the first summation term
"" min BByy $x112 x xxxxS _x1x]
Then 35 is equivalent to
min ((>) =
min min {3lly xx + x 2n x} + log det Bny
min min [x" Ey x + log det Σ, } + Blly $x 13
So when + oo, 355 ) is equivalent to minimizing the following problem.
min min [x"=g'=
En-xx x log det Σn
(36)
s. t. y 4x
Let g()) = miny (x* - x + log det E,), then according to Lemma 1 in 37 g(x satisfies
gxx = 0(1) + [M - min ( [M, KT.) log 8-1
where K represents the estimated number of blocks and 8-1 - (noiseless). Therefore, when g(x) achieves its minimum value by (36). K will achieve its minimum value simultaneously.
The results in demonstrate that if Kg < M++1 then no other solution exists such that y $x with < 2L estimated signal & Xine-
22
M+1 Therefore, we have K 2 Ko. and when reaches its minimum value Ko. the
F
Proof of Lemma 4.2
Proof. We can equivalently transform the constraint > ΦΣ I into
Z z $E, + 3 1 - Vo E Thm" mw 2 T
+ :- f
The LHS w Zw linear with respect Z. And for the RHS, th
- wE w-
q" L''nq w-' w, where q xx w, and Eg can bu reformulated
Σn = diag( /Ti 7gt. diag( VTn... Vgr.))
Bn
112
ToL BN1
VoL
BNN
Therefore, RHS= qi Birr + + qiqN BIN / T + + QN BNI
2 BNN + ww vec(qq & BB @ v1) + ww which is linear with respect to
V7 2 V7. In conclusion, Z > x- + 3-
convex with respect to Z and /7 8 /7.
18

---

G Proof of Lemma 4.3
Proof. Given y" E y C' and satisfying y"u C, without loss of generality, choose u - My y, i... y = n Then can be rewritten as
= E - -
$ D b T' u.
(37)
Applying the vectorization operation to both sides of the equation,
37
results in
b vec
( [(u' +)
+ vec (Eo)
[u" 4) @
vec CBC
[(u" ④) @
G x G
vec
B
[uu" (b) @ diag
vec
B
Diag
G @
[(u" b) @ diag
vec
(
(v50v7)
"< Vice versa.
H Proof of Theorem 4.4
Proof. Based on Lemma
we consider the following optimization problem:
min
log det Ey
7
8.
P((7V9))
(38)
7=0,
where Σg = - and are already defined in Lemma 4.3 In order to analyze
the property of the minimization problem (38), we introduce symmetric matrix Z E RMM here. Therefore, the problem with respect to Z and 7 becomes
min 2,7
log det Z
(a.1)
8. b.
Z > DE0 +
(a.2)
P
P
& v =b
(a.3)
0,
(a.4)
It is evident that problem (38 and problem (a) are equivalent. Denote the solution of (a) (Z", Y*), so y here also the solution of (38). Thus, we will analysis the minimization problem (a) instead in the following paragraph.
We first demonstrate the concavity of (a). Obviously, with respect and (v5 VT) the objective function log det Z is concave, and (a.3) is convex. According to Lemma 4.2
a.2
is convex as well.
Hence, we only need show the convexity of (a.4) with respect to Z and
V7).
is observed that
h
h2
7
(VT 2 H(
2
h gr.
where h, A (f.1.... d (gt)) Based on the convexity-preservinn property of
linear transformation B9), the constraint 7 0 exhibits convexity with respect (VT 2 vT).
Therefore, (a) is concave with respect to (V7 x vT) and Z. So we can rewrite (a) as
min Z, 2/
log Z
S. t.
Z > Φ T" + +
P / 8 v7) =b
7 > 0.
19

---

The minimum of (b) will achieve at an extreme point. According to the equivalence between extreme point and basic feasible solution (BFS)
[40] the extreme point of (b) BFS
Z ー + +
I
(V78v7)=1 7
which concludes VI 3 v I
<r(P) M, equivalently I S VM. This result implies that
every local minimum (also BFS to the convex polytope) must be attained at a sparse solution. O
The experiment of 1D signals with block sparsity
L1 The reconstruction results
As mentioned in 2ection2.11.3 homoscedasticity can be seen as a special case of our model. Therefore, we test our algorithm on homoscedastic data provided in [24]. In this dataset, each block shares the same size L = 6, and the amplitudes within each block follow a homoscedastic normal distribution.
The reconstructed results are shown in Figure 10 Figure 3 and the first part of Table 1 DBv demonstrates a significant improvement compared other a glgorithms.
13
10
14 10
(at Original Signal
DivSBL
BSBL
(8) PC-SBL
(e) SBL
(1 Group Laaso
3 Group BPDN
(h) StracIMMP
Figure 10: The original homoscedastic signal and reconstructed results by various algorithms. (N=162, M-80)
we consider heteroscedastic signal, which better reflects the characteristics of real-world data. The recovery results presented in Figure 11 Figure 3 and the second part of Table
Furthermore,
[A) Original Signal
(3)
100
(e)
(1) Groop Lasso
Group HPON
(h) StrectUMP
Figure 1I: The original heteroscedastic signal and reconstructed results by various algorithms (N=16,, M-80)
L,2 Reconstructed by Bayesian methods with credible intervals for point estimation
Here we provide comparative experiments on heteroscedastic data with three classic Bayesian sparse regression methods: Horseshoe model [41], spike-and-slab Lasso 42 and hierarchi- cal normal-gamma method 43 in Figure [22
Regarding the natural advantage of Bayesian methods in quantifying uncertainties for point estimates, further include the posterior fidence intervals from Bayesian methods. As shown in Figure 13 DivSBL offers more stable and accurate posterior confidence intervals.
Figure 12: Reconstruction (NMSE) and correlation.
20

---

(6) DISSBL
(b) BSBL
PC-SBL.
(4) SBL
(e) Horseshov
Normal Normal-Cumma
Figure 13: Confidence intervals for each Bayesian approach.
J The experiment of audio signals
Audio signals display block sparse structures in the discrete cosine transform (DCT) basis. illustrated in Figure 14 the original audio signal (a) transforms into a block sparse structure (b) after DCT transformation.
We carry out experiments on real- world audio signal, which is ran- domly chosen AudioSel [34]. The reconstruction results for audio sig- nals are present in Figure [5] It is noteworthy that DivSBL exhibits improvement over 24.2% % com- pared to other algorithms.
(0) Original Audio Signal
(b) Spurse Representation
Figure 14: The original signal and its sparse representation.
Eat Original Signal
(b) DivSBL
BSBL
(4) PC-SBI
100
202
SBL
Group
2 Group
Figure 15: The sparse audio signal reconstructed by respective algorithms. NMSE: (b) 0.0406 (c) 0.0572 (d) 150)
0.1033 (e) 1014 (f) 0.0536 (g) 0.0669 (h) 0.1062. (N 480,
ONSOL
The sensitivity sample rate As demonstrate in Section 5.3 tested audio sets investigate the sensitivity of sample rate (M/N) varied from 0.25 to 0.55. DivSBL emerges the top performer across diverse sampling rates, exhibiting a consistent 1 dB improvement in NMSE relative the best- performing algorithm, as depicted in Figure 16
PC-S2L
SeyclOuP
Figure 16: NMSE vs. sample rates.
K The experiment of image reconstruction
As depicted in Figure the images exhibit block sparsity in discrete wavelet domain. We've created box plots for NMSE and correlation reconstruction results for each image undergoing restoration,
21

---

as depicted in Figures 18 reconstruction tasks.
25
It's evident that the DivSBL exhibits significant ad advantages in image
400
100
20
40
80
80
100
120
20
40
80
80
100
120
(o) Parnot Image's Spurse Domain
(b) Ulouee Imsuee's ' Spuns Domain
Figure 17: Parrot and House image data (the first five columns) transformed in discrete wavelet domain.
Figure 18: NMSE and Corr for Parrot
Figure 19: NMSE and Corr for House
Figure 20: NMSE and Corr for Lena
Figure 21: NMSE and Corr for Monarch
Figure 22: NMSE and Corr for Cameraman
Figure 23: NMSE and Corr for Boat
Figure 24: NMSE and Corr Foreman
Figure 25: NMSE and Barbara
L The sensitivity to initialization
According to our algorithm, given the variance Tri the prior covariance matrix can be obtained / (dga)))iia(((/ VToL). In the absence of any structural infor-
Eo
22

---

mation, the initial correlation matrix B is set to the identity matrix. Consequently, the mean and covariance matrix for the first iteration can also be determined. Since other variables derived from the variance, we only need to test the sensitivity to the initial values of variances 7.
We test the sensitivity of DivSBL. to initialization Initial variances are set to 7 ranging from 10-1 the convergence speed to some extent, the algorithm' 's overall convergence is assured.
the heteroscedastic signal from Section 5.1 (nes(gL, 1) and 7 = = (g,, 1) with the scale parameter 10 The result in Figure shows that while initialization could affect
v=
0.1
y== 0.1
0.5
02
y 0.5
9=1 1
9=1
4= 10
=
50
V 50
100
100
O
1000
1= 1000
10000
10000
on
(00 midigl, 1)
Figure 26: The sensitivity initialization for DivSBL.
23

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The main claims present in abstract and introduction (Section 1 have reflected the paper's contributions and scope.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: In Theorem 4.1 and Theorem 4.4 we conclude the proof under a noiseless assumption, And we conjecture that similar conclusion hold even in the noise case. In Section [.3] we evaluate the algorithm's 's robustness at different signal-to-noise ratios (SNR). The experimental results consistently show leading performance of the proposed algorithm across various noise environments.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All the theorems and assumptions are clearly stated in Section Appendix
[[ the proof of them.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: For reproducibility, experiment details are provided in each subsection of Section [ Additionally, the code is available in the Supplementary Material.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
25

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
For reproducibility, experiment code available in Supplementary Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.cc.
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7 //nips. htte://bllggguudes/e/eeeee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Ys]]
Justification:
The full details are provided with code.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Ys]]
Justification:
The results are accompanied by confidence intervals, as shown in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
26

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper have provided compute time Section 5 and Appendix Details compute worker are provided in code (README.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics atttps://neurigg htt.///www....cpppooo..ccccccaaa
Answer: [Yes]
Justification:
The research conducted in the paper adheres to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no societal impact of the work performed. The paper aims to explore new technical methods algorithms without delving into topics related societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed. If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
27

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The data and code used in the paper have all been properly credited, and citations are provided in the text.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
28

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
29

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "s65bx8NEta", "reviewer": "Reviewer_rTtn", "summary": "In this work, the authors propose a novel prior called Diversified Block Sparse Prior  towards a new framework to address the problem of recovery of block sparse signals. They provide theoretical and experimental justification as a proof of the efficacy of their work.", "questions": "1. What is the additional burden due to the introduction of diversified prior. Plots of m/p to substantiate the above. \n2. How should the proofs change to include noise?\n3. How does your method compare with PC-SBL, to be added into 2.1.3.\n4. What is the error in estimating B_i in the synthetic case?", "limitations": "This method is effective only with signals that have constant block-size. No sample complexity results are available.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The authors propose a novel diversified block sparse prior which allows for a diversified variance and a diversified correlation. Such a prior can be used to encode/learn the knowledge of DAGs. An EM based solution is derived.", "weaknesses": "This area of research is quite old, and hence, any result that comes about tends to have flavors of several previous works. While the results here are relevant for a journal, I do not find anything exciting in the work which is worth publishing at Neurips. Overall the impact of the work is poor. However, in a stand-alone manner, these are some of the weaknesses:\n1. The length of the block is assumed constant across the blocks. Although the authors claim that the corresponding entries will be zero or non-zero, the model will be forced towards solutions that have a constant non-zero block size. \n2. Lack of sample complexity results: when we introduce new variables into any existing set-up (as compared to B-SBL, the variance here is G_iB_iG_i, which is twice as many parameters) we expect the number of measurements to be larger. Noise also impacts sample complexity. Hence, it is essential to analyse their joint effect on the sample complexity.\n3. Local and global minima results hold in no-noise scenarios: The noisy scenario is presented only as a conjecture. \n4. Although EM iterations are used, a closed form solution for B_i is not available. Authors propose the ascent approach for estimating B_i. This impacts the estimation process, but it has not been clarified. \n5. It is not clear from the experimental settings as to what leads to better results of the proposed algorithm. The algorithm displays better performance in spite of having to estimate additional parameters in G and B. This is possible only if the number of measurements increases. More experimental results based on the ratio, m/p where m denotes the number of observations and p denotes the sparsisity is required.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your valuable questions on our paper. In this rebuttal, we respond to the concerns raised in the reviews.\n\n---\n\n### **Q1 (Constant block size)**: \nThanks for your question. Since the block locations and sizes are unknown in real-world scenarios, block-based methods require a predefined block size to perform estimations. Our observation is that traditional block-based methods are sensitive to the predefined block information because they estimate the elements within a block to be either all zero or all non-zero. As you mentioned, these traditional models will be forced towards solutions that have the constant non-zero predefined block size, leading to significant errors if the block size is misspecified.\n\nIn our approach, by diversification, each variable at a position is controlled by a variance term. The variable selection at each position is determined by the shrinkage of the variance at that position. This addresses the simultaneous zero or non-zero issue, thus making the method robust to the block size.\n\nAlthough our method still requires a predefined block size, which is necessary because we need to learn a correlation matrix $B_i$ with a determined dimension, the predefined block size acts more like an initial point in DivSBL. Through variance shrinkage, DivSBL can eventually find the true block structure. We have further added visualization experiments related to Figure 4 in Section 5.2 of the paper, where the true signal block sizes are highly non-uniform. You can refer to **Fig. 2 in the global rebuttal PDF**, where regardless of whether we choose a small, medium, or large block size, our method can ultimately identify the true block positions through variance shrinkage, which other block-based methods (like BSBL) do not possess.\n\n---\n\n### **Q2 (Sample complexity):**  \nThis is a very good question. We agree that incorporating too many latent variables could be burdensome for recovery. DivSBL involves $n+g$ latent variables (since the correlation matrix $B_i$ for each block retains only one AR parameter through Toeplitz projection), which is a reasonable number in the Bayesian framework. For instance, the Bayesian Fused Lasso model in [1] involves $2n$ latent variables but is still a classic method in structured sparse learning.\n\nHere, our observation is that BSBL involves $g+1$ latent variables (under the strong constraint where $B_i = B$ for each block). This number of latent variables is too few (even fewer than the $n$ latent variables in SBL), making BSBL unable to effectively capture the prior covariance structure. Since elements within a block share a common variance parameter in the BSBL model, they are estimated to be either all zero or all non-zero simultaneously, making the method highly sensitive to the preset block information, as shown in **Figure 4 of our paper and Fig. 2 of the global rebuttal PDF**.\n\nWe have added experiments **in Fig.1 of the global rebuttal PDF** showing the joint impact of observations and noise on the algorithms. Our method remains stable even when observations is close to the number of non-zero elements, supporting our argument: in terms of representing the prior covariance structure, it is not that DivSBL is over-parameterized, but rather that BSBL is under-parameterized.\n\n---\n\n### **Q3 (Theoretical results in noisy case):**  \nThanks for your constructive question. For the global minimum, the proof is a generalization of [2], and it seems hard to relax since the equivalent transformations from (35) to (36) in the paper depend on the assumption of noiselessness.\n\nFor the local minima, we subsequently adjusted the proof, allowing the method to be extended to noisy scenarios. This also validates our conjecture in the paper. **For a detailed proof, please refer to the global rebuttal**.\n\n---\n\n### **Q4 (A closed-form solution in EM):**  \nThanks for your question. As documented in [2], the subproblems of the EM algorithm have close form solutions both in the unconstrained case and under strong constraints. Strong constraints are used to avoid overfitting.\n\nOur contribution lies in proposing a weak constraint framework and provide both explicit and hidden formats for choosing $\\psi$. Subproblems of the EM algorithm with explicit constraints require iterative solving via the dual ascent method, while subproblems with hidden constraints have a closed-form solution for $B_i$, as demonstrated in Proposition 3.1. We also provide comparative experiments in Appendix D to demonstrate the effectiveness of algorithm with hidden constraints.\n\n---\n\n### **Q5 (PC-SBL):**  \nThank you for your insightful question. The prior in PC-SBL is $p(x_i|\\alpha_{i-1},\\alpha_{i},\\alpha_{i+1}) = \\mathcal{N}(x_i;0,(\\alpha_{i} + \\beta \\alpha_{i-1} + \\beta \\alpha_{i+1})^{-1}).$ This pattern-based method, which uses variance coupling between elements rather than learning correlation, differs from block-based DivSBL. Hence, it is not a special case of DivSBL in Section 2.1.3.\n\nIn summary, our proposal of the DivSBL was not aimed at unifying SBL and its variants, nor was it our main contribution. The diversification of variance and correlation matrix had clear motivations and resolved the longstanding sensitivity issue of block-based methods.\n\n---\n\n### **Q6 (Error in estimating $B_i$):**  \nThanks for your question. The correlation matrices $B_i$ in the model are latent variables. Given a block sparse signal $x$, it could be generated by arbitrary correlation matrix $B_i$ of any dimension, hence there is no ground truth for $B_i$ in block sparse recovery. The latent variables $B_i$ are introduced here to better exploit block sparse information, but ultimately, only the target signal $x$ is used to measure errors.\n\n---\n\nReferences:\n\n[1] Casella G, et al. Penalized regression, standard errors, and Bayesian lassos[J]. 2010.\n\n[2] Zhang Z, Rao B D. Sparse signal recovery with temporally correlated source vectors using sparse Bayesian learning[J]. 2011.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ty1b8QScij", "reviewer": "Reviewer_2MRM", "summary": "The authors propose a hierarchical bayesian model for sparse inverse problems where sparsity is structured in blocks. The authors propose a diversified block sparse prior using a structured covariance taking into account both intra block and block-to-block correlations. They propose an EM algorithm to solve the problem, showcase some thereotical properties in noiseless settings and illustrate the performance of their model with synthetic and real datasets.", "questions": "1. Paragraph 2.1.1 should be explained better. I fail to see how the proposed structured covariance would lead to the diversified sparsity (intra block/extra block) regardless of the predefined blocks. But if the method is robust to the chosen blocks, what is their effect then ? Why not let the method discover the blocks by itself ?\n\n2. I fail to see how the proposed method can recover accurate sparsity structures regardless of the predefined blocks. I do not find fig2 helpful\nin this regard. In both conditions (white/pink) the recovered gamma_i are close to 0 ? \n\n3. I believe in  L95 there should be gL*(L+1)/2 constraints ?\n\n4. Is there an intuition behind selecting the constraint function psi ? \n\n5. Where does the toeplitz correction come from ? What is the impact of this step on the convergence of the EM algoritm ? Is this step necessary ?\n\n6. Since the main contribution of the paper is the structured sparsity in groups, in the experiments I would expect the group lasso to perform very well when the groups are known and fixed. Which is not the case here. Is that due to a poor hyperparameter setting ?\n\n- typo: L137 a diversified solution\n\n- typo: L176 the diversified block sparse prior, the following global", "limitations": "none", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Self contained paper\n- Novel and simple model with both theoretical and applied contributions\n- The illustration used to provide the intuition are not easy to understand\n- The theoretical findings are not well motivated / explained and seem out of place / space fillers.\n- The presentation of the paper could be significantly improved (figures hard to read, tiny fonts)", "weaknesses": "- The illustration used to provide the intuition are not easy to understand\n- The theoretical findings are not well motivated / explained and seem out of place / space fillers.\n- The presentation of the paper could be significantly improved (figures hard to read, tiny fonts)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback and constructive suggestions on our paper, which we believe will help enrich the content of the original text. In this rebuttal, we respond to the concerns raised in the reviews.\n\n---\n\n### **Q1**: \nThis is a very good question. Block-based methods require a predefined block size and then estimate based on these blocks. Traditional block-based methods are sensitive to predefined block sizes, as they estimate each block as either all zero or all non-zero. If the block size is misspecified, the method can produce significant errors.\n\nIn our approach, by diversification, each variable is controlled by a corresponding variance term (while in BSBL, all elements within a block are controlled by a single variance term). Variable selection is based on individual variance shrinkage, avoiding the situation where all elements within a block are simultaneously zero or non-zero, thus making the method robust to the block size.\n\nAlthough our method still requires a predefined block size, which is necessary because we need to learn a correlation matrix $B_i$ with a determined dimension, the predefined block size acts more like an initial point in DivSBL. Through variance shrinkage, DivSBL can eventually find the true block structure, as you mentioned. You can refer to **Fig. 2 of the global rebuttal PDF**, where regardless of whether we choose a small, medium, or large block size, our method can ultimately identify the true block positions through variance shrinkage, which other block-based methods (like BSBL) do not possess.\n\n---\n\n### **Q2**: \nWe apologize for the confusion. In Figure 2 of the paper, the ~0 in the pink area indicates that $ \\gamma_i $ is non-zero (not close to zero), while the 0 in the white area indicates that $ \\gamma_i $ is zero. We want to convey that through diversified variance, we can exclude white areas in predefined blocks via variance shrinkage, thereby adaptively finding the true blocks (i.e., the pink areas), as **shown in Fig. 2 of the global rebuttal PDF**.\n\nIn BSBL, all elements within a block share the same $ \\gamma $, which means the elements within a block are estimated to be either all zero or all non-zero simultaneously. Interestingly, if we formulate group Lasso in a Bayesian approach, as suggested in [1], it could be found that all elements in the same block also share a common variance in the prior. That’s why traditional block-based methods have this simultaneous zero or non-zero issue. Our insight is that the key to leveraging block information lies in learning the correlation matrix $ B_i$, rather than having the elements within a block share a common variance parameter.\n\n---\n\n### **Q3**: \nYes, although they are of the same order of magnitude, considering the symmetry of the correlation matrix, the number of constraints should be $ \\frac{gL(L+1)}{2} $. Thanks for your correction.\n\n---\n\n### **Q4**: \nThis is a very good question. Reference [2] documents that if correlation matrices $B_i$ of different blocks are not constrained, it could lead to overfitting. Therefore, a strong constraint $ B_i = B $ is used, meaning that each block has the same correlation matrix to avoid overfitting. Figure 7 in the paper shows that the unconstrained algorithm (green line, Diff-BSBL) is faster initially but suffers from significant error increase later due to overfitting. On the other hand, algorithms with strong constraints (black and blue lines, DivSBL without diversified correlation & BSBL) are slower initially but achieve better accuracy later.\n\nOur motivation is to develop an algorithm that achieves both faster speed and better accuracy. Thus, our contribution lies in proposing a weak constraint framework and providing both explicit and implicit formats for choosing $ \\psi $, which allows the correlation matrix of each block to retain some similarities while preserving their individual specificities. As shown by the red line (DivSBL) in the figure, DivSBL is faster in the early stages and achieves higher accuracy in the later stages. We believe that there might be better ways to select $ \\psi $, and we leave this as future work.\n\n---\n\n### **Q5**: \nThank you for your insightful question. The step of Toeplitz correction originates from BSBL [2] and is necessary, since we need to ensure that $ B_i$ maintains a correlation matrix structure during updates. Therefore, after updating $ B_i $, it needs to be projected onto a correlation matrix. Toeplitz correction provides a feasible and sufficiently simple way to do this, although it does result in some loss of correlation information. We believe that more complex projection methods could be considered, but this is beyond the scope of this paper.\n\n---\n\n### **Q6**: \nThanks for your question. In all of our experiments, the size and location of the blocks are unknown to the algorithm and the classic CVX toolbox is used for solving group Lasso. For block-based methods, we agree that if the blocks are known and fixed, the methods perform well. However, since block information is unknown in real scenarios, block-based methods require preset block information, to which traditional methods are very sensitive, as shown in Figure 4 of the paper.\n\nOur contribution lies in addressing the sensitivity of block-based methods to preset block information via diversification. This way, even if our preset block information is not accurate, we can still adaptively identify the true blocks by variance shrinkage, **as shown in Fig.2 of the global rebuttal PDF**. We further included experiments on the joint effect of noise and the number of observations, demonstrating the advantages of our method in block sparse recovery, **as shown in Fig.1 of the PDF**.\n\n---\n\n\nReferences:\n\n[1] Casella G, Ghosh M, Gill J, et al. Penalized regression, standard errors, and Bayesian lassos[J]. 2010.\n\n[2] Zhang Z and Rao B D. Extension of SBL algorithms for the recovery of block sparse signals with intra-block correlation. 2013.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YMtckeRS6M", "reviewer": "Reviewer_c5nz", "summary": "This paper introduces block sparse bayesian learning for block sparse settings, as motivated by compressed sensing theory. The method relies on a “diversified scheme” which allows for inference that is robust to block choices by modeling intra-block covariance and inter-block correlation. The authors derive an algorithm for learning the model parameters and provide some simple but solid convergence results. They demonstrate their method’s effectiveness on a variety of applications, showing it is more robust than multiple existing and established methods to the prior specification of block information.", "questions": "In practice, when the block structure is misspecified, how well does the proposed method learn the zero variance terms described in e.g. figure 2? How sensitive is the method to initialization?", "limitations": "The authors evaluate the limitations of their work with extensive experiments, as outlined in the checklist. However, the authors could do a better job of addressing the limitations of their work (for example, potential sensitivity to initialization) directly within their paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The method introduced is intuitive. The authors provide a clear description of the EM algorithm and dual ascent method, backing the use of both with theoretical justification. Impressive ground truth and computational results, a technically sound paper overall.", "weaknesses": "Since EM is used for fitting, method may be sensitive to initialization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We deeply appreciate your kind words regarding the clarity of our presentation and the recognition of our theoretical and experimental work. Additionally, we value your insightful questions about initialization and the practical demonstration of the variance term. We will incorporate the content of this rebuttal in the subsequent version of the paper.\n\n---\n\n### **Q1 (Sensitivity to initialization):**  \nThank you for your thorough understanding of DivSBL and your insightful questions. Following your suggestion, we tested the impact of initialization on the DivSBL algorithm. According to our algorithm, given the variance $\\{\\gamma_{ij}\\}$, the prior covariance matrix can be obtained as \n$\\Sigma_0 = \\text{diag}(\\sqrt{\\gamma_{11}}, \\cdots, \\sqrt{\\gamma_{gL}}) B \\text{diag}(\\sqrt{\\gamma_{11}}, \\cdots, \\sqrt{\\gamma_{gL}})$. \nIn the absence of any structural information, the initial correlation matrix $B$ is set to the identity matrix. Consequently, the mean and covariance matrix for the first iteration can also be determined. Since other variables are derived from the variance, we only need to test the sensitivity to the initial values of variances $\\gamma$.\n\n**The results are displayed in Fig.5 in the global rebuttal PDF**. Fig. 5(a) shows the iteration curve with the initial variance vector \n$\n\\gamma = \\eta \\cdot \\text{ones}(g L, 1)\n$\nwhile Fig. 5(b) shows it with \n$\n\\gamma = \\eta \\cdot \\text{rand}(gL, 1)\n$\nThe parameter $\\eta$ varies from $1 \\times 10^{-1}$ to $1 \\times 10^{4}$, representing different initial variance values. We observe that while the initialization could affect the convergence rate to some extent, the algorithm's overall convergence is assured.\n\n---\n\n### **Q2 (Variance learning):**  \nThis is a very good question. The variable selection at each position is determined by the shrinkage of the variance at that position. Through variance shrinkage, DivSBL can eventually find the true block structure, making the method robust to the block size.\n\nBased on your constructive questions, we illustrate the structure of the variance learned at different preset block sizes, **as shown in Fig.2 in the global rebuttal PDF**. We find that, regardless of whether the block size is small, medium, or large, DivSBL consistently shrinks to the true block as expected, which is an achievement other block-based algorithms cannot consistently match.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rjqwa4DHJ6", "reviewer": "Reviewer_KPTu", "summary": "The paper introduces a prior named Diversified Block Sparse Prior, which can be viewed as a generalization of priors for existing sparse Bayesian learning methods. It utilizes EM algorithm and dual ascent to obtain parameter estimates and convergence of estimates to the true parameter in the $\\beta$ limit has been established.", "questions": "See above.", "limitations": "Not Applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The structure of the paper is well organized for readers to follow. Generalization of the existing sparse Bayesian learning methods would provide more flexible framework in sparse regression problems.", "weaknesses": "1. The paper does not mention any of the existing well-known Bayesian sparse regression methods: for instance, horse-shoe prior [1], spike-slab LASSO [2], hierarchical normal-gamma hyperpriors [3], which have been very successful in sparse signal estimation problems. Furthermore, the strength of the Bayesian approach in this problem is in quantifying uncertainties associated with the point estimate. Unlike many frequentist approaches where the construction of confidence intervals requires a more sophisticated debiasing approach, the Bayesian approach provides a natural way to obtain credible intervals for the point estimate. The paper seems to largely ignore such strength of the Bayesian approach.\n\n[1] Carvalho, Carlos M., Nicholas G. Polson, and James G. Scott. \"Handling sparsity via the horseshoe.\" Artificial intelligence and statistics. PMLR, 2009. \n\n[2] Ročková, Veronika, and Edward I. George. \"The spike-and-slab lasso.\" Journal of the American Statistical Association 113.521 (2018): 431-444\n\n[3] Calvetti, Daniela, Erkki Somersalo, and A. Strang. \"Hierachical Bayesian models and sparsity: ℓ2-magic.\" Inverse Problems 35.3 (2019): 035003.\n\n2. The paper establishes theoretical results on local minima in Section 4.2, but this section doesn't seem to add much information about the algorithm. Perhaps the authors should provide more qualitative statements from the established theoretical results, which the current manuscript misses.\n\n3. The current theoretical guarantee only considers the noiseless setting. Is there anything further one could say in the noisy setting?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your feedback and constructive suggestions on our paper, which I believe will help to enrich the content of the original text. In this rebuttal, we respond to the concerns raised in the reviews.\n\n---\n\n### **Q1**:  \nThank you for your suggestions. Since our paper primarily investigates structured block sparsity, we did not pay much attention to purely sparse models. Horseshoe model, spike and slab LASSO, and hierarchical normal-gamma model are indeed classic Bayesian sparse regression methods. Given that our paper is also based on the Bayesian framework, we deeply agree that these classic works should be mentioned, and we are willing to cite these seminal works in the revised version of our paper.\n\nAdditionally, **in the global rebuttal PDF**, we have included comparative experiments (Section 5.1 of the paper) with these three classic methods **in Fig.4**, further illustrating the advantages of DivSBL in block sparse recovery problems. Regarding your point about the natural advantage of Bayesian methods in quantifying uncertainties, we have included the posterior confidence intervals of Bayesian methods **in Fig.3 of the global rebuttal PDF**. As shown in the figure, DivSBL provides more stable and accurate posterior confidence intervals. We will incorporate this point into the revised paper. Once again, we appreciate your constructive feedback.\n\n---\n\n### **Q2**: \nThis is a very good question. The theory established in Section 4 is primarily intended to benchmark against BSBL. As a classic work in the field, BSBL has both theoretical and experimental guarantees. In Section 4, we demonstrate that although the DivSBL model is more complex compared to BSBL, with more latent variables and higher nonlinearity, it still has similar or even better theoretical properties than the BSBL model. (Another classic work in the field, PC-SBL, does not have such theoretical properties.) However, at the algorithmic level, for both BSBL and DivSBL, the conditions under which the algorithm converges to global or local optima have not been established. This is because in non-convex optimization models, whether and when the EM algorithm converges to a global or local solution has been a long-standing problem in the optimization field, although in our experiments, we generally obtain satisfactory solutions in most cases, which, according to Theorem 4.1, are typically global minima. Fortunately, there is now some work that indicates for most common non-convex objective functions in machine learning, most local minima are approximately global minima [1]. However, this is well beyond the scope of this paper.\n\n---\n\n### **Q3**: \nWe sincerely thank the reviewer for your insightful question, which has driven us to further our theoretical advancements. For the global minimum, the proof is a generalization of [2][3], and it seems hard to relax the noiseless condition due to the fact that the equivalent transformations from (35) to (36) in the paper depend on the assumption of noiselessness.\n\nFor the local minimum, we initially used the Schur complement to prove Lemma 4.2, which led to the proof of Theorem 4.4, but this proof was only applicable to the noiseless scenario. We subsequently adjusted the proof, with the core being the direct proof of lines 493-494 in Appendix H of the original paper without relying on Lemma 4.2, allowing the method to be extended to noisy scenarios. This also validates our conjecture in the original paper. **For a detailed proof, please refer to the global rebuttal**.\n\n---\n\nReferences:\n\n[1] Ma T. Why do local methods solve nonconvex problems? [J]. 2020.\n\n[2] Wipf D P, Rao B D. Sparse Bayesian learning for basis selection[J]. IEEE Transactions on Signal processing, 2004, 52(8): 2153-2164.\n\n[3] Zhang Z, Rao B D. Sparse signal recovery with temporally correlated source vectors using sparse Bayesian learning[J]. IEEE Journal of Selected Topics in Signal Processing, 2011, 5(5): 912-926.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
# Global Rebuttal

---

## **1. Experimental Setup in Global Rebuttal PDF**

### **Fig.1:**  
The test data in Fig.1 is sourced from the Audioset described in Section 5.3 of the paper. This audio data contains approximately 90 non-zero elements ($K=90$), which constitutes about 20% of the total dimensionality ($N = 480$). Therefore, we start the test measurements with a sampling rate ($M/N$) of a same 20%. In this scenario, $M/K$ is roughly 1 and increases with the sampling rate. Concurrently, the signal-to-noise ratio (SNR) varies gradually from 10 to 50. The phase transition diagram illustrates that DivSBL performs well at more extreme sampling rates and is better suited for lower SNR conditions.

### **Fig.2:**  
Figure 2 visualizes the posterior variance learning on the signal from Section 5.2 of the paper to demonstrate DivSBL's ability to adaptively identify the true blocks. The block sizes of the three non-zero blocks are 100, 40, and 30, and the algorithms are tested with preset block sizes of 20 (small), 50 (medium), and 125 (large), respectively, to show how each algorithm learns the blocks when the block structure is misspecified. The first row of each subplot shows the distribution of non-zero elements in the original signal, while the subsequent rows display the posterior variance learned by the comparative algorithms. As expected, DivSBL is able to adaptively find the true block through diversification learning and remains robust to the preset block size, validating our discussion in Figure 2 of the paper.

### **Fig.3 & Fig.4:**  
Figures 3 and 4 present experiments on the test signal from Section 5.1 of the paper. Based on the reviewers' valuable suggestions, we have included posterior confidence intervals of the Bayesian methods to better demonstrate the natural advantage of Bayesian models in quantifying uncertainties. Additionally, we have added comparative experiments of recovery errors (NMSE & Correlation) with the horseshoe model, spike & slab LASSO, and hierarchical normal-gamma model for 500 random runs in Fig.4, further illustrating the advantages of DivSBL in block sparse recovery problems.

### **Fig.5:**  
The experiment in Fig.5 tests the sensitivity of DivSBL to initialization on the signal data from Section 5.1 of the paper. Initial variances are set to 
$\gamma = \eta \cdot \text{ones}(g L, 1)$ 
and 
$\gamma = \eta \cdot \text{rand}(gL, 1)$ 
with the scale parameter $\eta$ ranging from $1 \times 10^{-1}$ to $1 \times 10^{4}$. The results show that while initialization could affect the convergence speed to some extent, the algorithm's overall convergence is assured.

---

## **2. The Proof of Local Minima in Noisy Scenario**

We sincerely thank the reviewers for your insightful questions, which have driven us to further our theoretical advancements. Your valuable feedback has been instrumental in enhancing the depth and rigor of our work.

We subsequently adjusted the proof, with the core being the direct proof of lines 493-494 in Appendix H of the original paper without relying on Lemma 4.2, allowing the method to be extended to noisy scenarios. We found that the constraint (a.2) with noise can be proved convex with respect to $Z$ and
$\sqrt{\gamma} \otimes \sqrt{\gamma}$  directly.
The proof is as follows:

### **Proof**

We can equivalently transform the constraint  (a.2) with noise into the following:

$$
Z \succeq \Phi \Sigma_0 \Phi^T + \beta^{-1} I
\Longleftrightarrow \forall \omega \in \mathbb{R}^m, \quad \omega^T Z \omega \geq \omega^T \Phi \Sigma_0 \Phi^T \omega + \beta^{-1} \omega^T \omega.
$$

The LHS $\omega^T Z \omega$ is linear with respect to $Z$. And for the RHS, $\omega^T \Phi \Sigma_0 \Phi^T \omega + \beta^{-1} \omega^T \omega = q^T \Sigma_0 q + \beta^{-1} \omega^T \omega$, where $q = \Phi^T \omega$, and $\Sigma_0$ can be reformulated as:

$$
\Sigma_0 = \text{diag}(\sqrt{\gamma_{11}}, \ldots, \sqrt{\gamma_{gL}}) \tilde{B} \text{diag}(\sqrt{\gamma_{11}}, \ldots, \sqrt{\gamma_{gL}}) 
= \begin{bmatrix}
{\gamma_{11}} \tilde{B}\_{11} & \sqrt{\gamma_{11}} \sqrt{\gamma_{12}} \tilde{B}\_{12} & \ldots & \sqrt{\gamma_{11}} \sqrt{\gamma_{gL}} \tilde{B}\_{1N} \\\\
\vdots & \vdots & & \vdots \\\\
\sqrt{\gamma_{gL}} \sqrt{\gamma_{11}} \tilde{B}\_{N1} & \sqrt{\gamma_{gL}} \sqrt{\gamma_{12}} \tilde{B}\_{N2} & \ldots & {\gamma_{gL}} \tilde{B}\_{NN}
\end{bmatrix}
$$

Therefore, RHS:

$$
\sum_{i=1}^{N} \sum_{j=1}^{N} q_i q_j \tilde{B}\_{ij} \sqrt{\gamma_{i}} \sqrt{\gamma_{j}} + \beta^{-1} \omega^T \omega = \text{vec}(q q^T \odot \tilde{B})^T (\sqrt{\gamma} \otimes \sqrt{\gamma}) + \beta^{-1} \omega^T \omega
$$

which is linear with respect to $\sqrt{\gamma} \otimes \sqrt{\gamma}$.

In conclusion, $Z \succeq \Phi \Sigma_0 \Phi^T + \beta^{-1} I$ is convex with respect to $Z$ and $\sqrt{\gamma} \otimes \sqrt{\gamma}$, which can conclude the proof in Theorem 4.4 in the noisy case ($\forall \beta$).

Meta-review: (*Note: the meta-review has been updated and finalized.*)

Thanks for your submission to NeurIPS! This is a borderline case, where
the reviewers failed to reach a consensus. Considering the overall
comments, feedback and further discussions with the SAC, the
recommendation from the AC is accept as poster.

The AC inclines to support the acceptance of this paper due to the
following points:

- A sound generalization of priors for SBL is proposed, and its
  inference algorithm is studied in theory. This generalization indeed
  broadens the applicability range of SBL, which may have profound
  potentials in practice.

- The weakness points on the fixed and known block size and position in
  review comments could be misunderstanding, probably due to the
  presentation that should be further improved. The experiments have
  considered the case where both are unknown.
  
- The criticism on no guarantee on exact inference of sparsity in theory
  could be the common issue in SBL or even sparse learning in general.
  Except the basic case like LASSO, such strict theoretical guarantees
  are mostly particularly challenging, which are admittedly desired but
  may take longer to be developed.
  
- Most technical questions have been answered in the rebuttal, although
  some reviewers did not follow up further discussions.

However, the authors need to take into account these negative feedback
and comments carefully to improve the paper:
  
- Figures are not satisfactory. The sizes of figures and fonts and their
  positions in paper should be carefully designed: Fig.3 and 5 are
  barely readable due to their particular tiny fontsize; the right
  subfigure in Fig.4 uses the much larger fontsize than the others. The
  authors need to take it serious in preparing the camera-ready. The
  current quality fails to meet the average of NeurIPS.
  
- We strongly suggest the authors to carefully organise/tidy the math
  symbols, and clearly tell what variables are fixed/variable,
  known/unknown. Apparently some reviewers were confused with these
  different setups of hyperparameters, etc. Indeed there are
  complications in the notation system due to the method itself, hence
  your careful writing is particularly favoured to ease understanding
  for readers.

- The theoretical results in Sec.4 may be better motivated and
  explained. A list of theories plainly addressed in math may not be
  much useful for readers to better understand and learn the boundary
  and strengths/weaknesses of your method. 

We thank the authors for your further efforts on preparing the camera-ready and  your contributions to NeurIPS!

Bests,

The AC
Decision: Accept (poster)