A Generalized Matching Pursuit Approach for Graph-Structured Sparsity

1 Introduction

In recent years, that is a growing demand on efficient computational methods for analyzing high-dimensional data in a variety of applications such as bioinformatics, medical imaging, social networks, and astronomy. In many settings, sparsity has been shown effective to model latent structure in high-dimensional data and at the same time remain a mathematically tractable concept. Beyond the ordinary, extensively studied, sparsity model, a variety of structured sparsity models have been proposed in the literature, such as the sparsity models defined through trees [Hegde et al., 2014b], groups [Jacob et al., 2009], clusters [Huang et al., 2011], paths [Asteris et al., 2015], and connected subgraphs [Hegde et al., 2015b]. These sparsity models are designed to capture the interdependence of the locations of the non-zero components via prior knowledge, and are considered in the general sparsity-constrained optimization problem:

where f : Rn ! R is a differentiable cost function and the sparsity model M is defined as a family of structured supports: M = ¶S1↪ S2↪ · · · ↪ SL♦, where Si ✓ [n] satisfies a certain structure property (e.g., trees, groups, clusters). The original k-sparse recovery problem corresponds to the particular case where the model M = ¶S ✓ [n] ♣ ♣S♣  k♦.

The methods that focus on general nonlinear cost functions fall into two major categories, including structured sparsityinducing norms based and model-projection based, both of which often assume that the cost function f(x) satisfies a certain convexity/smoothness condition, such as Restricted Strong Convexity/Smoothness (RSC/RSS) or Stable ModeRestricted Hessian (SMRH). In particular, the methods in the first category replace the structured sparsity model with regularizations by a sparsity-inducing norm that is typically nonsmooth and non-Euclidean [Bach et al., 2012]. The methods in the second category decompose Problem (1) into an unconstrained subproblem and a model projection oracle that finds the best approximation of an arbitrary x in the model M:

A number of methods are proposed specifically for the ksparsity model M = ¶S ✓ [n] ♣ ♣S♣  k♦, including the forward-backward algorithm [Zhang, 2009], the gradient descent algorithm [Tewari et al., 2011], the gradient hardthresholding algorithms [Yuan et al., 2013; Bahmani et al., 2013; Jain et al., 2014], and the Newton greedy pursuit algorithm [Yuan and Liu, 2014]. A limited number of methods are proposed for other types of structured sparsity models via projected gradient descent, such as the union of subspaces [Blumensath, 2013] and the union of nested subsets [Bahmani et al., 2016].

In this paper, we focus on general nonlinear optimization subject to graph-structured sparsity constraints. Our approach applies to data with an underlying graph structure in which nodes corresponding to supp(x) form a small number of connected components. By a proper choice of the underlying graph, several other structured sparsity models such as the "standard" k-sparsity, block sparsity, cluster sparsity, and tree sparsity can be encoded as special cases of graph-structured sparsity [Hegde et al., 2015a].

We have two key observations: 1) Sparsity-inducing norms. There is no known sparsity-inducing norm that is able to capture graph-structured sparsity. The most relevant norm is generalized fused lasso [Xin et al., 2014] that enforces the smoothness between neighboring entries in x, but does not have fine-grained control over the number of connected components. Hence, existing methods based on sparsity-inducing norms are not directly applicable to the problem to be optimized. 2) Model projection oracle. There is no exact model projection oracle for a graph-structured sparsity model, as this exact projection problem is NP-hard due to a reduction from the classical Steiner tree problem [Hegde et al., 2015b]. As most existing model-projection based methods assume an exact model projection oracle, they are not directly applicable here as well. To the best of our knowledge, there is only one recent approach that admits inexact projections for a graphstructured sparsity model by assuming "head" and "tail" approximations for the projections, but is only applicable to linear regression problems [Hegde et al., 2015b]. This paper will generalize this approach to optimize general nonlinear functions. The main contributions of our study are summarized as follows:

