Network Flow Algorithms for Structured Sparsity

Introduction

By considering sums of norms of appropriate subsets, or groups, of variables, these regularizations control the sparsity patterns of the solutions. The underlying optimization problem is usually difficult, in part because it involves nonsmooth components. Proximal methods have proven to be effective in this context, essentially because of their fast convergence rates and their ability to deal with large problems . While the settings where the penalized groups of variables do not overlap or are embedded in a tree-shaped hierarchy have already been studied, sparsity-inducing regularizations of general overlapping groups have, to the best of our knowledge, never been considered within the proximal method framework.

This paper makes the following contributions:

It shows that the proximal operator associated with the structured norm we consider can be computed by solving a quadratic min-cost flow problem, thereby establishing a connection with the network flow optimization literature.

It presents a fast and scalable procedure for solving a large class of structured sparse regularized problems, which, to the best of our knowledge, have not been addressed efficiently before.

It shows that the dual norm of the sparsity-inducing norm we consider can also be evaluated efficiently, which enables us to compute duality gaps for the corresponding optimization problems.

It demonstrates that our method is relevant for various applications, from video background subtraction to estimation of hierarchical structures for dictionary learning of natural image patches.

Structured Sparse Models

We consider in this paper convex optimization problems of the form

If ${\mathcal{G}}$ is a more general partition of $[1;p]$, variables are selected in groups rather than individually. When the groups overlap, $\Omega$ is still a norm and sets groups of variables to zero together . The latter setting has first been considered for hierarchies , and then extended to general group structures .Note that other types of structured sparse models have also been introduced, either through a different norm , or through non-convex criteria . Solving Eq. (1) in this context becomes challenging and is the topic of this paper. Following who tackled the case of hierarchical groups, we propose to approach this problem with proximal methods, which we now introduce.

In a nutshell, proximal methods can be seen as a natural extension of gradient-based techniques, and they are well suited to minimizing the sum $f+\lambda\Omega$ of two convex terms, a smooth function $f$ —continuously differentiable with Lipschitz-continuous gradient— and a potentially non-smooth function $\lambda\Omega$ (see and references therein). At each iteration, the function $f$ is linearized at the current estimate ${\mathbf{w}}_{0}$ and the so-called proximal problem has to be solved:

The quadratic term keeps the solution in a neighborhood where the current linear approximation holds, and $L\!>\!0$ is an upper bound on the Lipschitz constant of $\nabla f$. This problem can be rewritten as

A Quadratic Min-Cost Flow Formulation

Without loss of generality, Let ${\boldsymbol{\xi}}^{\star}$ denote a solution of Eq. (4). Optimality conditions of Eq. (4) derived in show that for all $j$ in $[1;p]$, the signs of the non-zero coefficients ${\boldsymbol{\xi}}_{j}^{\star g}$ for $g$ in ${\mathcal{G}}$ are the same as the signs of the entries ${\mathbf{u}}_{j}$. To solve Eq. (4), one can therefore flip the signs of the negative variables ${\mathbf{u}}_{j}$, then solve the modified dual formulation (with non-negative variables), which gives the magnitude of the entries ${\boldsymbol{\xi}}_{j}^{\star g}$ (the signs of these being known). we assume from now on that the scalars ${\mathbf{u}}_{j}$ are all non-negative, and we constrain the entries of ${\boldsymbol{\xi}}$ to be non-negative. We now introduce a graph modeling of problem (4).

We introduce a canonical graph $G$ associated with our optimization problem, and uniquely characterized by the following construction: (i) $V$ is the union of two sets of vertices $V_{u}$ and $V_{gr}$, where $V_{u}$ contains exactly one vertex for each index $j$ in $[1;p]$, and $V_{gr}$ contains exactly one vertex for each group $g$ in ${\mathcal{G}}$. We thus have $|V|=|{\mathcal{G}}|+p$. For simplicity, we identify groups and indices with the vertices of the graph. (ii) For every group $g$ in ${\mathcal{G}}$, $E$ contains an arc $(s,g)$. These arcs have capacity $\lambda\eta_{g}$ and zero cost. (iii) For every group $g$ in ${\mathcal{G}}$, and every index $j$ in $g$, $E$ contains an arc $(g,j)$ with zero cost and infinite capacity. We denote by ${\boldsymbol{\xi}}_{j}^{g}$ the flow on this arc. (iv) For every index $j$ in $[1;p]$, $E$ contains an arc $(j,t)$ with infinite capacity and a cost $c_{j}\!\triangleq\!\frac{1}{2}({\mathbf{u}}_{j}-{\boldsymbol{\bar{\xi}}}_{j})^{2}$, where ${\boldsymbol{\bar{\xi}}}_{j}$ is the flow on $(j,t)$. Note that by flow conservation, we necessarily have ${\boldsymbol{\bar{\xi}}}_{j}\!=\!\sum_{g\in{\mathcal{G}}}{{\boldsymbol{\xi}}_{j}^{g}}$.

