Expected complexity of sphere decoding for sparse integer least-square problems

Sparse integer least-squares problems come up in a wide range of applications including wireless communications and genomics. The sphere decoding algorithm can find near-optimal solution to these problems with reduced average complexity if the knowledge of sparsity of the unknown vector is used in decoding. In this paper, we formulate a sphere decoding approach that relies on the ℓ₀-norm constraint on the unknown vector to solve sparse integer least-squares problems. The expected complexity of this algorithm is derived analytically for sparse alphabets associated with common applications such as sparse channel estimation and validated via simulations. The results indicate superior performance and speed compared to the classical sphere decoding algorithm.