Graph-Structured Sparse Regularization Via Convex Optimization

Abstract

In this paper, we present a novel convex method for the graph-structured sparse recovery. While various structured sparsities can be represented as the graph-structured sparsity, graph- structured sparse recovery remains to be a challenging non-convex problem. To solve this difficulty, we propose a convex penalty function which automatically identifies the relevant subgraph of an underlying graph. We design a graph-structured recovery model using the proposed penalty, and develop its first-order iterative solver which consists only of simple operations such as closed-form proximity operators and difference operator on the graph. Numerical experiments show that the proposed method has better estimation accuracy than the existing convex regularizations using fixed structures.