text: We study an extention of total variation denoising over images to over Cartesian power graphs and its applications to estimating non-parametric network models. The power graph fused lasso (PGFL) segments a matrix by exploiting a known graphical structure, @math , over the rows and columns. Our main results shows that for any connected graph, under subGaussian noise, the PGFL achieves the same mean-square error rate as 2D total variation denoising for signals of bounded variation. We study the use of the PGFL for denoising an observed network @math , where we learn the graph @math as the @math -nearest neighborhood graph of an estimated metric over the vertices. We provide theoretical and empirical results for estimating graphons, a non-parametric exchangeable network model, and compare to the state of the art graphon estimation methods.
  @cite_22: 
  @cite_7: We consider the problem @math , and propose algorithms of the form @math , where @math denotes projection on the positive orthant, @math is a stepsize chosen by an Armijo-like rule and @math is a positive definite symmetric matrix which is partly diagonal. We show that @math can be calculated simply on the basis of second derivatives of f so that the resulting Newton-like algorithm has a typically superlinear rate of convergence. With other choices of @math convergence at a typically linear rate is obtained. The algorithms are almost as simple as their unconstrained counterparts. They are well suited for problems of large dimension such as those arising in optimal control while being competitive with existing methods for low-dimensional problems. The effectiveness of the Newton-like algorithm is demonstrated via computational examples involving as many as 10,000 variables. Extensions to general linearly constrained pr...
  @cite_9: 
  @cite_2: The Lasso is a very well-known penalized regression model, which adds an L1 penalty with parameter λ1 on the coefficients to the squared error loss function. The Fused Lasso extends this model by also putting an L1 penalty with parameter λ2 on the difference of neighboring coefficients, assuming there is a natural ordering. In this article, we develop a path algorithm for solving the Fused Lasso Signal Approximator that computes the solutions for all values of λ1 and λ2. We also present an approximate algorithm that has considerable speed advantages for a moderate trade-off in accuracy. In the Online Supplement for this article, we provide proofs and further details for the methods developed in the article.
  @cite_31: Problem Setup a graph G with vertices V = v1, . . . , vN an edge weight matrix W a data vector f ∈ R, where fi corresponds to vi Notation & Recursive Partitioning A preliminary step for the GHWT is to use recursive bisection to generate a recursive partitioning of the graph (see [1] for an example). Our notation is: j ∈ [0, jmax] denotes levels, where j = 0 is the coarsest level (the only region is the entire graph) and j = jmax is the finest level (each region is a single node) k ∈ [0,K ) indexes the regions on level j In addition, we let N j k denote the number of nodes in region k on level j If N j k > 1 then we let k ′ and k ′ + 1 denote the indices of the children regions on level j + 1 Basis Vector & Coefficient Notation GHWT basis vectors and coefficients are written as ψ k, and d j k, , respectively, where j and k correspond to level and region and is the tag. = 0 ⇒ scaling coefficient basis vector = 1 ⇒ Haar-like coefficient basis vector ≥ 2 ⇒ Walsh-like coefficient basis vector
  @cite_11: In this paper we study a first-order primal-dual algorithm for non-smooth convex optimization problems with known saddle-point structure. We prove convergence to a saddle-point with rate O(1 N) in finite dimensions for the complete class of problems. We further show accelerations of the proposed algorithm to yield improved rates on problems with some degree of smoothness. In particular we show that we can achieve O(1 N 2) convergence on problems, where the primal or the dual objective is uniformly convex, and we can show linear convergence, i.e. O(? N ) for some ??(0,1), on smooth problems. The wide applicability of the proposed algorithm is demonstrated on several imaging problems such as image denoising, image deconvolution, image inpainting, motion estimation and multi-label image segmentation.
summary: There is an extensive body of literature on solving the fused lasso, . Algorithms for solving the fused lasso can be divided into two categories: solvers for a fixed @math , and path algorithms that find the solution for every @math within a range. The fused lasso for a fixed @math has a quadratic program dual form, and some popular algorithms for this are the projected Newton algorithm of @cite_7 @cite_22 , first-order primal-dual algorithm @cite_11 , and split-Bregman iteration @cite_9 . Some path algorithms include the generalized lasso path algorithm of @cite_31 , and a max-flow version for the fused lasso in @cite_2 . If applied directly to C2-power graphs, these methods would have computational and memory complexity that scale with the number of dyads, @math .