Surveying and comparing simultaneous sparse approximation (or group-lasso) algorithms

Abstract

In this paper, we survey and compare different algorithms that, given an overcomplete dictionary of elementary functions, solve the problem of simultaneous sparse signal approximation, with common sparsity profile induced by a ${\ell }_p-{\ell }_q$ mixed-norm. Such a problem is also known in the statistical learning community as the group lasso problem. We have gathered and detailed different algorithmic results concerning these two equivalent approximation problems. We have also enriched the discussion by providing relations between several algorithms. Experimental comparisons of the detailed algorithms have also been carried out. The main lesson learned from these experiments is that depending on the performance measure, greedy approaches and iterative reweighted algorithms are the most efficient algorithms either in term of computational complexities, sparsity recovery or mean-square error.

Introduction

Since several years now, there has been a lot of interest about sparse signal approximation. This large interest comes from frequent wishes of practitioners to represent data in the most parsimonious way.

Recently, researchers have focused their efforts on a natural extension of sparse approximation problem which is the problem of finding jointly sparse representations of multiple signal vectors. This problem is also known as simultaneous sparse approximation and it can be stated as follows. Suppose we have several signals describing the same phenomenon, and each signal is contaminated by noise. We want to find the sparsest approximation of each signal by using the same set of elementary functions. Hence, the problem consists in finding the best approximation of each signal while controlling the number of functions involved in all the approximations.

Such a situation arises in many different application domains such as sensor networks signal processing [30], [11], neuroelectromagnetic imaging [22], [37], [59], source localization [31], image restoration [17], distributed compressed sensing [27] and signal and image processing [24], [49].

Formally, the problem of simultaneous sparse approximation is the following. Suppose that we have measured L signals $\{{\mathbf{s}}_i{\}}_{i=1}^L$ where each signal is of the form ${\mathbf{s}}_i=\mathbf{\Phi }{\mathbf{c}}_i+\epsilon$ where ${\mathbf{s}}_i\in {\mathbb{R}}^N$, $\mathbf{\Phi }\in {\mathbb{R}}^{N\times M}$ is a matrix of unit-norm elementary functions, ${\mathbf{c}}_i\in {\mathbb{R}}^M$ is a weighting vector and $\epsilon$ is a noise vector. $\mathbf{\Phi }$ will be denoted in the sequel as the dictionary matrix. Since we have several signals, the overall measurements can be written as

$$\mathbf{S}=\mathbf{\Phi }\mathbf{C}+\mathcal{E}$$

with $\mathbf{S}=[{\mathbf{s}}_1{\mathbf{s}}_2\cdots {\mathbf{s}}_L]$ is a signal matrix, $\mathbf{C}=[{\mathbf{c}}_1{\mathbf{c}}_2\cdots {\mathbf{c}}_L]$ a coefficient matrix and $\mathcal{E}$ a noise matrix. Note that in the sequel, we have adopted the following notations: $c_{i,·}$ and $c_{·,j}$ respectively denote the i-th row and j-th column of matrix $\mathbf{C}$ and $c_{i,j}$ is the i-th element in the j-th column of $\mathbf{C}$.

For the simultaneous sparse approximation (SSA) problem, the goal is then to recover the matrix $\mathbf{C}$ given the signal matrix $\mathbf{S}$ and the dictionary $\mathbf{\Phi }$ under the hypothesis that all signals ${\mathbf{s}}_i$ share the same sparsity profile. This latter hypothesis can also be translated into the coefficient matrix $\mathbf{C}$ having a minimal number of non-zero rows. In order to measure the number of non-zero rows of $\mathbf{C}$, a possible criterion is the so-called row-support or row-diversity measure of a coefficient matrix defined as

$$\text{rowsupp}(\mathbf{C})=\{i\in [1\cdots M]:c_{i,k}\ne 0\text{for some}k\}$$

The row-support of $\mathbf{C}$ tells us which atoms of the dictionary have been used for building the signal matrix. Hence, if the cardinality of the row-support is lower than the dictionary cardinality, it means that at least one atom of the dictionary has not been used for synthesizing the signal matrix. Then, the row-${\ell }_0$ pseudo-norm of a coefficient matrix can be defined as: $\parallel \mathbf{C}{\parallel }_{\mathit{row}\text{‐}0}=|\text{rowsupp}(\mathbf{C})|$. According to this definition, the simultaneous sparse approximation problem can be stated as

$$\underset{\mathbf{C}}{\min }\frac{1}{2}\parallel \mathbf{S}-\mathbf{\Phi }\mathbf{C}{\parallel }_F^2\mathrm{s}.\mathrm{t}.\parallel \mathbf{C}{\parallel }_{\mathit{row}\text{‐}0}\le T$$

where $\parallel ·{\parallel }_F$ is the Frobenius norm and T a user-defined parameter that controls the sparsity of the solution. Note that the problem can also take the different form:

$$\underset{\mathbf{C}}{\min }\parallel \mathbf{C}{\parallel }_{\mathit{row}\text{‐}0}\mathrm{s}.\mathrm{t}.\frac{1}{2}\parallel \mathbf{S}-\mathbf{\Phi }\mathbf{C}{\parallel }_F\le \epsilon$$

For this latter formulation, the problem translates in minimizing the number of non-zero rows in the coefficient matrix $\mathbf{C}$ while keeping control on the approximation error. Both problems (2) and (3) are appealing for their formulation clarity. However, similarly to the single signal approximation case, solving these optimization problems are notably intractable because $\parallel ·{\parallel }_{\mathit{row}\text{‐}0}$ is a discrete-valued function. Two ways of addressing these intractable problems (2) and (3) are possible: relaxing the problem by replacing the $\parallel ·{\parallel }_{\mathit{row}\text{‐}0}$ function with a more tractable row-diversity measure or by using some suboptimal algorithms.

