Finding NEMO: near mutually orthogonal sets and applications to MIMO broadcast scheduling

We define a near-orthogonal set of channel vectors as one that meets certain SIR and SNR guarantees. The probability of finding a near-orthogonal set in a pool of n users is characterized. We identify a phase transition phenomenon in channel geometry whereby this probability transitions from 0 to 1 as k, the number of users that have been examined, increases. It is shown that after this transition the probability of failing to find such a set behaves like θ(k^-m). The rate at which SNR and SIR can be scaled while we remain above this threshold is also characterized. The existence results we provide are not specific to the MIMO scheduling problem, but apply to the more general setting of finding a near-orthogonal set in a random collection of isotropic vectors. The proofs make use of new tight bounds we develop to bound the surface content of spherical caps in arbitrary dimensions. Broader implications of these results are discussed. Specifically, in the case of zero-forcing the best sum rate achievable increases at a rate on the order of log log n.