A “Scene Re-Lighter” provides various techniques for using an automatically reconstructed light transport matrix derived from a sparse sampling of images to provide various combinations of complex light transport effects in images, including caustics, complex occlusions, inter-reflections, subsurface scattering, etc. More specifically, the Scene Re-Lighter reconstructs the light transport matrix from a relatively small number of acquired images using a “Kernel Nyström” based technique adapted for low rank matrices constructed from sparsely sampled images. A “light transport kernel” is incorporated into the Nyström method to exploit nonlinear coherence in the light transport matrix. Further, an adaptive process is used to efficiently capture the sparsely sampled images from a scene. The Scene Re-Lighter is capable of achieving good reconstruction of the light transport matrix with only few hundred images to produce high quality relighting results. Further, the Scene Re-Lighter is also effective for modeling scenes with complex lighting effects and occlusions.