(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
Let S be a subdivision of Rd into n convex regions. We consider the combinatorial complexity of the image of the (k - 1)-skeleton of S orthogonally projected into a k-dimensional subspace. We give an upper bound of the complexity of the projected image by reducing it to the complexity of an arrangement of polytopes. If k = d - 1, we construct a subdivision whose projected image has Ω(n⌊(3d-2)/2⌋) complexity, which is tight when d ≤ 4. We also investigate the number of topological changes of the projected image when a three-dimensional subdivision is rotated about a line parallel to the projection plane. © 1994.
Eric Price, David P. Woodruff
FOCS 2011
Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
Gal Badishi, Idit Keidar, et al.
IEEE TDSC
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006