Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis

DOI10.1109/TSP.2014.2307836zbMATH Open1394.94957arXiv1402.1519MaRDI QIDQ4579161FDOQ4579161

Haris Vikalo, Somsubhra Barik

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: 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 applications in wireless communications, digital fingerprinting, and array-comparative genomic hybridization systems. Sphere decoding, commonly used for solving integer least-squares problems, can utilize the knowledge about sparsity of the unknown vector to perform computationally efficient search for the solution. In this paper, we formulate and analyze the sparsity-aware sphere decoding algorithm that imposes $el{l}_0$-norm constraint on the admissible solution. Analytical expressions for the expected complexity of the algorithm for alphabets typical of sparse channel estimation and source allocation applications are derived and validated through extensive simulations. The results demonstrate superior performance and speed of sparsity-aware sphere decoder compared to the conventional sparsity-unaware sphere decoding algorithm. Moreover, variance of the complexity of the sparsity-aware sphere decoding algorithm for binary alphabets is derived. The search space of the proposed algorithm can be further reduced by imposing lower bounds on the value of the objective function. The algorithm is modified to allow for such a lower bounding technique and simulations illustrating efficacy of the method are presented. Performance of the algorithm is demonstrated in an application to sparse channel estimation, where it is shown that sparsity-aware sphere decoder performs close to theoretical lower limits.

Full work available at URL: https://arxiv.org/abs/1402.1519

Mathematics Subject Classification ID

Decoding (94B35)

Cited In (5)

• Decoding spherical codes for the Gaussian channel
• Lossless Dimension Reduction for Integer Least Squares With Application to Sphere Decoding
• Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
• Simple Codes and Sparse Recovery with Fast Decoding
• On the sphere-decoding algorithm I. Expected complexity

This page was built for publication: Sparsity-Aware Sphere Decoding: Algorithms and Complexity Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579161)