A totally unimodular view of structured sparsity

Introduction

Many important machine learning problems reduce to extracting parameters from dimensionality-reduced and potentially noisy data . The most common data model in this setting takes the familiar linear form

In the absence of additional assumptions, it is impossible to reliably learn $\boldsymbol{x}^{\natural}$ when $n\ll p$, since $\boldsymbol{A}$ has a nontrivial nullspace. Hence, we must exploit application-specific knowledge on $\boldsymbol{x}^{\natural}$. This knowledge often imposes $\boldsymbol{x}^{\natural}$ to be simple, e.g., well-approximated by a sparse set of coefficients that obey domain structure. Indeed, structured sparse parameters frequently appear in machine learning, signal processing, and theoretical computer science, and have broader generalizations including structure on matrix-valued $\boldsymbol{x}^{\natural}$ based on its rank.

This paper relies on the convex optimization perspective for structured sparse recovery, which offers a rich set of analysis tools for establishing sample complexity for recovery and algorithmic tools for obtaining numerical solutions . To describe our approach, we focus on the proto-problem

However, choosing convex functions that jointly address simplicity and structure in the proto-problem requires some effort, since their natural descriptions are inherently combinatorial . For instance, sparsity (i.e., the number of nonzero coefficients) of $\boldsymbol{x}^{\natural}$ subject to discrete restrictions on its support (i.e., the locations of the sparse coefficients) initiates many of the structured sparsity problems. Unsurprisingly, there is a whole host of useful convex functions in the literature that induce sparsity with the desiderata in this setting (cf., for a review). The challenge resides in finding computationally tractable convex surrogates that tightly captures the combinatorial models.

To this end, this paper introduces a combinatorial sparse modeling framework that simultaneously addresses both tractability and tightness issues that arise as a result of convex relaxation. In retrospect, our key idea is quite simple and closely follows the recipe in , but with some new twists: We first summarize the discrete constraints that encode structure as linear inequalities. We then identify whether the structural constraint matrix is totally unimodular (TU), which can be verified in polynomial-time . We then investigate classical discrete notions of simplicity and derive the Fenchel biconjugate of the combinatorial descriptions to obtain the convex relaxations for (2).

We illustrate how TU descriptions of simplicity and structure make many popular norms in the literature transparent, such as the (latent) group norm, hierarchical norms, and norms that promote exclusivity. Moreover, we show that TU descriptions of sparsity structures support tight convex relaxations and polynomial-time solution complexity for (2). Our tightness result is a direct corollary of the fact that TU inequalities result in an integral constraint polyhedron where we can optimize linear costs exactly by convex relaxation (cf., Lemma 2).

Preliminaries

We denote scalars by lowercase letters, vectors by lowercase boldface letters, matrices by boldface uppercase letters, and sets by uppercase script letters.

We introduce some definitions that are used in the sequel.

In what follows, some proofs have been omitted due to lack of space; see the supplementary material.

A generative view of sparsity models

It is also interesting to compute the biconjugate of $g(\boldsymbol{x})$ over other unit balls in the Euclidean space, which we will not discuss in this paper. The proof of Lemma 1 is elementary, and is provided for completeness:

The conjugate is a discrete optimization problem which, in general, is hard to solve. Assumption $A2$ guarantees that its convex relaxation has integral optimal solutions, otherwise the last equality will only hold as an upper bound.

Given assumption $A1$, $(\star)$ holds by Sion’s minimax theorem [23, Corollary 3.3]. Assumption $A3$ guarantees that the final convex minimization problem is tractable. ∎

It is worth noting that, without assumption $A2$, the resulting convex function will still be a convex lower bound of $g(\boldsymbol{x})$, albeit not necessarily the tightest one.

Note that in lemma 1, we had to restrict the biconjugate over the box $[-c,c]^{p}$ (with $c=1$), otherwise it would evaluate to a constant. In the sequel, unless otherwise stated, we assume $c=1$ without loss of generality.

In general, computing even the conjugate is a hard problem. If the chosen combinatorial penalty has a tractable conjugate, its envelope can be numerically approximated by a subgradient method .

2 Submodular sparsity models

In the generative modeling approach, non-decreasing submodular functions provide a flexible framework that is quite popular. While the best known method for checking submodularity has sub-exponential time complexity , we can often identify submodular structures by inspection, or we can restrict ourselves to known submodular models that closely approximate our objectives.