• ÷ Design of an efficient approximation algorithm. A new and efficient algorithm, namely, GRAPH-MP, is developed to approximately solve Problem (1) with a differentiable cost function and a graph-structured sparsity model. We show that GRAPH-MP reduces to a state-ofthe-art algorithm for graph-structured compressive sensing and linear models, namely, GRAPH-COSAMP, when f(x) is a least square loss function.
• ÷ Theoretical analysis and connections to existing methods. The convergence rate and accuracy of the proposed GRAPH-MP are analyzed under a condition of f(x) that is weaker than popular conditions such as RSC/RSS and SMRH. We demonstrate that GRAPH-MP enjoy strong guarantees analogous to GRAPH-COSAMP on both convergence rate and accuracy.
• ÷ Compressive experiments to validate the effectiveness and efficiency of the proposed techniques. The proposed GRAPH-MP is applied to optimize a variety of graph scan statistic models for the task of connected subgraph detection. Extensive experiments demonstrate that GRAPH-MP performs superior over state-of-the-art methods that are customized for the task of connected subgraph detection on both running time and accuracy.

The rest of this paper is organized as follows. Section 2 introduces the graph-structured sparsity model. Section 3 formalizes the problem and presents an efficient algorithm GRAPH-MP. Sections 4 and 5 present theoretical analysis and applications of GRAPH-MP. Experiments are presented in Section 6, and Section 7 describes future work. An extended version of this paper is available from [Chen, 2016].

2 Graph-Structured SparsityModel

Given an underlying graph G = (V↪ E) defined on the coefficients of the unknown vector x, where V = [n] and E ✓ V ⇥ V, a graph-structured sparsity model has the form:

where k refers to an upper bound of the sparsity (total number of nodes) of S and γ(S) = g refers to the maximum number of connected components formed by the forest induced by S: GS = (S↪ ES), where ES = ¶(i↪ j) ♣ i↪ j 2 S↪ (i↪ j) 2 E♦. The corresponding model projection oracle is defined as

Solving Problem (3) exactly is NP-hard due to a reduction from the classical Steiner tree problem. Instead of solving (3) exactly, two nearly-linear time approximation algorithms with the following complementary approximation guarantees are proposed in [Hegde et al., 2015b]:

• ÷ Tail approximation (T(x)): Find S 2 M(kT ↪ g) such that

• ÷ Head approximation (H(x)): Find S 2 M(kH↪ g) such that kxSk2 ≥ cH · max S02M(k↪g) kxS0 k2↪ (5) where cH = p1◁14 and kH = 2k.

If cT = cH = 1, then T(x) = H(x) = S provides the exact solution of the model projection oracle: P(x) = xS, which indicates that the approximations stem from the fact that cT > 1 and cH < 1. We note that these two approximations originally involve additional budgets (B) based on edge weights, which are ignored in this paper by setting unit edge weights and B = k - g.

Generalization: The above graph-structured sparsity model is defined based on the number of connected components in the forest induced by S. This model can be generalized to graph-structured sparsity models that are defined based on other graph topology constraints, such as density, k-core, radius, cut, and various others, as long as their corresponding head and tail approximations are available [Chen, 2016].

3 Problem Statement and Algorithm

Given the graph-structured sparsity model, M(k↪ g), as defined above, the sparsity-constrained optimization problem to be studied is formulated as:

where f : Rn ! R is a differentiable cost function, and the upper bound of sparsity k and the maximum number of connected components g are predefined by users.

Hegde et al. propose GRAPH-COSAMP, a variant of COSAMP [Hegde et al., 2015b] to optimize the least square cost function f(x) = ky - Axk22 based on the head and tail approximations. The authors show that GRAPH-COSAMP achieves an information-theoretically optimal sample complexity for a wide range of parameters. In this paper, we genearlize GRAPH-COSAMP and propose a new algorighm named as GRAPH-MP for Problem (6), as shown in Algorithm 1. The first step (Line 3) in each iteration, g = rf(xi ), evaluates the gradient of the cost function at the current estimate. Then a subset of nodes are identified via head approximation, Γ = H(g), that returns a support set with head value at least a constant fraction of the optimal head value, in which pursuing the minimization will be most effective. This subset is then merged with the support of the current estimate to obtain the merged subset ⌦, over which the function f is minimized to produce an intermediate estimate, b = argminx2Rn f(x) s▷t▷ x⌦c = 0. Then a subset of nodes are identified via tail approximation, B = T(b), that returns a support set with tail value at most a constant times larger than the optimal tail value. The iterations terminate when the halting condition holds. There are two popular options to define the halting condition: 1) the change of the cost function from the previous iteration is less than a threshold (♣f(xi+1 ) - f(xi )♣  ✏); and 2) the change of the estimated minimum from the previous iteration is less than a threshold (kxi+1 - xi k2  ✏), where ✏ is a predefined threshold (e.g., ✏ = 0▷001).

