Block-Sparse Solutions Using Kernel Block RIP and Its Application to Group Lasso

Abstract

We propose Kernel Block Restricted Isometry Property (KB-RIP) as a generalization of the well-studied RIP and prove a variety of results. First, we present a “sum-of-norms”-minimization based formulation of the sparse recovery problem and prove that under certain conditions on KB-RIP, it recovers the optimal sparse solution exactly. The Group Lasso formulation, widely used as a good heuristic, arises naturally from the Lagrangian relaxation of our formulation. Second, we present an efficient combinatorial algorithm for provable sparse recovery under similar assumptions on KB-RIP. As a side product, this result improves the previous best assumptions on RIP under which a combinatorial algorithm was known. Finally, we provide numerical evidence to illustrate that not only are our sum-of-norms-minimization formulation and combinatorial algorithm significantly faster than Lasso, they also outperforms Lasso in terms of recovery.