Showing cs.DSShow all
2 papers · 1 filter
cs.DS2011
Lower Bounds for Sparse Recovery
Khanh Do Ba, Piotr Indyk, Eric Price +1
We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-…
cs.DS2010★ 2 cited
Steiner Transitive-Closure Spanners of d-Dimensional Posets
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu +3
Given a directed graph G and an integer k >= 1, a k-transitive-closure-spanner (k-TCspanner) of G is a directed graph H that has (1) the same transitive-closure as G and (2) diamet…