(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
The definition scheme, "A poset P is Z-inductive if it has a subposet B of Z-compact lements such that for every element of p of P there is a Z-set S in B such that p = {big square union}S, becomes meaningful when we replace the symbol of Z by such adjectives as "sirected", "chain", "pairwise compatible", "singleton", etc. Furthermore, several theorems have been proved that seem to differ only in their instantiations of Z. A simialr phenomena occurs when we comsider concepts such as Z-completeness of Z-comtinuity. This suggests that in all these different cases we are really talking about Z same thing. In this paper we show that this is indeed the case by abstracting out the essential common properties of the different instantiations of Z and proving common theorems within the resulting abstract framework. © 1978.
Eric Price, David P. Woodruff
FOCS 2011
David A. Selby
IBM J. Res. Dev
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Ohad Shamir, Sivan Sabato, et al.
Theoretical Computer Science