Examples of canonical graphs are given in Figures 1(a)-1(c). The flows ${\boldsymbol{\xi}}_{j}^{g}$ associated with $G$ can now be identified with the variables of problem (4): indeed, the sum of the costs on the edges leading to the sink is equal to the objective function of (4), while the capacities of the arcs $(s,g)$ match the constraints on each group. This shows that finding a flow minimizing the sum of the costs on such a graph is equivalent to solving problem (4).

When some groups are included in others, the canonical graph can be simplified to yield a graph with a smaller number of edges. Specifically, if $h$ and $g$ are groups with $h\subset g$, the edges $(g,j)$ for $j\in h$ carrying a flow ${\boldsymbol{\xi}}^{g}_{j}$ can be removed and replaced by a single edge $(g,h)$ of infinite capacity and zero cost, carrying the flow $\sum_{j\in h}{\boldsymbol{\xi}}^{g}_{j}$. This simplification is illustrated in Figure 1(d), with a graph equivalent to the one of Figure 1(c). This does not change the optimal value of ${\boldsymbol{\bar{\xi}}}^{\star}$, which is the quantity of interest for computing the optimal primal variable ${\mathbf{w}}^{\star}$. We present in Appendix A a formal definition of equivalent graphs. These simplifications are useful in practice, since they reduce the number of edges in the graph and improve the speed of the algorithms we are now going to present.

2 Computation of the Proximal Operator

The general case of overlapping groups is more difficult. Hochbaum and Hong have shown in that quadratic min-cost flow problems can be reduced to a specific parametric max-flow problem, for which an efficient algorithm exists .By definition, a parametric max-flow problem consists in solving, for every value of a parameter, a max-flow problem on a graph whose arc capacities depend on this parameter. While this approach could be used to solve Eq. (4), it ignores the fact that our graphs have non-zero costs only on edges leading to the sink. To take advantage of this specificity, we propose the dedicated Algorithm 1. Our method clearly shares some similarities with a simplified version of presented in , namely a divide and conquer strategy. Nonetheless, we performed an empirical comparison described in Appendix D, which shows that our dedicated algorithm has significantly better performance in practice.

The approach of is guaranteed to have the same worst-case complexity as a single max-flow algorithm. However, we have experimentally observed a significant discrepancy between the worst case and empirical complexities for these flow problems, essentially because the empirical cost of each max-flow is significantly smaller than its theoretical cost. Despite the fact that the worst-case guarantee of our algorithm is weaker than their (up to a factor $|V|$), it is more adapted to the structure of our graphs and has proven to be much faster in our experiments (see supplementary material).

Some implementation details are crucial to the efficiency of the algorithm:

Exploiting maximal connected components: When there exists no arc between two subsets of $V$, it is possible to process them independently to solve the global min-cost flow problem. To that effect, before calling the function computeFlow($V,E$), we look for maximal connected components $(V_{1},E_{1}),\ldots,(V_{N},E_{N})$ and call sequentially the procedure computeFlow($V_{i},E_{i}$) for $i$ in $[1;N]$.

Efficient max-flow algorithm: We have implemented the “push-relabel” algorithm of to solve our max-flow problems, using classical heuristics that significantly speed it up in practice (see ). Our implementation uses the so-called “highest-active vertex selection rule, global and gap heuristics” (see ), and has a worst-case complexity of $O(|V|^{2}|E|^{1/2})$ for a graph $(V,E,s,t)$. This algorithm leverages the concept of pre-flow that relaxes the definition of flow and allows vertices to have a positive excess.

Using flow warm-restarts: Our algorithm can be initialized with any valid pre-flow, enabling warm-restarts when the max-flow is called several times as in our algorithm.

Improved projection step: The first line of the procedure computeFlow can be replaced by ${\boldsymbol{\gamma}}\leftarrow\operatornamewithlimits{arg\,min}_{\boldsymbol{\gamma}}\sum_{j\in V_{u}}\frac{1}{2}({\mathbf{u}}_{j}-{\boldsymbol{\gamma}}_{j})^{2}~{}~{}\text{s.t.}~{}~{}\sum_{j\in V_{u}}{\boldsymbol{\gamma}}_{j}\leq\lambda\sum_{g\in V_{gr}}\eta_{g}~{}\text{and}~{}|{\boldsymbol{\gamma}}_{j}|\leq\lambda\sum_{g\ni j}\eta_{g}.$ The idea is that the structure of the graph will not allow ${\boldsymbol{\bar{\xi}}}_{j}$ to be greater than $\lambda\sum_{g\ni j}\eta_{g}$ after the max-flow step. Adding these additional constraints leads to better performance when the graph is not well balanced. This modified projection step can still be computed in linear time .

