2019/09/03 by Mihailo Stojnic, Stojnic, Mihailo · 1 citation
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.1909.01190
openalex publication_date 2019/09/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In our companion paper \citeStojnicclupint19 we introduced a powerful mechanism that we referred to as the Controlled Loosening-up (CLuP) for handling MIMO ML-detection problems. It turned out that the algorithm has many remarkable features and one of them, the computational complexity, we discuss in more details in this paper. As was explained in \citeStojnicclupint19, the CLuP is an iterative procedure where each iteration amounts to solving a simple quadratic program. This clearly implies that the key contributing factor to its overall computational complexity is the number of iterations needed to achieve a required precision. As was also hinted in \citeStojnicclupint19, that number seems to be fairly low and in some of the most interesting scenarios often not even larger than 10. Here we provide a Random Duality Theory based careful analysis that indeed indicates that a very small number of iterations is sufficient to achieve an excellent performance. A solid set of results obtained through numerical experiments is presented as well and shown to be in a nice agreement with what the theoretical analysis predicts. Also, as was the case in \citeStojnicclupint19, we again focus only on the core CLuP algorithm but do mention on several occasions that the concepts that we introduce here are as remarkably general as those that we introduced in \citeStojnicclupint19 and can be utilized in the analysis of a large number of classes of algorithms applicable in the most diverse of scientific fields. Many results in these directions we will present in several of our companion papers.