Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery

I Introduction

The framework of compressed sensing is concerned with the recovery of an unknown vector from an underdetermined system of linear equations . The key property exploited for recovery of the unknown data is the assumption of sparsity. More concretely, denoting by ${\bf x}$ an unknown vector that is observed through a measurement matrix ${{\bf D}}$ according to ${\bf y}={{\bf D}}{\bf x}$, it is assumed that ${\bf x}$ has only a few nonzero entries. A fundamental observation is that if ${{\bf D}}$ is chosen properly and ${\bf x}$ is sufficiently sparse, then ${\bf x}$ can be recovered from ${\bf y}={{\bf D}}{\bf x}$, irrespectively of the locations of the nonzero entries of ${\bf x}$, even if ${{\bf D}}$ has far fewer rows than columns. This result has given rise to a multitude of different recovery algorithms which can be proven to recover a sparse vector ${\bf x}$ under a variety of different conditions on ${{\bf D}}$ .

In this paper, we consider compressed sensing of sparse signals that exhibit additional structure in the form of the nonzero coefficients occurring in clusters. Such signals are referred to as block-sparse . Our goal is to explicitly take this block structure into account, both in terms of the recovery algorithms and in terms of the measures that are used to characterize their performance. The significance of the results we obtain lies in the fact that making explicit use of block-sparsity can provably yield better reconstruction properties than treating the signal as being sparse in the conventional sense, thereby ignoring the additional structure in the problem.

Block-sparsity arises naturally, e.g., when dealing with multi-band signals or in measurements of gene expression levels . Another interesting special case of the block-sparse model appears in the multiple measurement vector (MMV) problem, which deals with the measurement of a set of vectors that share a joint sparsity pattern . Furthermore, it was shown in that the block-sparsity model can be used to treat the problem of sampling signals that lie in a union of subspaces .

The focus of the present paper is on developing a parallel line of results by generalizing the notion of coherence to the block setting. This can be seen as extending the program laid out in to the block-sparse case. Specifically, we define two separate notions of coherence: coherence within a block, referred to as sub-coherence and capturing local properties of the dictionary, and block-coherence, describing global dictionary properties. We will show that both coherence notions are necessary to characterize the essence of block-sparsity. We present extensions of the BP, the matching pursuit (MP), and the OMP algorithms to the block-sparse case and prove corresponding performance guarantees.

We point out that the term block-coherence was used previously in in the context of quantifying the recovery performance of the MP algorithm in block-incoherent dictionaries. Our definition pertains to block-versions of the MP and the OMP algorithm and is different from that used in .

II Block-Sparsity and Block-Coherence

with the indicator function $I(\cdot)$, a block $k$-sparse vector ${\bf x}$ is defined as a vector that satisfies $\|{\bf x}\|_{2,0}\leq k$. In the remainder of the paper conventional sparsity will be referred to simply as sparsity, in contrast to block-sparsity.

The representation (1) is unique if and only if ${{\bf D}}{\bf g}\neq{\bf 0}$ for every ${\bf g}\neq{\bf 0}$ that is block $2k$-sparse.

II-B Block-coherence

The coherence of a dictionary ${{\bf D}}$ measures the similarity between basis elements, and is defined by

It is natural to seek a generalization of coherence to the block-sparse setting with the resulting block-coherence measure having the same operational significance as the coherence $\mu$ in the sparse case. Below, we propose such a generalization, which is shown —in Sections III and IV— to occur naturally in uncertainty relations and in recovery thresholds for the block-sparse case.

We define the block-coherence of ${{\bf D}}$ as

Since the columns of ${{\bf D}}$ have unit norm, the coherence $\mu$ in (5) satisfies $\mu\,\in\,$ and therefore, as a consequence of $\nu\in[0,\mu]$, we have $\nu\,\in\,$. The following proposition establishes the same limits for the block-coherence $\mu_{\operatorname{B}}$, which explains the choice of normalization by $1/d$ in the definition (6).

In the remainder of the paper conventional coherence will be referred to simply as coherence, in contrast to block-coherence and sub-coherence.

