We consider the problem of efficient end-to-end monitoring of path-level performance metrics in communication networks. Our goal is to minimize the number of measurements or monitoring stations required to maintain an acceptable estimation accuracy. We present a framework based on diffusion wavelets and non-linear estimation. Our procedure involves the development of a diffusion wavelet basis that is adapted to the monitoring problem. This basis exploits spatial and temporal correlations in the measured phenomena to provide a compressible representation of network-wide performance parameters. We then adopt nonlinear estimation techniques to generate predictions for the performance on unmeasured paths, exploiting the compressibility of the aforementioned representation. We demonstrate how our estimation framework can improve the efficiency of end-to-end delay estimation in IP networks and reduce the number of hardware monitors required to track bit-error rates in all-optical networks.