Algorithm 1 GRAPH-MP

• 1: i = 0, xi = 0;
• 2: repeat
• 3: g =rf(xi );
• 5: ⌦ = Γ[ supp(xi )
• 4: Γ = H(rf(gi ));
• 6: b = argminx2Rn f(x) s▷t▷ x⌦c = 0
• 7: B = T(b);
• 8: xi+1 = bB
• 9: until halting condition holds
• 10: return xi+1

4 Theoretical Analysis of GRAPH-MP

In order to demonstrate the accuracy of estimates using Algorithm 1 we require a variant of the Restricted Strong Convexity/Smoothness (RSC/RSS) conditions proposed in [Yuan et al., 2013] to hold. The RSC condition basically characterizes cost functions that have quadratic bounds on the derivative of the objective function when restricted to model-sparse vectors. The condition we rely on, the Weak Restricted Strong Convexity (WRSC), can be formally defined as follows:

Definition 1 (Weak Restricted Strong Convexity Property (WRSC)). A function f(x) has condition (⇠, δ, M)-WRSC if 8x↪ y 2 Rn and 8S 2 M with supp(x) [ supp(y) ✓ S, the following inequality holds for some ⇠ > 0 and 0 < δ < 1:

Remark 1. 1) In the special case where f(x) = ky -Axk22 and ⇠ = 1, condition (⇠, δ, M)-WRSC reduces to the well known Restricted Isometry Property (RIP) condition in compressive sensing. 2) The RSC and RSS conditions imply condition WRSC, which indicates that condition WRSC is no stronger than the RSC and RSS conditions [Yuan et al., 2013].

Theorem 4.1. Consider the graph-structured sparsity model M(k↪ g) for some k↪ g 2 N and a cost function f : Rn ! R that satisfies condition (⇠↪ δ↪ M(8k↪ g))-WRSC. If ⌘ = cH(1δ)-δ > 0, then for any true x 2 Rn with supp(x) 2 M(k↪ g), the iterates of Algorithm 1 obey

Proof. A proof of this result can be found in Appendix.

As indicated in Theorem 4.1, under proper conditions the estimator error of GRAPH-MP is determined by the multiplier of krSf(x)k2, and the convergence rate before reaching this error level is geometric. In particular, if the true x is sufficiently close to an unconstrained minimum of f, then the estimation error is negligible because krSf(x)k2 has a small magnitude. Especially, in the ideal case where rf(x) = 0, it is guaranteed that we can obtain the true x to arbitrary precision. If we further assume that ↵ = (1+cT )p1-⌘2 p1-δ < 1, then exact recovery can be achieved in finite iterations.

The shrinkage rate ↵ < 1 controls the convergence of GRAPH-MP, and it implies that when δ is very small, the approximation factors cH and cT satisfy

We note that the head and tail approximation algorithms designed in [Hegde et al., 2015b] do not satisfy the above condition, with cT = p7 and cH = p1◁14. However, as proved in [Hegde et al., 2015b], the approximation factor cH of any given head approximation algorithm can be boosted to any arbitrary constant c0H < 1, such that the above condition is satisfied. Empirically it is not necessary to boost the headapproximation algorithm as strongly as suggested by the analysis in [Hegde et al., 2014a].

Theorem 4.2. Let x 2 Rn be a true optimum such that supp(x) 2 M(k↪ g), and f : Rn ! R be a cost function that satisfies condition (⇠↪ δ↪M(8k↪ g))-WRSC. Assuming that ↵ < 1, GRAPH-MP returns a ˆx such that, supp(ˆx) 2 M(5k↪ g) and kx-ˆxk2  ckrIf(x)k2, where c = (1+ β 1-↵ ) is a fixed constant. Moreover, GRAPH-MP runs in time

where T is the time complexity of one execution of the subproblem in Line 6. In particular, if T scales linearly with n, then GRAPH-MP scales nearly linearly with n.

Proof. The i-th iterate of Algorithm 1 satisfies

After t = llog ⇣ kxk2 krIf(x)k2 ⌘ ◁ log 1↵ m iterations, Algorithm 1 returns an estimate ˆx satisfying kx - ˆxk2  (1 + β 1-↵ )krIf(x)k2▷ The time complexities of both head and tail approximations are O(♣E♣ log3 n). The time complexity of one iteration in Algorithm 1 is (T + ♣E♣ log3 n), and the total number of iterations is llog ⇣ kxk2 krIf(x)k2 ⌘ ◁ log 1↵ m, and the overall time complexity follows.