The block-coherence $\mu_{\operatorname{B}}$ satisfies $0\leq\mu_{\operatorname{B}}\leq\mu$.

where (9) is a consequence of Geršgorin’s disc theorem ([32, Corollary 6.1.5]). ∎

From $\mu\,\leq\,1$, with Proposition 2, it now follows trivially that $\mu_{\operatorname{B}}\,\leq\,1$.

Using the submultiplicativity of the spectral norm, we have

III Uncertainty Relation for Block-Sparse Signals

We next show how the block-coherence $\mu_{\operatorname{B}}$ defined above naturally appears in an uncertainty relation for block-sparse signals. This uncertainty relation generalizes the corresponding result for the sparse case derived in .

where \mu(\mbox{\boldmath{\Phi}},\mbox{\boldmath{\Psi}}) is the coherence between $\Phi$ and $\Psi$, defined as

It is easily seen that for ${{\bf D}}$ consisting of the orthonormal bases $\Phi$ and $\Psi$, i.e., {{\bf D}}=[\mbox{\boldmath{\Phi}}\,\,\mbox{\boldmath{\Psi}}], we have \mu(\mbox{\boldmath{\Phi}},\mbox{\boldmath{\Psi}})=\mu, where $\mu$ is as defined in (5) and associated with {\bf D}=[\mbox{\boldmath{\Phi}}\,\,\mbox{\boldmath{\Psi}}].

When $\sqrt{L}$ is an integer, the relations in (15) can all be satisfied with equality by choosing ${\bf x}$ as a Dirac comb \mbox{\boldmath{\delta}}_{\sqrt{L}} with spacing $\sqrt{L}$, resulting in $\sqrt{L}$ nonzero elements. This follows from the fact that the Fourier transform of \mbox{\boldmath{\delta}}_{\sqrt{L}} is also \mbox{\boldmath{\delta}}_{\sqrt{L}}.

We now develop an uncertainty relation for block-sparse decompositions. Specifically, we derive a result that is equivalent to (13) with $A$ and $B$ replaced by block-sparsity levels as defined in (4), and \mu(\mbox{\boldmath{\Phi}},\mbox{\boldmath{\Psi}}) replaced by the block-coherence between the orthonormal bases considered, and defined below in (18).

Let $A=\|{\bf a}\|_{2,0}$ and $B=\|{\bf b}\|_{2,0}$. Then,

Note that for ${{\bf D}}$ consisting of the orthonormal bases $\Phi$ and $\Psi$, i.e., {{\bf D}}=[\mbox{\boldmath{\Phi}}\,\,\mbox{\boldmath{\Psi}}], we have \mu_{\operatorname{B}}(\mbox{\boldmath{\Phi}},\mbox{\boldmath{\Psi}})=\mu_{\operatorname{B}}, where $\mu_{\operatorname{B}}$ is as defined in (6) and associated with {{\bf D}}=[\mbox{\boldmath{\Phi}}\,\,\mbox{\boldmath{\Psi}}].

Without loss of generality, we assume that $\|{\bf x}\|_{2}^{2}=1$. Then,

where, for brevity, we wrote \mu_{\operatorname{B}}=\mu_{\operatorname{B}}(\mbox{\boldmath{\Phi}},\mbox{\boldmath{\Psi}}). Substituting into (19), we get

Applying the Cauchy-Schwarz inequality yields

where we used the fact that $\sum_{r=1}^{R}\|{\bf b}[r]\|_{2}^{2}=\|{\bf b}\|_{2}^{2}=1$ since $\|{\bf x}\|_{2}^{2}=1$ and $\Psi$ is unitary. Similarly, we have that $\sum_{r=1}^{R}\|{\bf a}[r]\|_{2}\leq\sqrt{A}$. Substituting into (22) and using the inequality of arithmetic and geometric means completes the proof. ∎

The bound provided by Theorem 1 can be tighter than that obtained by applying the conventional uncertainty relation (13) to the block-sparse case. This can be seen by using $\|{\bf a}\|_{0}\leq d\|{\bf a}\|_{2,0}$ and $\|{\bf b}\|_{0}\leq d\|{\bf b}\|_{2,0}$ in (13) to obtain

