Trace interpolation is often needed for processing spatially-aliased seismic data. One existing algorithm for trace interpolation is the linear two-step method. The method first finds prediction filters from known traces, and then estimates the missing traces by minimizing the output energy of the prediction filters. This paper presents a new method for finding prediction filters from known, spatially-aliased data. This method has three major advantages over previous methods. First, it can correctly interpolate data whose dip structure varies with respect to frequencies. Second, it does not require the amplitudes of the wavelets along an event to be constant. And third, it correctly determines prediction filters even when the data are completely aliased. Examples with synthetic and field data confirm that this method is superior to the prior algorithms in handling seriously aliased data.