A novel approach is developed for nonlinear compression and reconstruction of high-or even infinite-dimensional signals living on a smooth but otherwise unknown manifold. Compression is effected through affine embeddings to lower-dimensional spaces. These embeddings are obtained via linear regression and bilinear dictionary learning algorithms that leverage manifold smoothness as well as sparsity of the affine model and its residuals. The emergent unifying framework is general enough to encompass known locally linear embedding and compressive sampling approaches to dimensionality reduction. Emphasis is placed on reconstructing high-dimensional data from their low-dimensional embeddings. Preliminary tests demonstrate the analytical claims, and their potential to (de)compressing synthetic and real data.