Since $\mu_{\operatorname{B}}\,\leq\,\mu$, this bound may be looser than (17).

As already noted, in the sparse case (i.e., $d=1$) for any two orthonormal bases ${\bf\Phi}$ and ${\bf\Psi}$, we have $\mu\,\geq\,1/\sqrt{L}$. We next show that the block-coherence satisfies a similar inequality, namely $\mu_{\operatorname{B}}\,\geq\,1/\sqrt{dL}$.

The block-coherence (18) satisfies $\mu_{\operatorname{B}}\,\geq\,1/\sqrt{dL}$.

When $d=1$, this basis pair reduces to the spike-Fourier pair which is well known to be maximally incoherent .

When $\mu_{\operatorname{B}}$ satisfies (29) the uncertainty relation becomes

If $\sqrt{R}$ is integer, the inequalities in (30) are met with equality for the signal {\bf x}=\mbox{\boldmath{\delta}}_{\sqrt{R}}\otimes{\bf c} where ${\bf c}$ is an arbitrary nonzero length-$d$ vector. Indeed, in this case, the representation of ${\bf x}$ in the spike basis requires $\sqrt{R}$ blocks (of size $d$), so that $\|{\bf a}\|_{2,0}=\sqrt{R}$. The representation of ${\bf x}$ in the basis $\Psi$ in (28) is obtained as

where we used the fact that the Fourier transform of \mbox{\boldmath{\delta}}_{\sqrt{R}} is also \mbox{\boldmath{\delta}}_{\sqrt{R}}. Therefore, ${\bf b}$ has $\sqrt{R}$ nonzero blocks so that $\|{\bf b}\|_{2,0}=\sqrt{R}$ and hence $A=B=\sqrt{R}$, which implies that all inequalities in (30) are met with equality.

IV Efficient Recovery Algorithms

IV-B Recovery conditions

To formally state our main results, suppose that ${\bf x}_{0}$ is a length-$N$ block $k$-sparse vector, and let ${\bf y}={{\bf D}}{\bf x}_{0}$. Let ${{\bf D}}_{0}$ denote the $L\times(kd)$ matrix whose blocks correspond to the nonzero blocks of ${\bf x}_{0}$, and let $\overline{{{\bf D}}}_{0}$ be the matrix of size $L\times(N-kd)$ which contains the $L\,\times\,d$ blocks of ${{\bf D}}$ that are not in ${{\bf D}}_{0}$. We then have the following theorem proved in Section V.

Therefore, (37) implies that for all $r$,

The sufficient condition (37) depends on ${{\bf D}}_{0}$ and therefore on the location of the nonzero blocks in ${\bf x}_{0}$, which, of course, is not known in advance. Nonetheless, as the following theorem, proved in Section V, shows, (37) holds universally under certain conditions on $\mu_{\operatorname{B}}$ and $\nu$ associated with the dictionary ${{\bf D}}$.

Let $\mu_{\operatorname{B}}$ be the block-coherence and $\nu$ the sub-coherence of the dictionary ${{\bf D}}$. Then (37) is satisfied if

BMP picks up a correct block in each step.

V Proofs of Theorems 2, 3, and 4

Before proceeding with the actual proofs, we start with some definitions and basic results that will be used throughout this section.

The following lemma provides bounds on $\|{\mathbf{A}}\|_{2,p}$, which will be used in the sequel.

In particular, $\rho_{r}({\mathbf{A}})=\rho_{c}({\mathbf{A}}^{H})$.

$\rho_{c}({\mathbf{A}})$ as defined in (38) is a matrix norm and as such satisfies the following properties:

Nonnegative: $\rho_{c}({\mathbf{A}})\,\geq\,0$

Positive: $\rho_{c}({\mathbf{A}})=0$ if and only if ${\mathbf{A}}={\bf 0}$

Triangle inequality: $\rho_{c}({\mathbf{A}}+{{\bf B}})\,\leq\,\rho_{c}({\mathbf{A}})+\rho_{c}({{\bf B}})$

