An audio encoder and an audio decoder are based on a combination of two audio channels (201, 202) to obtain a first combination signal (204) as a mid signal and a residual signal (205) which can be derived using a predicted side signal derived from the mid signal. The first combination signal and the prediction residual signal are encoded (209) and written (212) into a data stream (213) together with the prediction information (206) derived by an optimizer (207) based on an optimization target (208). A decoder uses the prediction residual signal, the first combination signal and the prediction information to derive a decoded first channel signal and a decoded second channel signal. In an encoder example or in a decoder example, a real-to-imaginary transform can be applied for estimating the imaginary part of the spectrum of the first combination signal. For calculating the prediction signal used in the derivation of the prediction residual signal, the real-valued first combination signal is multiplied by a real portion of the complex prediction information and the estimated imaginary part of the first combination signal is multiplied by an imaginary portion of the complex prediction information.