Lagrangian Coherent Structures are material surfaces that extremize an appropriate finite-time normal repulsion or attraction measure over all nearby material surfaces. The computation of LCS structures heavily depends on an expensive advection of a dense set of particles in order to compute the map of the flow field. However, salient manifolds (cores and boundaries) are intrinsically sparse and their information content is therefore much smaller than the resolution of the sampled volume which suggests a possible improvement of efficiency. Several attempts were made in order to find robust approximations of the flow map derived from the numerical integration of a smaller number of points along the flow. Compressed sensing has been used successfully to reconstruct sparse signals from a small number of samples acquired through a sensing basis that is incoherent with the reconstruction basis. In this work, we discuss the application of the compressed sensing theory to the sampling of the flow map.