Embedding high-dimensional data sets into subspaces of much lower dimension is important for reducing storage cost and speeding up computation in several applications, including numerical linear algebra, manifold learning, and computer science. The relatively new field of compressed sensing is based on the observation that if the high-dimensional data are sparse in a known basis, they can be embedded into a lower-dimensional space in a manner that permits their efficient recovery through l1-minimization. We first give a brief overview of compressed sensing, and discuss how certain statistical procedures like cross validation can be naturally incorporated into this set-up. The latter part of the talk will focus on a "near equivalence" of two fundamental concepts in compressed sensing: the Restricted Isometry Property and the Johnson-Lindenstrauss Lemma; as a consequence of this result, we improve on the best-known bounds for dimensionality reduction using structured, or "fast" linear embeddings. Finally, we discuss the Restricted Isometry Property for structured measurement matrices formed by subsampling orthonormal polynomial systems, and implications for approximating of high-dimensional functions from a few samples.Scales in images and on curves and surfaces