3 Computation of the Dual Norm

In the network problem associated with (12), the capacities on the arcs $(s,g)$, $g\in{\mathcal{G}}$, are set to $\tau\eta_{g}$, and the capacities on the arcs $(j,t)$, $j$ in $[1;p]$, are fixed to ${\boldsymbol{\kappa}}_{j}$. Solving problem (12) amounts to finding the smallest value of $\tau$, such that there exists a flow saturating the capacities ${\boldsymbol{\kappa}}_{j}$ on the arcs leading to the sink $t$ (i.e., ${\boldsymbol{\bar{\xi}}}={\boldsymbol{\kappa}}$). Equration (12) and the algorithm below are proven to be correct in Appendix B.

Applications and Experiments

Our experiments use the algorithm of based on our proximal operator, with weights $\eta_{g}$ set to $1$. We present this algorithm in more details in Appendix C.

In our experiments, the regularization parameter $\lambda$ is chosen to achieve this level of sparsity. For SG, we take the step size to be equal to $a/(k+b)$, where $k$ is the iteration number, and $(a,b)$ are the best parameters selected in $\{10^{-3},\dots,10\}\!\times\!\{10^{2},10^{3},10^{4}\}$. For the interior point methods, since problem (1) can be cast either as a quadratic (QP) or as a conic program (CP), we show in Figure 2 the results for both formulations. Our approach compares favorably with the other methods, on three problems of different sizes, $(n,p)\in\{(100,10^{3}),(1024,10^{4}),(1024,10^{5})\}$, see Figure 2. In addition, note that QP, CP and SG do not obtain sparse solutions, whereas ProxFlow does. We have also run ProxFlow and SG on a larger dataset with $(n,p)=(100,10^{6})$: after $12$ hours, ProxFlow and SG have reached a relative duality gap of $0.0006$ and $0.02$ respectively.Due to the computational burden, QP and CP could not be run on every problem.

2 Background Subtraction

3 Multi-Task Learning of Hierarchical Structures

Inspired by ideas from multi-task learning , we propose to learn the tree structure $\mathcal{T}$ by pruning irrelevant parts of a larger initial tree $\mathcal{T}_{0}$. We achieve this by using an additional regularization term $\Omega_{\text{joint}}$ across the different decompositions, so that subtrees of $\mathcal{T}_{0}$ will simultaneously be removed for all signals ${\mathbf{y}}^{i}$. In other words, the approach of is extended by the following formulation:

Conclusion

Appendix A Equivalence to Canonical Graphs

Formally, the notion of equivalence between graphs can be summarized by the following lemma:

Let $G=(V,E,s,t)$ be the canonical graph corresponding to a group structure ${\mathcal{G}}$ with weights $(\eta_{g})_{g\in{\mathcal{G}}}$. Let $G^{\prime}=(V,E^{\prime},s,t)$ be a graph sharing the same set of vertices, source and sink as $G$, but with a different arc set $E^{\prime}$. We say that $G^{\prime}$ is equivalent to $G$ if and only if the following conditions hold:

Arcs of $E^{\prime}$ outgoing from the source are the same as in $E$, with the same costs and capacities.

Arcs of $E^{\prime}$ going to the sink are the same as in $E$, with the same costs and capacities.

For every arc $(g,j)$ in $E$, with $(g,j)$ in $V_{gr}\times V_{u}$, there exists a unique path in $E^{\prime}$ from $g$ to $j$ with zero costs and infinite capacities on every arc of the path.

Conversely, if there exists a path in $E^{\prime}$ between a vertex $g$ in $V_{gr}$ and a vertex $j$ in $V_{u}$, then there exists an arc $(g,j)$ in $E$.

Then, the cost of the optimal min-cost flow on $G$ and $G^{\prime}$ are the same. Moreover, the values of the optimal flow on the arcs $(j,t)$, $j$ in $V_{u}$, are the same on $G$ and $G^{\prime}$.

Proof. We first notice that on both $G$ and $G^{\prime}$, the cost of a flow on the graph only depends on the flow on the arcs $(j,t)$, $j$ in $V_{u}$, which we have denoted by ${\boldsymbol{\bar{\xi}}}$ in $E$.

We will prove that finding a feasible flow $\pi$ on $G$ with a cost $c(\pi)$ is equivalent to finding a feasible flow $\pi^{\prime}$ on $G^{\prime}$ with the same cost $c(\pi)=c(\pi^{\prime})$. We now use the concept of path flow, which is a flow vector in $G$ carrying the same positive value on every arc of a directed path between two nodes of $G$. It intuitively corresponds to sending a positive amount of flow along a path of the graph.