Remark 2. The previous algorithm GRAPHCOSAMP [Hegde et al., 2015b] for compressive sensing is a special case of GRAPH-MP. Assume f(x) = ky -Axk22 .

1) Reduction. The gradient in Step 3 of GRAPH-MP has the form: rf(xi ) = -AT (y - Axi ), and an analytical form of b in Step 6 can be obtained as: b⌦ = A+⌦ y and b⌦c = 0, where A+ = AT (AT A)-1 , which indicates that GRAPH-MP reduces to GRAPH-COSAMP in this scenario. 2) Shrinkage rate. The shrinkage rate ↵ of GRAPH-MP is analogous to that of GRAPH-COSAMP, even though that the shrinkage rate of GRAPH-COSAMP is optimized based on the RIP sufficient constants. In particular, they are identical when δ is very small. 3) Constant component. Assume that ⇠ = 1. Condition (⇠↪ δ↪M(k↪ g))-WRSC then reduces to the RIP condition in compressive sensing. Let e = y - Ax. The component krf(xi )k2 = kAT ek2 is upper bounded by p1+ δkek2 [Hegde et al., 2014a]. The constant βkrIf(x)k is then upper bounded by ⇠(1+cT )p1+δ 1-δ  (1+cH ) ⌘ + ⌘(1+cH) p1-⌘2 +1] kek2 that is analogous to the constant of GRAPH-COSAMP, and they are identical when δ is very small.

5 Application in Graph Scan Statistic Models

In this section, we specialize GRAPH-MP to optimize a number of graph scan statistic models for the task of connected subgraph detection. Given a graph G = (V↪ E), where V = [n], E ✓ V⇥V, and each node v is associated with a vector of features c(v) 2 Rp . Let S ✓ V be a connected subset of nodes. A graph scan statistic, F(S) = log Prob(Data♣H1(S)) Prob(Data♣H0) , corresponds to the generalized likelihood ratio test (GLRT) to verify the null hypothesis (H0): c(v) ⇠ D1↪ 8v 2 V, where D1 refers to a predefined background distribution, against the alternative hypothesis (H1(S)): c(v) ⇠ D2↪ 8v 2 S and c(v) ⇠ D1↪ 8v 2 V ∩ S, where D2 refers to a predefined signal distribution. The detection problem is formulated as

where k is a predefined bound on the size of S.

Taking elevated mean scan (EMS) statistic for instance, it aims to decide between H0 : c(v) ⇠ N(0↪ 1)↪ 8v 2 V and H1(S): c(v) ⇠ N(θ↪ 1)↪ 8v 2 S and c(v) ⇠ N(0↪ 1)↪ 8v 2 V ∩ S, where for simplicity each node v only has a univariate feature c(v) 2 R. This statistic is popularly used for detecting signals among node-level numerical features on graph [Qian et al., 2014; Arias-Castro et al., 2011] and is formulated as F(S) = (Pv2S c(v))2 ◁♣S♣. Let the vector form of S be x 2 ¶0↪ 1♦n , such that supp(x) = S. The connected subgraph detection problem can be reformulated as

where c = [c(1)↪ · · · ↪ c(n)]T . To apply GRAPH-MP, we relax the input domain of x such that x 2 [0↪ 1]n , and the connected subset of nodes can be found as S = supp(x? ), the support set of the estimate x? that minimizes the strongly convex function [Bach, 2011]:

Assume that c is normalized, and hence 0  ci < 1↪ 8i. Let ˆ c = max¶ci♦. The Hessian matrix of the above objective function r2 f(x) ≻ 0 and satisfies the inequalities:

According to Lemma 1 (b) in [Yuan et al., 2013]), the objective function f(x) satisfies condition (⇠↪ δ↪M(8k↪ g))-WRSC that δ = p1-2⇠(1- ˆ c2 ) + ⇠ 2 ↪ for any ⇠ such that ⇠ < 2(1 - ˆ c2 ). Hence, the geometric convergence of GRAPH-MP as shown in Theorem 4.1 is guaranteed. We note that not all the graph scan statistic functions satisfy the WRSC condition, but, as shown in our experiments, GRAPH-MP works empirically well for all the scan statistic functions tested, and the maximum number of iterations to convergence for optimizing each of these scan statistic functions was less than 10.