In the light of Lemma 1, submodular functions (cf., Def. 1) indeed satisfy the three assumptions, which allow the tractable computation of tight convex relaxations. For instance, the convex envelope of a submodular non-decreasing function is given by its Lovász extension , and optimization with the resulting convex regularizer can be done efficiently. In fact, the corresponding proximity operator is equivalent to solving a submodular minimization problem (SFM) using the minimum-norm point algorithm , which empirically runs in ${O}(p^{2})$-time . However, recent results show that in the worst-case analysis, min-norm point algorithm solves SFM in $O(p^{7})$-time .

Totally unimodular sparsity models

Combinatorial descriptions that satisfy Lemma 1 are not limited to submodular functions. Indeed, we can intuitively model the classical sparsity penalties that encourage the simplest support subject to structure constraints via basic linear inequalities . When the matrix encoding the structure is TU, such models admit tractable convex relaxations that are tight, which is supported by the following.

Let us first provide a simple linear template for TU models:

We define TU penalties as discrete penalties over the support of $\boldsymbol{x}$ that can be written as

By Lemma 2, it follows that TU penalties satisfy the sufficient conditions described in Lemma 1, where the convex extension is the function itself, and the resulting convex envelope is given below.

The convex envelope of a TU penalty is given by the following LP:

Note that when the matrix $M$ in Definition 4 is not TU, the above LP is still useful, since it is a convex lower bound of the penalty, despite being non-tight as noted in Remark 1.

The simplicity description does not need to be a linear function of $\boldsymbol{\omega}$ and $\boldsymbol{s}$. We can often find TU descriptions of higher order interactions that can be “lifted” to result in the linear TU penalty framework (cf., Section 6.3).

A weaker sufficient condition for lemma 2 to hold is for the system $\boldsymbol{M}\boldsymbol{\beta}\leq\boldsymbol{c}$ to be total dual integral (e.g., submodular polyhedra). Then, penalties of the form described in Definition 4 will again satisfy Lemma 1.

Besides allowing tractable tight convexifications, the choice of TU penalties is motivated by their ability to capture several important structures encountered in practice. In what follows, we study several TU penalties and their convex relaxations. We present a reinterpretation of several well-known convex norms in the literature, as well as introduce new ones.

Group sparsity

Group sparsity is an important class of structured sparsity models that arise naturally in machine learning applications (cf., and the citations therein), where prior information on $\boldsymbol{x}^{\natural}$ dictates certain groups of variables to be selected or discarded together.

A group sparsity model thus consists of a collection of potentially overlapping groups $\mathfrak{G}=\{\mathcal{G}_{1},\cdots,\mathcal{G}_{M}\}$ that cover the ground set $\mathcal{P}$, where each group $\mathcal{G}_{i}\subseteq\mathcal{P}$ is a subset of variables. A group structure construction immediately supports two compact graph representations (c.f., Figure 1).

First, we can represent $\mathfrak{G}$ as a bipartite graph , where the groups form one set, and the variables form the other. A variable $i\in\mathcal{P}$ is connected by an edge to a group $\mathcal{G}_{j}\in\mathfrak{G}$ iff $i\in\mathcal{G}_{j}$. We denote by $\boldsymbol{B}\in\{0,1\}^{p\times M}$ the biadjacency matrix of this bipartite graph; $B_{ij}=1$ iff $i\in\mathcal{G}_{j}$, and by $\boldsymbol{E}\in\{0,1\}^{|\mathcal{E}|\times(M+p)}$ its edge-node incidence matrix; $E_{ij}=1$ iff the vertex $j$ is incident to the edge $e_{i}\in\mathcal{E}$. Second, we can represent $\mathfrak{G}$ as an intersection graph , where the vertices are the groups $\mathcal{G}_{i}\in\mathfrak{G}$. Two groups $\mathcal{G}_{i}$ and $\mathcal{G}_{j}$ are connected by an edge iff $\mathcal{G}_{i}\cap\mathcal{G}_{j}\neq\emptyset$. This structure makes it explicit whether groups themselves have cyclic interactions via variables, and identifies computational difficulties.

We now show how to express this penalty as a TU penalty.

where $\boldsymbol{H}$ is the following matrix:

$g_{\mathfrak{G},\cap}(\boldsymbol{x})$ indeed sums up the weight of the groups intersecting with the support, since for any coefficient in the support of $\boldsymbol{x}$ the constraint $\boldsymbol{H}\boldsymbol{\beta}\leq 0$ forces all the groups that contain this coefficient to be selected.

Here, $\boldsymbol{H}$ is TU, since each row of $\boldsymbol{H}$ contains at most two non-zero entries, and the entries in each row with two non-zeros sum up to zero, which is a sufficient condition for total unimodularity [17, Proposition 2.6].

2 Minimal group cover