According to the definition of graph equivalence introduced in the Lemma, it is easy to show that there is a bijection between the arcs in $E$, and the paths in $E^{\prime}$ with positive capacities on every arc. Given now a feasible flow $\pi$ in $G$, we build a feasible flow $\pi^{\prime}$ on $G^{\prime}$ which is a sum of path flows. More precisely, for every arc $a$ in $E$, we consider its equivalent path in $E^{\prime}$, with a path flow carrying the same amount of flow as $a$. Therefore, each arc $a^{\prime}$ in $E^{\prime}$ has a total amount of flow that is equal to the sum of the flows carried by the path flows going over $a^{\prime}$. It is also easy to show that this construction builds a flow on $G^{\prime}$ (capacity and conservation constraints are satisfied) and that this flow $\pi^{\prime}$ has the same cost as $\pi$, that is, $c(\pi)=c(\pi^{\prime})$.

Conversely, given a flow $\pi^{\prime}$ on $G^{\prime}$, we use a classical path flow decomposition (see Proposition 1.1 in ), saying that there exists a decomposition of $\pi^{\prime}$ as a sum of path flows in $E^{\prime}$. Using the bijection described above, we know that each path in the previous sums corresponds to a unique arc in $E$. We now build a flow $\pi$ in $G$, by associating to each path flow in the decomposition of $\pi^{\prime}$, an arc in $E$ carrying the same amount of flow. The flow of every other arc in $E$ is set to zero. It is also easy to show that this builds a valid flow in $G$ that has the same cost as $\pi^{\prime}$.

Appendix B Convergence Analysis

We show in this section the correctness of Algorithm 1 for computing the proximal operator, and of Algorithm 2 for computing the dual norm $\Omega^{\star}$.

We now prove that our algorithm converges and that it finds the optimal solution of the proximal problem. This requires that we introduce the optimality conditions for problem (4) derived in , since our convergence proof essentially checks that these conditions are satisfied upon termination of the algorithm.

The primal-dual variables $({\mathbf{w}},{\boldsymbol{\xi}})$ are respectively solutions of the primal (3) and dual problems (4) if and only if the dual variable ${\boldsymbol{\xi}}$ is feasible for the problem (4) and

Note that these optimality conditions provide an intuitive view of our min-cost flow problem. Solving the min-cost flow problem is equivalent to sending the maximum amount of flow in the graph under the capacity constraints, while respecting the rule that the flow outgoing from a group $g$ should always be directed to the variables ${\mathbf{u}}_{j}$ with maximum residual ${\mathbf{u}}_{j}-\sum_{g\in\mathcal{G}}{\boldsymbol{\xi}}^{g}_{j}$.

Before proving the convergence and correctness of our algorithm, we also recall classical properties of the min capacity cuts, which we intensively use in the proofs of this paper. The procedure computeFlow of our algorithm finds a minimum $(s,t)$-cut of a graph $G=(V,E,s,t)$, dividing the set $V$ into two disjoint parts $V^{+}$ and $V^{-}$. $V^{+}$ is by construction the sets of nodes in $V$ such that there exists a non-saturating path from $s$ to $V$, while all the paths from $s$ to $V^{-}$ are saturated. Conversely, arcs from $V^{+}$ to $t$ are all saturated, whereas there can be non-saturated arcs from $V^{-}$ to $t$. Moreover, the following properties hold

There is no arc going from $V^{+}$ to $V^{-}$. Otherwise the value of the cut would be infinite. (Arcs inside $V$ have infinite capacity by construction of our graph).

There is no flow going from $V^{-}$ to $V^{+}$ (see properties of the minimum $(s,t)$-cut ).

The cut goes through all arcs going from $V^{+}$ to $t$, and all arcs going from $s$ to $V^{-}$.

All these properties are illustrated on Figure 5.

Recall that we assume (cf. Section 3.1) that the scalars ${\mathbf{u}}_{j}$ are all non negative, and that we add non-negativity constraints on ${\boldsymbol{\xi}}$. With the optimality conditions of Lemma 3 in hand, we can show our first convergence result.

Algorithm 1 converges in a finite and polynomial number of operations.

Suppose for instance that $V^{-}\!\!=\emptyset$. In this case, the capacity of the min-cut is equal to $\sum_{j\in V_{u}}{\boldsymbol{\gamma}}_{j}$, and the value of the max-flow is $\sum_{j\in V_{u}}{\boldsymbol{\bar{\xi}}}_{j}$. Using the classical max-flow/min-cut theorem , we have equality between these two terms. Since, by definition of both ${\boldsymbol{\gamma}}$ and ${\boldsymbol{\bar{\xi}}}$, we have for all $j$ in $V_{u}$, ${\boldsymbol{\bar{\xi}}}_{j}\leq{\boldsymbol{\gamma}}_{j}$, we obtain a contradiction with the existence of $j$ in $V_{u}$ such that ${\boldsymbol{\bar{\xi}}}_{j}\neq{\boldsymbol{\gamma}}_{j}$.

Conversely, suppose now that $V^{+}\!\!=\emptyset$. Then, the value of the max-flow is still $\sum_{j\in V_{u}}{\boldsymbol{\bar{\xi}}}_{j}$, and the value of the min-cut is $\lambda\sum_{g\in V_{gr}}\eta_{g}$. Using again the max-flow/min-cut theorem, we have that $\sum_{j\in V_{u}}{\boldsymbol{\bar{\xi}}}_{j}=\lambda\sum_{g\in V_{gr}}\eta_{g}$. Moreover, by definition of ${\boldsymbol{\gamma}}$, we also have $\sum_{j\in V_{u}}{\boldsymbol{\bar{\xi}}}_{j}\leq\sum_{j\in V_{u}}{\boldsymbol{\gamma}}_{j}\leq\lambda\sum_{g\in V_{gr}}\eta_{g}$, leading to a contradiction with the existence of $j$ in $V_{u}$ such that ${\boldsymbol{\bar{\xi}}}_{j}\neq{\boldsymbol{\gamma}}_{j}$. This proof holds for any graph that is equivalent to the canonical one. After proving the convergence, we prove that the algorithm is correct with the next proposition.

Algorithm 1 solves the proximal problem of Eq. (3).

Proof. For a group structure ${\mathcal{G}}$, we first prove the correctness of our algorithm if the graph used is its associated canonical graph that we denote $G_{0}=(V_{0},E_{0},s,t)$. We proceed by induction on the number of nodes of the graph. The induction hypothesis ${\mathcal{H}}(k)$ is the following: For all canonical graphs $G=(V=V_{u}\cup V_{gr},E,s,t)$ associated with a group structure ${\mathcal{G}}_{V}$ with weights $(\eta_{g})_{g\in{\mathcal{G}}_{V}}$ such that $|V|\leq k$, computeFlow$(V,E)$ solves the following optimization problem:

Since ${\mathcal{G}}_{V_{0}}={\mathcal{G}}$, it is sufficient to show that ${\mathcal{H}}(|V_{0}|)$ to prove the proposition.

We initialize the induction by ${\mathcal{H}}(2)$, corresponding to the simplest canonical graph, for which $|V_{gr}|=|V_{u}|=1$). Simple algebra shows that ${\mathcal{H}}(2)$ is indeed correct.

The algorithm then computes a max-flow, using the scalars ${\boldsymbol{\gamma}}_{j}$ as capacities, and we now have two possible situations:

If ${\boldsymbol{\bar{\xi}}}_{j}={\boldsymbol{\gamma}}_{j}$ for all $j$ in $V_{u}$, the algorithm stops; we write ${\mathbf{w}}_{j}={\mathbf{u}}_{j}-{\boldsymbol{\bar{\xi}}}_{j}$ for $j$ in $V_{u}$, and using Eq. (8), we obtain

Since all the quantities in the previous sum are positive, this can only hold if for all $g\in V_{gr}$,

Moreover, by definition of the max flow and the optimality conditions, we have

By Lemma 3, we have shown that the problem (7) is solved.

Let us now consider the case where there exists $j$ in $V_{u}$ such that ${\boldsymbol{\bar{\xi}}}_{j}\neq{\boldsymbol{\gamma}}_{j}$. The algorithm splits the vertex set $V$ into two parts $V^{+}$ and $V^{-}$, which we have proven to be non-empty in the proof of Proposition 1. The next step of the algorithm removes all edges between $V^{+}$ and $V^{-}$ (see Figure 5). Processing $(V^{+},E^{+})$ and $(V^{-},E^{-})$ independently, it updates the value of the flow matrix ${\boldsymbol{\xi}}^{g}_{j},\ j\in V_{u},\ g\in V_{gr}$, and the corresponding flow vector ${\boldsymbol{\bar{\xi}}}_{j},\ j\in V_{u}$. As for $V$, we denote by $V^{+}_{u}\triangleq V^{+}\cap V_{u}$, $V^{-}_{u}\triangleq V^{-}\cap V_{u}$ and $V^{+}_{gr}\triangleq V^{+}\cap V_{gr}$, $V^{-}_{gr}\triangleq V^{-}\cap V_{gr}$.

