Block-sparse Solutions using Kernel Block RIP and its Application to Group Lasso


Rahul Garg, Rohit Khandekar ;
Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, PMLR 15:296-304, 2011.


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. [pdf][supplementary]

Related Material