2019/09/03 by Mihailo Stojnic, Stojnic, Mihailo
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1909.01201
arxiv created 2019/09/03 · openalex publication_date 2019/09/03 · arxiv updated 2019/09/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Controlled Loosening-up (CLuP) mechanism that we recently introduced in \citeStojnicclupint19 is a generic concept that can be utilized to solve a large class of problems in polynomial time. Since it relies in its core on an iterative procedure, the key to its excellent performance lies in a typically very small number of iterations needed to execute the entire algorithm. In a separate paper \citeStojnicclupcmpl19, we presented a detailed complexity analysis that indeed confirms the relatively small number of iterations. Since both papers, \citeStojnicclupint19 and \citeStojnicclupcmpl19 are the introductory papers on the topic we made sure to limit the initial discussion just to the core of the algorithm and consequently focused only on the algorithm's most basic version. On numerous occasions though, we emphasized that various improvements and further upgrades are possible. In this paper we present a first step in this direction and discuss a very simple upgrade that can be introduced on top of the basic CLuP mechanism. It relates to the starting of the CLuP and suggests the well-known so-called polytope-relaxation heuristic (see, e.g. \citeStojnicBBSD05,StojnicBBSD08) as the starting point. We refer to this variant of CLuP as the CLuP-plt and proceed with the presentation of its complexity analysis. As in \citeStojnicclupcmpl19, a particular complexity analysis per iteration level type of complexity analysis is chosen and presented through the algorithm's application on the well-known MIMO ML detection problem. As expected, the analysis confirms that CLuP-plt performs even better than the original CLuP. In some of the most interesting regimes it often achieves within the first three iterations an excellent performance. We also complement the theoretical findings with a solid set of numerical experiments.