Then, we notice that $(V^{+},E^{+},s,t)$ and $(V^{-},E^{-},s,t)$ are respective canonical graphs for the group structures ${\mathcal{G}}_{V^{+}}\triangleq\{g\cap V_{u}^{+}\mid g\in V_{gr}\}$, and ${\mathcal{G}}_{V^{-}}\triangleq\{g\cap V_{u}^{-}\mid g\in V_{gr}\}$.

Writing ${\mathbf{w}}_{j}={\mathbf{u}}_{j}-{\boldsymbol{\bar{\xi}}}_{j}$ for $j$ in $V_{u}$, and using the induction hypotheses ${\mathcal{H}}(|V^{+}|)$ and ${\mathcal{H}}(|V^{-}|)$, we now have the following optimality conditions deriving from Lemma 3 applied on Eq. (7) respectively for the graphs $(V^{+},E^{+})$ and $(V^{-},E^{-})$:

We will now combine Eq. (10) and Eq. (11) into optimality conditions for Eq. (7). We first notice that $g\cap V_{u}^{+}=g$ since there are no arcs between $V^{+}$ and $V^{-}$ in $E$ (see the properties of the cuts discussed before this proposition). It is therefore possible to replace $g^{\prime}$ by $g$ in Eq. (10). We will show that it is possible to do the same in Eq. (11), so that combining these two equations yield the optimality conditions of Eq. (7).

More precisely, we will show that for all $g\in V_{gr}^{-}$ and $j\in g\cap V_{u}^{+}$, $|{\mathbf{w}}_{j}|\leq\max_{l\in g\cap V_{u}^{-}}|{\mathbf{w}}_{l}|$, in which case $g^{\prime}$ can be replaced by $g$ in Eq. (11). This result is relatively intuitive: $(s,V^{+})$ and $(V^{-},t)$ being an $(s,t)$-cut, all arcs between $s$ and $V^{-}$ are saturated, while there are unsaturated arcs between $s$ and $V^{+}$; one therefore expects the residuals ${\mathbf{u}}_{j}-{\boldsymbol{\bar{\xi}}}_{j}$ to decrease on the $V^{+}$ side, while increasing on the $V^{-}$ side. The proof is nonetheless a bit technical.

Let us show first that for all $g$ in $V_{gr}^{+}$, $\left\|{\mathbf{w}}_{g}\right\|_{\infty}\leq\max_{j\in V_{u}}|{\mathbf{u}}_{j}-{\boldsymbol{\gamma}}_{j}|$. We split the set $V^{+}$ into disjoint parts:

As previously, we denote $V^{+-}\!\triangleq V_{u}^{+-}\!\cup V_{gr}^{+-}$ and $V^{++}\triangleq\!\!V_{u}^{++}\cup V_{gr}^{++}$. We want to show that $V_{gr}^{+-}$ is necessarily empty. We reason by contradiction and assume that $V_{gr}^{+-}\neq\varnothing$.

According to the definition of the different sets above, we observe that no arcs are going from $V^{++}$ to $V^{+-}$, that is, for all $g$ in $V_{gr}^{++}$, $g\cap V_{u}^{+-}=\varnothing$. We observe as well that the flow from $V_{gr}^{+-}$ to $V_{u}^{++}$ is the null flow, because optimality conditions (10) imply that for a group $g$ only nodes $j\in g$ such that ${\mathbf{w}}_{j}=\|{\mathbf{w}}_{g}\|_{\infty}$ receive some flow, which excludes nodes in $V_{u}^{++}$ provided $V_{gr}^{+-}\neq\varnothing$; Combining this fact and the inequality $\sum_{g\in V_{gr}^{+}}\lambda\eta_{g}\geq\sum_{j\in V_{u}^{+}}{\boldsymbol{\gamma}}_{j}$ (which is a direct consequence of the minimum $(s,t)$-cut), we have as well

Let $j\in V_{u}^{+-}$, if ${\boldsymbol{\bar{\xi}}}_{j}\neq 0$ then for some $g\in V_{gr}^{+-}$ such that $j$ receives some flow from $g$, which from the optimality conditions (10) implies ${\mathbf{w}}_{j}=\|{\mathbf{w}}_{g}\|_{\infty}$; by definition of $V_{gr}^{+-}$, $\|{\mathbf{w}}_{g}\|_{\infty}>{\mathbf{u}}_{j}-{\boldsymbol{\gamma}}_{j}$. But since at the optimum, ${\mathbf{w}}_{j}={\mathbf{u}}_{j}-{\boldsymbol{\bar{\xi}}}_{j}$, this implies that ${\boldsymbol{\bar{\xi}}}_{j}<{\boldsymbol{\gamma}}_{j}$, and in turn that $\sum_{j\in V_{u}^{+-}}{\boldsymbol{\bar{\xi}}}_{j}=\lambda\sum_{g\in V_{gr}^{+-}}\eta_{g}$. Finally,

