This paper aims to develop a novel framework to systematically trade-off computational complexity with output distortion, in linear multimedia transforms, in an optimal manner. The problem is important in real-time systems where the computational resources available are time-dependent. We solve the real-time adaptation problem by developing an approximate transform framework. There are three key contributions of this paper - (a) a fast basis approximation framework that allows us to store signal independent partial transform results to be used in real-time, (b) estimating the complexity distortion curve for the linear transform using a basis set and (c) determining optimal operating points and a meta-data embedding algorithm for images that allows for real-time adaptation. We have applied this approach on the FFT transform with excellent results.