ICESat-2, the first photon counting satellite, maps the earth’s surface with unprecedented details and accuracy. However, the resulting photon clouds, distributed as the ATL-03 geocoded photon product, are vast, unstructured, and noisy datasets. The high density and four-dimensional nature of the photon dataset (location and time), coupled with different responses over different surfaces (e.g., ice, forest cover, water), pose a unique and challenging problem regarding surface detection’s overall objective of intelligently reducing the data volume. Multiscale models uncover hidden structures in data due to their ability to analyze the underlying processes at multiple scales. Besides the traditional wisdom of using multiple scales for improving local and global approximations, in this work, we show their application as an intelligent sampling mechanism for redundant and noisy datasets. Our proposed approach’s fundamental idea is the generation of data dependent and multiscale basis functions and corresponding representative sparse representations, which retain points essential for minimizing the error of reconstruction. Thereby, points associated with rapid spatial change are chosen, while those that are easily reconstructed using the smooth basis functions are discarded. As the final output, the algorithm provides an efficient sparse representation of the data that captures all relevant features for modeling and prediction with quantified uncertainty. Our presentation includes a detailed description of the algorithm and theory as applied to process the ATL-03 geolocated photon product of the ICESat-2 mission. We will demonstrate the efficiency of our approach by examples of different ice sheet surfaces, including heavily crevassed glaciers, that pose a challenge for currently used change detection methods.