In this talk we examine problems related to approximating general linear dimensionality reduction operators by structured surrogates admitting natural, low complexity implementations.  We discuss a special case of convolutional approximations, motivated by their implementability benefits both in hardware (as sampled outputs of certain linear time invariant, or LTI, systems) and software (as partial circulant matrices admit fast memory efficient implementations via Fourier transform methods).  We present several fundamental approximation results for this class of problems, and demonstrate the efficacy of this approach via numerical experiments.