We note that our proposed method GRAPH-MP is also applicable to general sparse learning problems (e.g. sparse logistic regression, sparse principle component analysis) subject to graph-structured constraints, and to a variety of subgraph detection problems, such as the detection of anomalous subgraphs, bursty subgraphs, heaviest subgraphs, frequent subgraphs or communication motifs, predictive subgraphs, and compression subgraphs. More details can be found at [Chen, 2016].

6 Experiments

This section evaluates the effectiveness and efficiency of the proposed GRAPH-MP approach for connected subgraph detection. The implementation of GRAPH-MP is available at https://github.com/baojianzhou/Graph-MP.

6.1 Experiment Design

Datasets: 1) Water Pollution Dataset. The Battle of the Water Sensor Networks (BWSN) [Ostfeld et al., 2008] provides a real-world network of 12,527 nodes and 14831 edges, and 4 nodes with chemical contaminant plumes that are distributed in four different areas. The spreads of contaminant plumes were simulated using the water network simulator EPANET for 8 hours. For each hour, each node has a sensor that reports 1 if it is polluted; 0, otherwise. We randomly selected K percent nodes, and flipped their sensor binary values in order to test the robustness of methods to noises, where K 2 ¶2↪ 4↪ 6↪ 8↪ 10♦. The objective is to detect the set of polluted nodes. 2) High-Energy Physics Citation Network. The CitHepPh (high energy physics phenomenology) citation graph is from the e-print arXiv and covers all the citations within a dataset of 34,546 papers with 421,578 edges during the period from January 1993 to April 2002. Each paper is considered as a node, each citation is considered as a edge (direction is not considered), and each node has one attribute denoting the number of citations in a specific year (t = 1993↪ · · · ↪ t = 2002), and another attribute denoting the average number of citations in that year. The objective is to detect a connected subgraph of nodes (papers) whose citations are abnormally high in comparison with the citations of nodes outside the subgraph. This subgraph is considered an indicator of a potential emerging research area. The data before 1999 is considered as training data, and the data from 1999 to 2002 is considered as testing data.

Graph Scan Statistics: Three graph scan statistics were considered, including Kulldorff's scan statistic [Neill, 2012], expectation-based Poisson scan statistic (EBP) [Neill, 2012], and elevated mean scan statistic (EMS, Equation (13)) [Qian et al., 2014]. The first two require that each node has an observed count of events at that node, and an expected count. For the water network dataset, the report of the sensor (0 or 1) at each node is considered as the observed count, and the noise ratio is considered as the expected count. For the CiteHepPh dataset, the number of citations is considered as the observed count, and the average number of citations is considered as the expected count. For the EMS statistic, we consider the ratio of observed and expected counts as the feature.

Comparison Methods: Seven state-of-the-art baseline methods are considered, including EdgeLasso [Sharpnack et al., 2012b], GraphLaplacian [Sharpnack et al., 2012a], LinearTimeSubsetScan (LTSS) [Neill, 2012], EventTree [Rozenshtein et al., 2014], AdditiveGraphScan [Speakman et al., 2013], DepthFirstGraphScan [Speakman et al., 2016], and NPHGS [Chen and Neill, 2014]. We followed strategies recommended by authors in their original papers to tune the related model parameters. Specifically, for EventTree and Graph-Laplacian, we tested the set of λ values: ¶0▷02↪ 0▷04↪ · · · ↪ 2▷0♦. DepthFirstScan is an exact search algorithm and has an exponential time cost in the worst case scenario. We hence set a constraint on the depth of its search to 10 in order to reduce its time complexity.

We also implemented the generalized fused lasso model (GenFusedLasso) for these three graph scan statistics using the framework of alternating direction method of multipliers (ADMM). GenFusedLasso is formalized as

where f(x) is a predefined graph scan statistic and the tradeoff parameter λ controls the degree of smoothness of neighboring entries in x. We applied the heuristic rounding step proposed in [Qian et al., 2014] to the numerical vector x to identify the connected subgraph. We tested the λ values: ¶0▷02↪ 0▷04↪ · · · ↪ 2▷0↪ 5▷0↪ 10▷0♦ and returned the best result.

Performance Metrics: The overall scores of the three graph scan statistics of the connected subgraphs returned by the competitive methods were compared and analyzed. The objective is to identify methods that could find the connected subgraphs with the largest scores. The running times of different methods are compared.

Our Proposed Method GRAPH-MP: Our proposed GRAPH-MP has a single parameter k, an upper bound of the subgraph size. We set k = 1000 by default, as the sizes of subgraphs of interest are often small; otherwise, the detection problem could be less challenging. We note that, to obtain the best performance of our proposed method GRAPH-MP, we should try a set of different k values (k = 50↪ 100↪ 200↪ 300↪ · · · ↪ 1000) and return the best.

6.2 Evolving Curves of Graph Scan Statistics

Figure 1 presents the comparison between our method and GenFusedLasso on the scores of the best connected subgraphs that are identified at different iterations based on the Kulldorff's scan statistic and the EMS statistic. Note that, a heuristic rounding process as proposed in [Qian et al., 2014] was applied to the numerical vector xi estimated by GenFusedLasso in order to identify the best connected subgraph at each iteration i. As the setting of the parameter λ

will influence the quality of the detected connected subgraph, the results based on different λ values are also shown in Figure 1. We observe that our proposed method GRAPH-MP converged in less than 5 steps and the qualities (scan statistic scores) of the connected subgraphs identified GRAPH-MP at different iterations were consistently higher than those returned by GenFusedLasso.

6.3 Comparison on Optimization Quality

The comparison between our method and the other eight baseline methods is shown in Table 1. The scores of the three graph scan statistics of the connected subgraphs returned by these methods are reported in this table. The results in indicate that our method outperformed all the baseline methods on the scores, except that AdditiveGraphScan achieved the highest EMS score (761.08) on the water network data set. Although AdditiveGraphScan performed reasonably well in overall, this algorithm is a heuristic algorithm and does not have theoretical guarantees.

6.4 Comparison on Time Cost

Table 1 shows the time costs of all competitive methods on the two benchmark data sets. The results indicate that our method was the second fastest algorithm over all the comparison methods. In particular, the running times of our method were 10+ times faster than the majority of the methods.

7 Conclusion and FutureWork

This paper presents, GRAPH-MP, an efficient algorithm to minimize a general nonlinear function subject to graphstructured sparsity constraints. For the future work, we plan to explore graph-structured constraints other than connected subgraphs, and analyze theoretical properties of GRAPH-MP for cost functions that do not satisfy the WRSC condition.

A Proof of Theorem 4.1

Proof. Let ri+1 = xi+1 -x. kri+1 k2 is upper bounded as

which follows from the definition of tail approximation. The component k(x-b)⌦k22 is upper bounded as

where the second equality follows from the fact that r⌦f(b) = 0 since b is the solution to the problem in Step 6 of Algorithm 1, and the last inequality follows from condition (⇠↪ δ↪ M(8k↪ g))-WRSC. After simplification, we have

It follows that

After rearrangement we obtain

where the first equality follows from the fact that supp(b) ✓ ⌦, the second and last inequalities follow from the fact that ⌦ = Γ [ supp(xi ). Combining above inequalities, we obtain

From Lemma A.2, we have

Combining the above inequalities, we prove the theorem.

Lemma A.1. [Yuan et al., 2013] Assume that f is a differentiable function. If f satisfies condition (⇠↪ δ↪M)-WRSC, then 8x↪ y 2 Rn with supp(x) [ supp(y) ⇢ S 2 M, the following two inequalities hold

Lemma A.2. Let ri = xi - x and Γ = H(rf(xi )). Then

where ⌘ = cH(1-δ)-δ and I = argmaxS2M(8k↪g) krSf(x)k2▷ We assume that cH and δ are such that ⌘ > 0.

Proof. Denote Φ = supp(x) 2 M(k↪ g)↪ Γ = H(rf(xi ) 2 M(2k↪ g), ri = xi - x, and ⌦ = supp(ri ) 2 M(6k↪ g). The component krΓf(xi )k2 can be lower bounded as

where the last inequality follows from Lemma A.1. The component krΓf(xi )k2 can also be upper bounded as

where the last inequality follows from condition (⇠↪ δ↪M(8k↪ g))-WRSC and the fact that riΓ[⌦ = ri . Let ⌘ = (cH · (1 - δ) - δ). Combining the two bounds and grouping terms, we have kriΓk ≥ ⌘kri k2-⇠(1+cH)krI f (x)k2. After a number of algebraic manipulations similar to those used in [Hegde et al., 2014a] Page 11, we prove the lemma. Readers are referred to [Chen, 2016] for more details of the proof.

B Acknowledgements

This work is supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center (DoI/NBC) contract D12PC00337. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the US government.