About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
JMLR
Paper
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 suitable 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. We present an efficient combinatorial algorithm for provable sparse recovery under similar assumptions on KB-RIP. This result improves the previously known 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. Copyright 2011 by the authors.