  Consider a MIMO interference channel whereby each transmitter and receiver
are equipped with multiple antennas. The basic problem is to design optimal
linear transceivers (or beamformers) that can maximize system throughput. The
recent work [1] suggests that optimal beamformers should maximize the total
degrees of freedom and achieve interference alignment in high SNR. In this
paper we first consider the interference alignment problem in spatial domain
and prove that the problem of maximizing the total degrees of freedom for a
given MIMO interference channel is NP-hard. Furthermore, we show that even
checking the achievability of a given tuple of degrees of freedom for all
receivers is NP-hard when each receiver is equipped with at least three
antennas. Interestingly, the same problem becomes polynomial time solvable when
each transmit/receive node is equipped with no more than two antennas. Finally,
we propose a distributed algorithm for transmit covariance matrix design, while
assuming each receiver uses a linear MMSE beamformer. The simulation results
show that the proposed algorithm outperforms the existing interference
alignment algorithms in terms of system throughput.
