----------------- Version 4 changes: ----------------- -- Version published in GAFA. Many typos fixed. (8/25/2015) ----------------- Version 3 changes: ----------------- -- Added a new co-author (Sjoerd Dirksen). (12/22/2014) -- Generally polished things throughout the paper. (12/22/2014) -- Put failure probability information in Section 4. This could be done throughout the paper, but we didn't since after seeing how it's done in Section 4, one will see the steps; there are no further conceptual hurdles. (12/22/2014) -- Added Section 3 (proof overview). (12/22/2014) -- Fixed a cell in Figure 1 for "previous m" for collection of subspaces. Previous work achieved d*log^6, not d+log^6. (12/22/2014) -- Added some appendices to give background on topics that might be unfamiliar to a TCS audience. (12/22/2014) -- Added Section 6 on sketching constrained least squares with the SJLT. (12/22/2014) -- In Version 2 the sentence fragment "We assume henceforth $k \le m/s$ since otherwise the integral above is $O(\sqrt{\log n})$" above (6.14) is erroneous. This is replaced by something that actually makes sense in Version 3 (namely (7.15)). (12/22/2014) ----------------- Version 2 changes: ----------------- -- Added more applications, to finite collections of (incoherent) subspaces, with applications to model-based compressed sensing, as well as to infinite collections of subspaces and smooth manifolds, with applications to manifold learning. (4/2/2014)