Submultiplicative: $\rho_{c}({\mathbf{A}}{{\bf B}})\,\leq\,\rho_{c}({\mathbf{A}})\rho_{c}({{\bf B}})$.

V-B Proof of Theorem 2 for L-OPT

We next show that (37) is also sufficient to ensure recovery using L-OPT. To this end we rely on the following lemma:

To prove that L-OPT recovers the correct vector ${\bf x}_{0}$, let ${\bf x}^{\prime}\,\neq\,{\bf x}_{0}$ be another length-$N$ block $k$-sparse vector for which ${\bf y}={{\bf D}}{\bf x}^{\prime}$. Denote by ${\bf c}_{0}$ and ${\bf c}^{\prime}$ the length-$kd$ vectors consisting of the nonzero elements of ${\bf x}_{0}$ and ${\bf x}^{\prime}$, respectively. Let ${{\bf D}}_{0}$ and ${{\bf D}}^{\prime}$ denote the corresponding columns of ${{\bf D}}$ so that ${\bf y}={{\bf D}}_{0}{\bf c}_{0}={{\bf D}}^{\prime}{\bf c}^{\prime}$. From the assumption in Proposition 1, it follows that there cannot be two different representations using the same blocks ${{\bf D}}_{0}$. Therefore, ${{\bf D}}^{\prime}$ must contain at least one block, ${{\bf Z}}$, that is not included in ${{\bf D}}_{0}$. From (40), we get $\rho_{c}({{\bf D}}_{0}^{\dagger}{{\bf Z}})<1$. For any other block ${{\bf U}}$ in ${{\bf D}}$, we must have that

V-C Proof of Theorem 3

We start by deriving an upper bound on $\rho_{c}({{\bf D}}_{0}^{\dagger}\overline{{{\bf D}}})$ in terms of $\mu_{\operatorname{B}}$ and $\nu$. Writing ${{\bf D}}_{0}^{\dagger}$ out, we have that

Submultiplicativity of $\rho_{c}({\mathbf{A}})$ (Lemma 2) implies that

Suppose that $\rho_{c}({\mathbf{A}})<1$. Then $({{\bf I}}+{\mathbf{A}})^{-1}=\sum_{k=0}^{\infty}(-{\mathbf{A}})^{k}$.

Follows immediately by using the fact that $\rho_{c}({\mathbf{A}})$ is a matrix norm (cf. Lemma 2) and applying [32, Corollary 5.6.16]. ∎

Here, (60) is a consequence of $\rho_{c}({\mathbf{A}})$ satisfying the triangle inequality and being submultiplicative and (61) follows by using (59).

where the last inequality is a consequence of (41).

V-D Proof of Theorem 4

Let ${{\bf D}}_{0}$ denote the $L\times(kd)$ matrix whose blocks correspond to the nonzero blocks of ${\bf x}_{0}$. Then, we have

where we used the fact that ${{\bf M}}[i,i]={{\bf I}}_{d}$, for all $i$, as a consequence of each of the blocks of ${{\bf D}}_{0}$ consisting of orthonormal vectors. Applying the Cauchy-Schwarz inequality to the second term in (65), we get

where (70) follows by the same argument as used in (23). Thus, combining (64) with (70), we get

VI Discussion

Using this lower bound together with Proposition 3 and the fact that after orthogonalization we have $\nu=0$, it can be shown that if $d>RM/(M-R)$, then the recovery threshold obtained from taking block-sparsity into account in the orthogonalized dictionary is higher than the recovery threshold corresponding to conventional sparsity in the original dictionary. This is true irrespectively of the dictionary we start from as long as the dictionary satisfies the conditions of Proposition 1.