The groups intersections penalty induces supports corresponding to the intersection of the complements of groups, while in several applications, it is desirable to explain the support of $\boldsymbol{x}^{\natural}$ as the union of groups in $\mathfrak{G}$. In particular, we can seek the minimal set cover of $\boldsymbol{x}^{\natural}$:

where $\boldsymbol{B}$ is the biadjacency matrix of the bipartite graph representation of $\mathfrak{G}$.

3 Sparsity within groups

where $\boldsymbol{M}$ here is either $\boldsymbol{M}=\boldsymbol{H}$ in Definition 5 or $\boldsymbol{M}=[-\boldsymbol{B},\boldsymbol{I}_{p}]$ in Definition 6.

Unfortunately, this penalty leads to a non-TU penalty, and thus its corresponding convex surrogate given by Proposition 1 is not guaranteed to be tight.

Given any group structure $\mathfrak{G}$, $g_{\mathfrak{G},s}(\boldsymbol{x})$ is not a TU penalty.

The convex surrogate via Proposition 1 for $g_{\mathfrak{G},s}(\boldsymbol{x})$ with $\boldsymbol{M}=\boldsymbol{H}$ (i.e., the group intersection model with sparse groups) is given by

for $\boldsymbol{x}\in^{p}$, and $\Omega_{\mathfrak{G},s}(\boldsymbol{x}):=\infty$ otherwise. Note that $\Omega_{\mathfrak{G},s}(\boldsymbol{x})\leq g_{\mathfrak{G},s}^{**}(\boldsymbol{x})$.

By construction, the convex penalty proposed by Proposition 5 is different from the sparse group lasso in .

Analogous to the latent group norm, we can seek to convexify the sparsest set cover with sparsity within groups:

for $\boldsymbol{x}\in^{p}$, and $g(\boldsymbol{x})_{\mathfrak{G},s}=\infty$ otherwise.

4 Sparse G𝐺G-group cover

In this section, we provide a more direct formulation to enforce sparsity both on the coefficients and the group level. If the true signal $\boldsymbol{x}^{\natural}$ we are seeking is a sparse signal covered by at most $G$ groups, it would make sense to look for the sparsest signal with a $G$-group cover that explains the data in (2). This motivates the following natural penalty.

where $\boldsymbol{B}$ is the biadjacency matrix of the bipartite graph representation of $\mathfrak{G}$.

If the actual number of active groups is not known, $G$ would be a parameter to tune. Note that $g_{\mathfrak{G},G}$ is an extension of the minimal group cover penalty (c.f., Section 5.2), where instead of looking for the signal with the smallest cover, we seek the sparsest signal that admit a cover with fewer than $G$ groups. $g_{\mathfrak{G},G}$ is a TU penalty whenever $\widetilde{\boldsymbol{B}}=\begin{bmatrix}\boldsymbol{B}\\ \mathds{1}\end{bmatrix}$is TU [17, Proposition 2.1], which is the case, for example, when $\boldsymbol{B}$ is an interval matrix.

for $\boldsymbol{x}\in^{p}$, and $g_{\mathfrak{G},G}^{\ast\ast}(\boldsymbol{x})=\infty$ otherwise.

5 Hierarchical model

We study the hierarchical sparsity model, where the coefficients of $\boldsymbol{x}^{\natural}$ are organized over a tree $\mathcal{T}$, and the non-zero coefficients form a rooted connected subtree of $\mathcal{T}$ (cf., Figure 4). This model is popular in image processing due to the natural structure of wavelet coefficients . We can describe such a hierarchical model as a TU model:

We define the penalty encoding the hierarchical model on $\boldsymbol{x}$ as

This is indeed a TU model since each row of $\mathcal{T}$ contains at most two non-zero entries that sum up to zero [17, Proposition 2.6].

where the groups $\mathcal{G}\in\mathfrak{G}_{H}$ are defined as each node and all its descendants.

Dispersive sparsity models

The sparsity models we considered thus far encourage clustering. The implicit structure in these models is that coefficients within a group exhibit a positive, reinforcing correlation. Loosely speaking, if a coefficient within a group is important, so are the others. However, in many applications, the opposite behavior may be true. That is, sparse coefficients within a group compete against each other .

Hence, we describe models that encourage the dispersion of sparse coefficients. Here, dispersive models still inherit a known group structure $\mathfrak{G}$, which underlie their interactions in the opposite manner to the group models in Section 5.

One natural model for dispersiveness allows only a certain budget of coefficients, e.g., only one, to be selected in each group:

