Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis

Integer least-squares problems, concerned with solving a system of equations where the components of the unknown vector are integer-valued, arise in a wide range of applications. In many scenarios the unknown vector is sparse, i.e., a large fraction of its entries are zero. Examples include various applications in wireless communications, digital fingerprinting, and array-comparative genomic hybridization systems. Sphere decoding, often used for solving integer least-squares problems, can utilize the knowledge about sparsity of the unknown vector to perform a computationally efficient search for the solution. In this work, the sparsity-aware sphere decoding algorithm that imposes l0-norm constraint on the admissible solution is formulated and analyzed. Analytical expressions for the expected complexity of the algorithm for alphabets typical of sparse channel estimation and source allocation applications are derived and validated.

The results demonstrate far superior performance and speed of sparsity aware sphere  decoder compared to the conventional sparsity-unaware algorithm as well as heuristic sparsity-aware techniques. Moreover, variance of the complexity of the sparsity-aware sphere decoding algorithm for binary alphabets was derived. The work is complemented with the derivation of fast variants of the algorithm that further reduce the search space without compromising optimality, and demonstrations of the superior performance over existing competing methods in several applications. 

This research undertaken by WNCG Prof. Haris Vikalo and student Somsubhra Barik. 

Paper: Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis