Harsha Kokel, Aamod Khatiwada, et al.
VLDB 2025
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.
Harsha Kokel, Aamod Khatiwada, et al.
VLDB 2025
Yale Song, Zhen Wen, et al.
IJCAI 2013
Joxan Jaffar
Journal of the ACM
Daniel Karl I. Weidele, Hendrik Strobelt, et al.
SysML 2019