Note that if $\boldsymbol{B}$ is TU, $\boldsymbol{B}^{T}$ is also TU [17, Proposition 2.1]. Groups that form a partition of $\mathcal{P}$ are acyclic, thus the corresponding matrix $\boldsymbol{B}$ is TU trivially (cf., Remark 5).

Another important example of a TU group structure arises from the simple one-dimensional model of the neuronal signal suggested by . In this model, neuronal signals are seen as a train of spike signals with some refractoriness period $\Delta\geq 0$, where the minimum distance between two non-zeros is $\Delta$. This structure corresponds to an interval matrix $\boldsymbol{B}^{T}=\boldsymbol{D}$, which is TU [17, Corollary 2.10].

2 Sparse group knapsack model

In some applications, it may be desirable to seek the sparsest signal satisfying the dispersive structure. This can be achieved by incorporating sparsity into the group knapsack penalty, resulting in the following TU penalty.

Given a group structure $\mathfrak{G}$ that leads to a TU biadjacency matrix $\boldsymbol{B}$, we define the penalty encoding the sparse group knapsack model on $\boldsymbol{x}$ as

We can compute the convex envelope of $g_{\boldsymbol{D},0}(\boldsymbol{x})$ in a similar fashion to Proposition 9.

We illustrate the effect of this loss of structure via a numerical example in Section 7.

3 Graph dispersiveness

In this section, we illustrate that our framework is not limited to linear costs, by considering a pairwise dispersive model. We assume that the parameter structure is encoded on a known graph $G(\mathcal{P},\mathcal{E})$, where coefficients connected by an edge are discouraged from being on simultaneously.

Given a graph $G(\mathcal{P},\mathcal{E})$ with a TU edge-node incidence matrix $\boldsymbol{E}_{G}$ (e.g., bipartite graph), we define the penalty encoding the pairwise dispersive model as

Note that this function is not submodular; in fact, $g_{\mathcal{G},\mathcal{D}}(\boldsymbol{x})$ is a supermodular function.

Now we can apply Proposition 1 to compute the convex envelope. The resulting convexification is again not a norm (c.f., Figure 7). ∎

Numerical illustration

Figure 8 shows that DBP outperforms BP as we vary the number of measurements. Note that the number of measurements needed to achieve a certain error is expected to be lower for DBP than BP, as theoretically characterized in . Hence, by changing the objective in the convexification, Figure 11 reinforces the message that we can lose the tightness in capturing certain structured sparsity models.

Conclusions

We have provided a principled recipe for designing convex formulations that jointly express models of simplicity and structure for sparse recovery, that promotes clustering or dispersiveness. The main hallmark of our approach is its pithiness in generating the prevalent convex structured sparse formulations and in explaining their tightness. Our key idea relies on expressing sparsity structures via simple linear inequalities over the support of the unknown parameters and their corresponding latent group indicators. By recognizing the totally unimodularity of the underlying constraint matrices, we can tractably compute the biconjugation of the corresponding combinatorial simplicity objective subject to structure, and perform tractable recovery using standard optimization techniques.

This work was supported in part by the European Commission under Grant MIRG-268398, ERC Future Proof, SNF 200021- 132548, SNF 200021-146750 and SNF CRSII2-147633.

Appendix A Numerical illustration of Sparse G𝐺G-group cover’s performance

Appendix B Proof of Proposition 2

Since $g_{\mathfrak{G},\cap}(\boldsymbol{x})$ is a TU-penalty, we can use Proposition 1 in the main text, to compute its convex envelope:

for $\boldsymbol{x}\in^{p}$, $g_{\mathfrak{G},\cap}^{\ast\ast}(\boldsymbol{x})=\infty$ otherwise. ∎

Appendix C Proof of Proposition 3

Note that $g_{\mathfrak{G},0}(\boldsymbol{x})$ can be written in the form given in Definition 4 with $\boldsymbol{M}=[-\boldsymbol{B},\boldsymbol{I}_{p}]$ and $\boldsymbol{c}=0$. Thus, when $\boldsymbol{B}$ is TU, so is $\boldsymbol{M}$ [17, Proposition 2.1], and thus we can use Proposition 1 in the main text, to compute its convex envelope:

for $\boldsymbol{x}\in^{p}$, $g_{\mathfrak{G},0}^{\ast\ast}(\boldsymbol{x})=\infty$ otherwise. ∎

Appendix D Proof of Proposition 4

Given any group structure $\mathfrak{G}$, $g_{\mathfrak{G},s}(\boldsymbol{x})$ is not a TU penalty.