We now have that for all $g$ in $V_{gr}^{+}$, $\left\|{\mathbf{w}}_{g}\right\|_{\infty}\leq\max_{j\in V_{u}}|{\mathbf{u}}_{j}-{\boldsymbol{\gamma}}_{j}|$. The proof showing that for all $g$ in $V_{gr}^{-}$, $\left\|{\mathbf{w}}_{g}\right\|_{\infty}\geq\max_{j\in V_{u}}|{\mathbf{u}}_{j}-{\boldsymbol{\gamma}}_{j}|,$ uses the same kind of decomposition for $V^{-}$, and follows along similar arguments. We will therefore not detail it.

To recap, we have shown that for all $g\in V_{gr}^{-}$ and $j\in g\cap V_{u}^{+}$, $|{\mathbf{w}}_{j}|\leq\max_{l\in g\cap V_{u}^{-}}|{\mathbf{w}}_{l}|$. Since there is no flow from $V^{-}$ to $V^{+}$, i.e., ${\boldsymbol{\xi}}_{j}^{g}=0$ for $g$ in $V_{gr}^{-}$ and $j$ in $V_{u}^{+}$, we can now replace the definition of $g^{\prime}$ in Eq. (11) by $g^{\prime}\triangleq g\cap V_{u}$, the combination of Eq. (10) and Eq. (11) gives us optimality conditions for Eq. (7).

The proposition being proved for the canonical graph, we extend it now for an equivalent graph in the sense of Lemma 2. First, we observe that the algorithm gives the same values of ${\boldsymbol{\gamma}}$ for two equivalent graphs. Then, it is easy to see that the value ${\boldsymbol{\bar{\xi}}}$ given by the max-flow, and the chosen $(s,t)$-cut is the same, which is enough to conclude that the algorithm performs the same steps for two equivalent graphs.

Similarly to the proximal operator, the computation of dual norm $\Omega^{*}$ can itself shown to solve another network flow problem, based on the following variational formulation, which extends a previous result from :

Proof. By definition of $\Omega^{*}({\boldsymbol{\kappa}})$, we have

with the additional $|{\mathcal{G}}|$ conic constraints $\|{\mathbf{z}}_{g}\|_{\infty}\leq\alpha_{g}$. This primal problem is convex and satisfies Slater’s conditions for generalized conic inequalities, which implies that strong duality holds . We now consider the Lagrangian $\mathcal{L}$ defined as

After simplifying the Lagrangian and flipping the sign of ${\boldsymbol{\xi}}$, the dual problem then reduces to

which is the desired result. We now prove that Algorithm 2 is correct.

Algorithm 2 computes the value of the dual norm of Eq. (12) in a finite and polynomial number of operations.

Proof. The convergence of the algorithm only requires to show that the cardinality of $V$ in the different calls of the function computeFlow strictly decreases. Similar arguments to those used in the proof of Proposition 1 can show that each part of the cuts $(V^{+},V^{-})$ are both non-empty. The algorithm thus requires a finite number of calls to a max-flow algorithm and converges in a finite and polynomial number of operations.

Let us now prove that the algorithm is correct for a canonical graph. We proceed again by induction on the number of nodes of the graph. More precisely, we consider the induction hypothesis ${\mathcal{H}}^{\prime}(k)$ defined as: for all canonical graphs $G=(V,E,s,t)$ associated with a group structure ${\mathcal{G}}_{V}$ and such that $|V|\leq k$, dualNormAux$(V=V_{u}\cup V_{gr},E)$ solves the following optimization problem:

We first initialize the induction by ${\mathcal{H}}(2)$ (i.e., with the simplest canonical graph, such that $|V_{gr}|=|V_{u}|=1$). Simple algebra shows that ${\mathcal{H}}(2)$ is indeed correct.

We next consider a canonical graph $G=(V,E,s,t)$ such that $|V|=k$, and suppose that ${\mathcal{H}}^{\prime}(k-1)$ is true. After the max-flow step, we have two possible cases to discuss:

If ${\boldsymbol{\bar{\xi}}}_{j}={\boldsymbol{\gamma}}_{j}$ for all $j$ in $V_{u}$, the algorithm stops. We know that any scalar $\tau$ such that the constraints of Eq. (13) are all satisfied necessarily verifies $\sum_{g\in V_{gr}}\tau\eta_{g}\geq\sum_{j\in V_{u}}{\boldsymbol{\kappa}}_{j}$. We have indeed that $\sum_{g\in V_{gr}}\tau\eta_{g}$ is the value of an $(s,t)$-cut in the graph, and $\sum_{j\in V_{u}}{\boldsymbol{\kappa}}_{j}$ is the value of the max-flow, and the inequality follows from the max-flow/min-cut theorem . This gives a lower-bound on $\tau$. Since this bound is reached, $\tau$ is necessarily optimal.

