Recent progress in acquisition technology has increased the availability and quality of measured appearance data. Although representations based on dimensionality reduction provide the greatest fidelity to measured data, they require assembling a high-resolution and regularly sampled matrix from sparse and non-uniformly scattered input. Constructing and processing this immense matrix becomes a significant computational bottleneck. We describe a technique for performing basis decomposition directly from scattered measurements. Our approach is flexible in how the basis is represented and can accommodate any number of linear constraints on the factorization. Because its time- and space-complexity is proportional to the number of input measurements and the size of the output, we are able to decompose multi-gigabyte datasets faster and at lower error rates than currently available techniques. We evaluate our approach by representing measured spatially-varying reflectance within a reduced linear basis defined over radial basis functions and a database of measured BRDFs.