Recall that $\boldsymbol{E}$ is the edge-node incidence matrix of $G(\mathfrak{G}\cup\mathcal{P},\mathcal{E})$. The constraint $\boldsymbol{E}\boldsymbol{\beta}\leq\boldsymbol{z}-\mathds{1}$ corresponds to $z_{ij}\geq\omega_{i}+s_{j}-1,\forall(i,j)\in\mathcal{E}$. Although both matrices $\boldsymbol{M}$ and $\boldsymbol{E}$ are TU, their concatenation $\widetilde{\boldsymbol{M}}=\begin{bmatrix}\boldsymbol{M}\\ \boldsymbol{E}\end{bmatrix}$ is not TU. To see this, let us first focus on the case where $\boldsymbol{M}=[-\boldsymbol{B},\boldsymbol{I}_{p}]$.

Given any coefficient $i\in\mathcal{P}$ covered by at least one group $\mathcal{G}_{i}$, we denote the corresponding edge in the bipartite graph by $e_{j}=(i,M+i)$, which corresponds to the $j^{th}$ row of $\boldsymbol{E}$. This translates into having the entries $\widetilde{\boldsymbol{M}}_{i,i}=-1,\widetilde{\boldsymbol{M}}_{i,M+i}=1,\widetilde{\boldsymbol{M}}_{p+j,i}=1,$ and $\widetilde{\boldsymbol{M}}_{p+j,M+i}=1$. The determinant of the submatrix resulting from these entries is $-2$, which contradicts the definition of TU (cf., Def. 4). It follows then that $\widetilde{\boldsymbol{M}}$ is TU iff $\mathfrak{G}=\{\emptyset\}$.

A similar argument holds for $\boldsymbol{M}=\boldsymbol{H}$. ∎

Appendix E Proof of Proposition 5

The convex surrogate via Proposition 1 in the main text, for $g_{\mathfrak{G},s}(\boldsymbol{x})$ with $\boldsymbol{M}=\boldsymbol{H}$ (i.e., the group intersection model with sparse groups) is given by

for $\boldsymbol{x}\in^{p}$, and, $\Omega_{\mathfrak{G},s}(\boldsymbol{x}):=\infty$ otherwise. Note that $\Omega_{\mathfrak{G},s}(\boldsymbol{x})\leq g_{\mathfrak{G},s}^{**}(\boldsymbol{x})$.

since ${\omega}_{i}^{\ast}=\|\boldsymbol{x}_{\mathcal{G}_{i}}\|_{\infty},{\boldsymbol{s}}^{\ast}=|\boldsymbol{x}|,$ and ${z}_{ij}^{\ast}=({\omega}_{i}^{\ast}+{s}_{j}^{\ast}-1)_{+}$. ∎

Appendix F Proof of Proposition 6

for $\boldsymbol{x}\in^{p}$, $\Omega_{\mathfrak{G},s}(\boldsymbol{x})=\infty$ otherwise.

since ${\boldsymbol{s}^{\ast}}=|\boldsymbol{x}|,$ and ${z}_{ij}^{\ast}=({\omega}_{i}+{s}_{j}^{\ast}-1)_{+}$. ∎

Appendix G Proof of Proposition 8

Since this is a TU-penalty we can use Proposition 1 in the main text, to compute its convex envelope:

for $\boldsymbol{x}\in^{p}$, $\infty$ otherwise, and where the groups $\mathcal{G}\in\mathfrak{G}_{H}$ are defined as each node and all its descendants. $(\star)$ holds since any feasible $\boldsymbol{s}$ should satisfy $\boldsymbol{s}\geq{|\boldsymbol{x}|}$ and $s_{\text{parent}}\geq s_{\text{child}}$, so starting from the leaves, each leaf satisfies $s_{i}\geq|x_{i}|$, and since we are looking to minimize the sum of $s_{i}$’s, we simply set $s_{i}=x_{i}$. For a node $i$ with two children $j,k$ as leaves, it will satisfy $s_{i}\geq|x_{i}|,|s_{j}|,|s_{k}|$, thus $s_{i}=\max\{|x_{i}|,|x_{j}|,|x_{k}|\}$, and so on. Thus, s_{i}=\max_{\{k\text{ is a descendant ofi$or$iitself}\}}{|x_{k}|} ∎

Appendix H Proof of Proposition 9

Since this is a TU penalty we can use Proposition 1 in the main text, to compute its convex envelope:

Appendix I Proof of Proposition 11

Now we can apply Proposition 1 in the main text, to compute the convex envelope:

for $\boldsymbol{x}\in^{p}$, $g_{\mathcal{G},\mathcal{D}}^{\ast\ast}(\boldsymbol{x})=\infty$ otherwise. ∎

References