We now consider the case where there exists $j$ in $V_{u}$ such that ${\boldsymbol{\bar{\xi}}}_{j}\neq{\boldsymbol{\kappa}}_{j}$, meaning that for the given value of $\tau$, the constraint set of Eq. (13) is not feasible for ${\boldsymbol{\xi}}$, and that the value of $\tau$ should necessarily increase. The algorithm splits the vertex set $V$ into two non-empty parts $V^{+}$ and $V^{-}$ and we remark that there are no arcs going from $V^{+}$ to $V^{-}$, and no flow going from $V^{-}$ to $V^{+}$. Since the arcs going from $s$ to $V^{-}$ are saturated, we have that $\sum_{g\in V_{gr}^{-}}\tau\eta_{g}\leq\sum_{j\in V_{u}^{-}}{\boldsymbol{\kappa}}_{j}$. Let us now consider $\tau^{\star}$ the solution of Eq. (13). Using the induction hypothesis ${\mathcal{H}}^{\prime}(|V^{-}|)$, the algorithm computes a new value $\tau^{\prime}$ that solves Eq. (13) when replacing $V$ by $V^{-}$ and this new value satisfies the following inequality $\sum_{g\in V_{gr}^{-}}\tau^{\prime}\eta_{g}\geq\sum_{j\in V_{u}^{-}}{\boldsymbol{\kappa}}_{j}$. The value of $\tau^{\prime}$ has therefore increased and the updated flow ${\boldsymbol{\xi}}$ now satisfies the constraints of Eq. (13) and therefore $\tau^{\prime}\geq\tau^{\star}$. Since there are no arcs going from $V^{+}$ to $V^{-}$, $\tau^{\star}$ is feasible for Eq. (13) when replacing $V$ by $V^{-}$ and we have that $\tau^{\star}\geq\tau^{\prime}$ and then $\tau^{\prime}=\tau^{\star}$.

To prove that the result holds for any equivalent graph, similar arguments to those used in the proof of Proposition 1 can be exploited, showing that the algorithm computes the same values of $\tau$ and same $(s,t)$-cuts at each step.

Appendix C Algorithm FISTA with duality gap

In this section, we describe in details the algorithm FISTA when applied to solve problem (1), with a duality gap as stopping criterion.

in place of (1). Based on Fenchel duality arguments ,

is a duality gap for (14). where $f^{*}({\boldsymbol{\kappa}})\triangleq\sup_{{\mathbf{z}}}[{\mathbf{z}}^{\top}{\boldsymbol{\kappa}}-f({\mathbf{z}})]$ is the Fenchel conjugate of $f$. Given a primal variable ${\mathbf{w}}$, a good dual candidate ${\boldsymbol{\kappa}}$ can be obtained by looking at the conditions that have to be satisfied by the pair $({\mathbf{w}},{\boldsymbol{\kappa}})$ at optimality . In particular, the dual variable ${\boldsymbol{\kappa}}$ is chosen to be

Consequently, computing the duality gap requires evaluating the dual norm $\Omega^{*}$. We sum up the computation of the duality gap in Algorithm 3.

Appendix D Additional Experimental Results

As shown in , min-cost flow problems, and in particular, the dual problem of (3), can be reduced to a specific parametric max-flow problem. We thus compare our approach (ProxFlow) with the efficient parametric max-flow algorithm proposed by Gallo, Grigoriadis, and Tar- jan and a simplified version of the latter proposed by Babenko and Goldberg in . We refer to these two algorithms as GGT and SIMP respectively. The benchmark is established on the same datasets as those already used in the experimental section of the paper, namely: (1) three datasets built from overcomplete bases of discrete cosine transforms (DCT), with respectively $10^{4},\ 10^{5}$ and $10^{6}$ variables, and (2) images used for the background subtraction task, composed of 57600 pixels. For GGT and SIMP, we use the paraF software which is a C++ parametric max-flow implementation available at http://www.avglab.com/andrew/soft.html. Experiments were conducted on a single-core 2.33 Ghz.

We report in the following table the execution time in seconds of each algorithm, as well as the statistics of the corresponding problems:

Although we provide the speed comparison for a single value of $\lambda$ (the one used in the corresponding experiments of the paper), we observed that our approach consistently outperforms GGT and SIMP for values of $\lambda$ corresponding to different regularization regimes.

References