A large class of relaxed versions of $\parallel ·{\parallel }_{\mathit{row}\text{‐}0}$ proposed in the literature are encompassed into the following form [52]:

$$J_{p,q}(\mathbf{C})=\sum _i\parallel c_{i,·}{\parallel }_q^p\mathrm{with}\parallel c_{i,·}{\parallel }_q={\left(\sum _j|c_{i,j}{|}^q\right)}^{1/q}$$

where typically $p\le 1$ and $q\ge 1$. This penalty term can be interpreted as the ${\ell }_p$ quasi-norm of the sequence $\{\parallel c_{i,·}{\parallel }_q{\}}_i$ to the power p. According to this relaxed version of the row-diversity measure, most of the algorithms proposed in the literature try to solve the relaxed problem:

$$\underset{\mathbf{C}}{\min }\frac{1}{2}\parallel \mathbf{S}-\mathbf{\Phi }\mathbf{C}{\parallel }_F^2+\lambda J_{p,q}(\mathbf{C})$$

where $\lambda$ is another user-defined parameter that balances the approximation error and the sparsity-inducing penalty $J_{p,q}(\mathbf{C})$. The choice of p and q results in a compromise between the row-support sparsity and the convexity of the optimization problem. Indeed, problem (4) is known to be convex when $p,q\ge 1$ while it is known to produce a row-sparse matrix $\mathbf{C}$ if $p\le 1$ (due to the penalty function singularity at $\mathbf{C}=0$ [15]).

The simultaneous sparse approximation problem as described here is equivalent to several other problems studied in other research communities. Problem (4) can be reformulated so as to make clear its relation with some other problems denoted as the ${\ell }_p-{\ell }_q$ group lasso [61] or block-sparse regression [28] in statistics or block-sparse signal recovery [13] in signal processing. Indeed, let us define

$$\tilde{\mathbf{s}}=\left(\begin{array}{c}\hfill {\mathbf{s}}_1\hfill \\ \hfill ⋮\hfill \\ \hfill {\mathbf{s}}_L\hfill \end{array}\right)\tilde{\mathbf{\Phi }}=\left(\begin{array}{ccc}\hfill \mathbf{\Phi }\hfill & \hfill \hfill & \hfill (0)\hfill \\ \hfill \hfill & \hfill \ddots \hfill & \hfill \hfill \\ \hfill (0)\hfill & \hfill \hfill & \hfill \mathbf{\Phi }\hfill \end{array}\right)\tilde{\mathbf{c}}=\left(\begin{array}{c}\hfill {\mathbf{c}}_1\hfill \\ \hfill ⋮\hfill \\ \hfill {\mathbf{c}}_L\hfill \end{array}\right)$$

then, problem (4) can be equivalently rewritten as

$$\underset{\tilde{\mathbf{c}}}{\min }\frac{1}{2}\parallel \tilde{\mathbf{s}}-\tilde{\mathbf{\Phi }}\tilde{\mathbf{c}}{\parallel }_2^2+\lambda J{\prime }_{p,q}(\tilde{\mathbf{c}})$$

where $J{\prime }_{p,q}(\tilde{\mathbf{c}})={\sum }_{i=1}^M\parallel {\tilde{\mathbf{c}}}_{g_i}{\parallel }_q^p$ with $g_i$ being all the indices in $\tilde{\mathbf{c}}$ related to the i-th element of the dictionary matrix $\mathbf{\Phi }$.

As we have already stated, simultaneous sparse approximation and equivalent problems have been investigated by diverse communities and have also been applied to various application problems. Since the literature on these topics has been overwhelming since the last few years. The aim of this work is to gather results from different communities (statistics, signal processing and machine learning) so as to survey, analyze and compare different proposed algorithms for solving optimization problem (4) for different values of p and q. In particular, instead of merely summarizing existing results, we enrich our survey by providing results like proof of convergence, formal relations between different algorithms and experimental comparisons that were not available in the literature. These experimental comparisons essentially focus on the computational complexity of the different methods, on their ability of recovering the signal sparsity pattern and on the quality of approximation they provided evaluated through mean-square error.

Note that recently, there has been various works which addressed the simultaneous sparse approximation in the noiseless case [47], [45] and many works which aim at providing theoretical approximation guarantees in both noiseless and noisy cases [6], [13], [33], [14], [25], [29]. Surveying these works is beyond the scope of this paper and we suggest interested readers to follow for instance these pointers and references therein.

The most frequent case of problem (4) encountered in the literature is the one where $p=1$ and $q=2$. This case is the simpler one since it leads to a convex problem. We discuss different algorithms for solving this problem in Section 2. Then, we survey in Section 3 generic algorithms that are able to solve our approximation problems with different values of p and q. These algorithms are essentially iterative reweighted ${\ell }_1$ or ${\ell }_2$ algorithms. Many works in the literature have focused on one algorithm for solving a particular case of problem (4). These specific algorithms are discussed in Section 4. Notably, we present some greedy algorithms and discuss a sparse Bayesian learning algorithm. The experimental comparisons we carried out aim at clarifying how each algorithm behaves in terms of computational complexity, in sparsity recovery and in approximation mean-square error. These results are described in Section 5. For a sake of reproducibility, the code used in this paper has been made freely available.¹ Final discussions and conclusions are given in Section 6.