A method and apparatus for cached adaptive transforms for compressing data streams, computing similarity, and recognizing patterns have been disclosed.In one embodiment of the invention an encoder and decoder begin with a baseline transform. As data is transferred an algorithm is arranged so that the encoder and decoder adapt toward a superior basis than the baseline, with a corresponding reduction in the encoding bit rate. That is the algorithm adapts to the incoming data stream and can use a custom basis. We deliberately avoid having to send the custom basis itself (when possible), because sending the basis vectors consumes precious bandwidth and may defeat the goal of compression. The encoder and decoder can bootstrap themselves into using one or more better bases.In one embodiment of the invention there is no beginning baseline transform shared between the encoder and the decoder.