Technical Report: A Generalized Matching Pursuit Approach for
  Graph-Structured Sparsity
  Sparsity-constrained optimization is an important and challenging problem
that has wide applicability in data mining, machine learning, and statistics.
In this paper, we focus on sparsity-constrained optimization in cases where the
cost function is a general nonlinear function and, in particular, the sparsity
constraint is defined by a graph-structured sparsity model. Existing methods
explore this problem in the context of sparse estimation in linear models. To
the best of our knowledge, this is the first work to present an efficient
approximation algorithm, namely, Graph-structured Matching Pursuit (Graph-Mp),
to optimize a general nonlinear function subject to graph-structured
constraints. We prove that our algorithm enjoys the strong guarantees analogous
to those designed for linear models in terms of convergence rate and
approximation accuracy. As a case study, we specialize Graph-Mp to optimize a
number of well-known graph scan statistic models for the connected subgraph
detection task, and empirical evidence demonstrates that our general algorithm
performs superior over state-of-the-art methods that are designed specifically
for the task of connected subgraph detection.
