A central problem in scientific machine learning is high-dimensional function recovery from limited data. At the same time, recent progress in approximation theory has highlighted the representational power of nonlinear models such as neural networks and their role in modern machine learning. In anisotropic smoothness settings, where the function exhibits different smoothness in different directions, universality questions arise naturally. The challenge is to recover functions efficiently when this anisotropic smoothness is unknown. In this work, we study such questions for recovery from point samples (standard information) in periodic Sobolev spaces with anisotropic smoothness, including both anisotropic Sobolev and anisotropic mixed-smoothness Sobolev spaces. Our approach is a nonlinear reconstruction scheme inspired by compressed sensing, for which we derive worst-case upper bounds on the recovery error in terms of the number of samples. Using widths from information-based complexity, we show that these recovery rates are optimal up to mild, dimension-independent logarithmic factors. Crucially, a single nonlinear recovery algorithm achieves the appropriate rate simultaneously over a range of unknown anisotropic smoothness levels, yielding a universal approximation result. In contrast, linear recovery methods incur unavoidable dimension-dependent logarithmic losses in unknown smoothness settings, reflecting the curse of dimensionality. This justifies the use of nonlinear algorithms for universal approximation in such function spaces.