Finally, we note that finding dictionaries that lead to significant improvements in the recovery thresholds when exploiting block-sparsity seems to be a difficult design problem. For example, partitioning the realizations of i.i.d. Gaussian matrices into blocks will, in general, not lead to satisfactory results. Nevertheless, there do exist dictionaries where significant improvements are possible. Consider, for example, the pair of bases \mbox{\boldmath{\Phi}}={{\bf I}}_{L} and \mbox{\boldmath{\Psi}}={{\bf F}}\otimes{{\bf U}}_{d} shown in Section III-A to achieve the lower bound in (27). For the corresponding dictionary {{\bf D}}=[\mbox{\boldmath{\Phi}}\,\,\mbox{\boldmath{\Psi}}], we have $M=2R$, $\mu_{\operatorname{B}}=1/(d\sqrt{R})$, with the recovery threshold, assuming that block-sparsity is exploited, given by $kd<d(\sqrt{R}+1)/2$. The coherence of the dictionary is $\mu=\|\textrm{vec}({{\bf U}}_{d})\|_{\infty}/\sqrt{R}$. Fig. 1, obtained by averaging over randomly chosen unitary matrices ${{\bf U}}_{d}$, shows that the recovery thresholds obtained by taking block-sparsity into account can be significantly higher than those for conventional sparsity. In particular, for ${{\bf U}}_{d}={{\bf I}}_{d}$, we obtain the conventional recovery threshold as $k=kd<(\sqrt{R}+1)/2$, which allows us to conclude that exploiting block-sparsity can result in guaranteed recovery for a sparsity level that is $d$ times higher than what would be obtained in the (conventional) sparse case.

VII Numerical Results

The aim of this section is to quantify the improvement in the recovery properties of OMP and BP obtained by taking block-sparsity explicitly into account and performing recovery using BOMP and L-OPT, respectively. In all simulation examples below, we randomly generate dictionaries by drawing from i.i.d. Gaussian matrices and normalizing the resulting columns to $1$. The dictionary is divided into consecutive blocks of length $d$. The sparse vector to be recovered has i.i.d. Gaussian entries on the randomly chosen support set (according to a uniform prior).

In Figs. 2 and 3, we plot the recovery success rateSuccess is declared if the recovered vector is within a certain small Euclidean distance of the original vector. as a function of the block-sparsity level of the signal to be recovered. For each block-sparsity level we average over $1000$ pairs of realizations of the dictionary and the block-sparse signal. We can see that BOMP outperforms OMP significantly and BOMP with orthogonalized blocks, denoted as BOMP-O, yields slightly better performance than BOMP. We also evaluate the performance of L-OPT compared to BP, as well as L-OPT run on orthogonalized blocks, termed L-OPT-O. For each block-sparsity level we average over $200$ pairs of realizations of the dictionary and the block-sparse signal. The corresponding results, depicted in Figs. 4 and 5, show that L-OPT outperforms BP, and L-OPT-O slightly outperforms L-OPT. Furthermore, we can see that BOMP-O significantly outperforms L-OPT-O.

VIII Conclusion

This paper extends the concepts of uncertainty relations, coherence, and recovery thresholds for matching pursuit and basis pursuit to the case of sparse signals that have additional structure, namely block-sparsity. The extension is made possible by an appropriate definition of block-coherence.

The motivation for considering block-sparse signals is two-fold. First, in many applications the nonzero elements of sparse vectors tend to cluster in blocks; several examples are given in . Second, it is shown in that sampling problems over unions of subspaces can be converted into block-sparse recovery problems. Specifically, this is true when the union has a direct-sum decomposition, which is the case in many applications including multiband signals . Reducing union of subspaces problems to block-sparse recovery problems allows for the first general class of concrete recovery methods for union of subspace problems. This was the main contribution of together with equivalence and robustness proofs for L-OPT based on a suitably modified definition of the restricted isometry property. Here, we complement this contribution by developing similar results using the concept of block-coherence.

Appendix A Proof of Lemma 1

which establishes (46). The proof of (47) is similar:

Appendix B Proof of Lemma 2

Nonnegativity and positivity follow immediately from the fact that the spectral norm is a matrix norm [32, p. 295]. Homogeneity follows by noting that

The triangle inequality is obtained as follows:

where the first inequality is a consequence of the spectral norm satisfying the triangle inequality.

Finally, to verify submultiplicativity, note that,

where we used the triangle inequality for, and the submultiplicativity of, the spectral norm. Now, we have

Appendix C Proof of Lemma 3

References