Pith. sign in

REVIEW 4 major objections 5 minor 27 references

Complexity analysis of the Controlled Loosening-up (CLuP) algorithm

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims CLuP reaches exact MIMO ML detection through a fixed small number of quadratic-programming iterations, backed by Random Duality Theory per-iteration predictions.

desk verdict A genuinely new per-iteration RDT analysis of CLuP's complexity, with impressive simulation agreement, but the constant-iteration claim rests on asserted strong random duality and hand-fitted overlap matrices for k≥3. read the letter →

arxiv 1909.01190 v2 pith:BNWFL2PY submitted 2019-09-03 cs.IT math.ITmath.STstat.TH

Mihailo Stojnic This is my paper · ORCID
classification cs.ITmath.ITmath.STstat.TH
keywords ControlledLoosening-up(CLuP)MIMOMLdetectionRandomDualityTheoryquadraticprogrammingcomputationalcomplexityiterativealgorithmslarge-scale
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that the Controlled Loosening-up (CLuP) algorithm solves MIMO maximum-likelihood (ML) detection not just accurately but cheaply: the number of iterations needed to reach ML-level accuracy is fixed as the problem size grows, in practice around 4 to 10. Each iteration is only a box-constrained quadratic program, so the iteration count is the whole computational story. Using Random Duality Theory, the paper derives per-iteration tracking equations for the error probability, objective value, norm, and overlap with the true solution, and verifies them by simulation. If the claim holds, MIMO ML detection, normally an exponential search, would be achievable to high precision by a polynomial-time iterative method with exceptionally simple steps.

What carries the argument

The load-bearing machinery is the Random Duality Theory (RDT) random dual: each CLuP iteration's hard constrained quadratic program is replaced by a Gaussian random dual whose expected value, $\xi_{\mathrm{RD}}^{(k)}$, concentrates and can be evaluated through a box-constrained scalar optimization, the $f_{\mathrm{box}}$ functionals. For the second and later iterations the dual must also track cross-overlaps, $q$ between current and previous signal displacements and $p$ between dual multiplier vectors, grown into overlap matrices $P,Q$, because the previous iterate is random and correlated with the channel and noise. The paper's derivation shows how the first-iteration random-dual output feeds the second-iteration dual, and how that transfer is intended to repeat for all $k$.

What would settle it

Run CLuP at $\alpha=0.8$, $r_{\mathrm{sc}}=1.3$, and $1/\sigma^2=13\,\mathrm{dB}$ for $n=1600,3200,6400$, and compare the per-iteration error probability with the paper's predicted ML limit; if the iteration count needed to reach that limit grows with $n$, or the per-iteration values drift from the $\xi_{\mathrm{RD}}^{(k)}$ predictions beyond simulation noise, the central claim fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that CLuP's performance can be characterized exactly iteration by iteration: the second iteration already contains all the new conceptual machinery, and every later iteration is the same step applied inductively. The central technical objects are random-dual functionals $\xi_{\mathrm{RD}}^{(1)}$ and $\xi_{\mathrm{RD}}^{(2)}$ that encode, in the large-$n$ limit, what the quadratic program at that iteration does to the signal; the second-iteration functional introduces cross-overlap parameters $p,q$ (and later matrices $P,Q$) tracking the correlation between the current iterate and earlier ones. The paper derives these functionals for the first two iterations and reports that the resulting predictions, for error probability, objective, norm, and overlap, match simulations closely for $n=400$ to $n=1600$, with the simulated error probability dropping toward the ML limit within roughly five to ten iterations. It then sketches the induction to the $(k+1)$-th iteration and uses estimated $P,Q$ matrices to show the same limiting behavior for later iterations.

Load-bearing premise

The load-bearing premise is that strong random duality holds at the second and every later iteration, meaning the hard constrained optimization can be replaced by its tractable random-dual surrogate without loss of accuracy once the iterate-dependent randomness and cross-overlap parameters are included; the paper asserts this equivalence and defers its proof to a separate paper.

Editorial extensions

If this is right

  • MIMO ML detection is claimed to be reachable by a constant number, about 4 to 10, of box-constrained quadratic programming steps, independent of problem dimension $n$.
  • Each iteration costs polynomial time, so the whole method is claimed to be polynomial-time while approaching the exact ML error rate.
  • The per-iteration predictions for error probability, objective value, norm, and overlap give a full characterization of the algorithm rather than only a termination bound.
  • Larger $n$ is predicted to require fewer iterations, while increasing the radius $r$ is predicted to increase the iteration count.
  • If exact ML is reached in a fixed number of iterations, the usual exponential complexity of ML detection is bypassed in the large-system Gaussian regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural test beyond the paper's own simulations is to push the per-iteration analysis to higher SNR or other values of $\alpha$; if the fixed iteration count survives, the method becomes an attractive practical MIMO decoder outside the binary i.i.d. Gaussian case.
  • The cross-overlap matrices $P,Q$ appear to be the mechanism that lets the dual remember earlier iterates; understanding their fixed-point structure might yield a direct proof of the constant iteration count without running the induction numerically.
  • Because the later-iteration predictions rely on manually estimated $P,Q$, an immediate check is to compute those matrices from the random-dual optimization itself at $k=3$ and compare with the simulated values; agreement would turn the sketch into a derivation.
  • One could also test whether the same per-iteration fixed-point description transfers to non-Gaussian channels, which would indicate that the complexity claim is a property of the algorithm's structure rather than of Gaussian concentration.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper analyzes the computational complexity of the Controlled Loosening-up (CLuP) algorithm for MIMO maximum-likelihood detection. CLuP is an iterative procedure in which each iteration solves a box-constrained quadratic program, and the paper aims to show that a fixed number of iterations (roughly 4 to 10, independent of the problem dimension n) suffices to reach ML-level accuracy. The first iteration is analyzed through a random-duality argument leading to Theorem 1. The second iteration is treated through a more involved random dual that introduces cross-overlap parameters p and q, and the paper claims this constitutes the key conceptual step; later iterations are handled by an inductive extension involving overlap matrices P and Q. The theoretical predictions are compared with simulations for n up to 1600 and for r_sc = 1.3 and 1.5, showing close agreement. The paper concludes that CLuP approaches exact ML performance in a fixed, small number of simple QP iterations.

Significance. If the central claim is correct, the paper would establish a striking phenomenon: exact MIMO ML performance achievable in a number of convex QP iterations that is constant in n, rather than growing with problem size. The paper also introduces a random-duality formalism for iterated algorithms with data-dependent iterates, which is conceptually interesting. The first-iteration analysis is clean and supported by convincing simulations, and the second-iteration random-dual computation gives predictions that match simulations closely. However, the strongest claims about all later iterations rest on unproved strong-random-duality assumptions and on manually estimated overlap matrices, so the paper does not yet deliver a proof of the fixed-iteration claim. The extensive simulation tables are a genuine strength, particularly the scaling checks across n, but they do not by themselves establish n-independence.

major comments (4)
  1. [Section 3, Eq. (38) and surrounding text] The second-iteration random dual in Eq. (38) is introduced with the statement, after Eq. (38), that the justification 'we leave it for a separate paper.' The replacement of the primal object ξ_{p,2} by the min_q max_p form over cross-overlaps p and q is exactly the step that would need a strong-random-duality theorem, and this theorem is not stated or proved. Theorem 1 covers only the first iteration, where x^(0) is independent of A and v; it cannot be inherited by the second iteration because x^(1) is a function of A and v. Since the second iteration is described as the key step for all later iterations, this missing proof is load-bearing for the paper's central claim.
  2. [Section 4, Step 2 and Eq. (93)] The inductive extension to the (k+1)-th iteration assumes that a strong random duality holds for the overlap matrices P^(k+1) and Q^(k+1), with the same Gibbsian-measure interpretation mentioned in Section 3. No proof or even a precise statement of this duality is given; the text simply says the remarks analogous to (39) and (40) remain in place. The constant-iteration conclusion depends on this unproved assertion for every k, so the central claim is not established.
  3. [Section 4.2, Eqs. (123)-(124) and Table 11] For k ≥ 3, the theoretical numbers in Table 11 are not obtained from a self-contained derivation: Section 4.2 states that P and Q were 'manually estimated' (Eqs. (123)-(124)), and the text acknowledges that these estimates 'are a little bit different from the values that can be obtained from a more precise systematic numerical analysis.' Consequently, the k = 3, 4, 5 'theory-estimated' values in Tables 11 and 13 are partially calibrated objects, not predictions of the random-duality formalism. This weakens the evidence for the claimed per-iteration accuracy of the theory beyond the second iteration.
  4. [Eqs. (48) and (99)] In passing from (46) to (48) and from (99) to (100), the paper neglects the σ-dependent h0 term in the random dual with no quantitative error bound. The text simply says the term 'is neglected.' If this term contributes at the same asymptotic order as the retained terms, the resulting expressions for ξ_RD are not fully justified. A bound or an argument showing the term is o(1) after scaling is needed before the theoretical curves can be treated as exact predictions.
minor comments (5)
  1. [Eq. (54)] The definition of f_box,2 in Eq. (54) writes the maximization over γ and ν, but the integrand f_box,2(h,γ,ν) in Eq. (55) depends on ν2, and the subtracted term is written as νs2√n − νs3√n rather than the expected νs2√n + ν2s3√n. This appears to be a typographical inconsistency that should be corrected for reproducibility.
  2. [Table 2 vs. Table 3] The signs of ξ_RD and s1 in Table 2 differ from those in Table 3 for the same quantities (e.g., ξ_RD is listed as 0.2252 in Table 2 and −0.2252/0.2252 in Table 3). The sign convention should be clarified, since it affects the interpretation of the constraint in Eq. (22).
  3. [Abstract and Index Terms] There is a typo in the Index Terms: 'Algorthms' should be 'Algorithms.'
  4. [Section 5] The paper never specifies a formal precision threshold for 'excellent performance' or 'a very small number of iterations.' Without such a threshold, the statement that the number of iterations is constant in n is not quantitatively defined; the claim should be made precise (e.g., for a fixed target error probability, the required number of iterations is bounded uniformly in n).
  5. [Throughout] The paper frequently defers technical details to companion papers, and several key formulas (e.g., the solution of (13) and the derivation of (18)) are cited rather than derived. This is acceptable in principle, but the dependence on unpublished companion papers for load-bearing steps should be reduced or the arguments should be included in an appendix.

Circularity Check

1 steps flagged · score 6.0 of 10

The k>=3 'theory-estimated' iteration values include manually estimated d1/d2 and P/Q that are then reported as predicted outputs; Table 13's comparison is partly a fitted-input check. The second-iteration strong duality remains an unproved asserted step.

  1. fitted input called prediction [Section 4.2, 'Numerical results – (k+1)-th iteration', before Eqs. (123)-(124) and Tables 10-13]
    "We have done so and manually estimated matrices P , Q, and vectors d1 and d2 throughout the process. ... Moreover, in Table 10 we give the estimated values for vectors d1 and d2. In Table 11, we complement these values for d1 and d2 with the estimated values for p_err and s as well. Since all these rely on some manual estimates..."

    The vectors d1 and d2 in Tables 10/11 are introduced as hand estimates ('manually estimated ... throughout the process') and then the same values reappear as the 'theory-estimated' entries for k=3,4,5 in Table 13, where they are compared with simulations. A quantity that is an input of the estimation procedure cannot also serve as an output prediction of that procedure; agreement of d1^(k),d2^(k) with simulation is therefore by construction, not evidence for the RDT derivation. The P,Q matrices are also manually set before computing f_sph^(k+1) and the per-iteration objective, so the k>=3 p_err and s 'theory-estimated' numbers are not derived from the random-duality formalism alone but are conditioned on hand-fitted overlaps.

full rationale

The first two iterations are not circular: Section 2 derives the first-iteration random dual in Eqs. (7)-(20) and Section 3 repeats the derivation for the second iteration in Eqs. (31)-(76), with simulations in Tables 3-4 and 7-9 agreeing well. The 'strong random duality trivially holds' statement in Theorem 1 covers the first iteration; however, the analogous second-iteration duality is asserted, not proved: after Eq. (38) the paper says 'we leave it for a separate paper' and invokes 'Gibbsian measures randomness'. That is an unproved load-bearing premise, and Section 4's induction for k>2 inherits it, but it is a correctness gap rather than a circular reduction. The genuine circularity appears for k>=3 in Section 4.2: the 'theory-estimated' d1,d2 and P,Q are manually estimated inputs, yet Tables 10, 11 and 13 present the same d1,d2 as theory outputs and compare them with simulations. Equation (127) even uses a 'trivial ad-hoc choice' for the P,Q-dependent coefficients in the f_sph bound. Therefore the later-iteration theoretical numbers are partly calibrated rather than independent predictions, and the abstract's cautious 'indicates' wording is appropriate. Because the first two iterations and the finite-n simulations provide independent content, the paper is not wholly circular; the manual-estimate-as-prediction affects only the k>=3 rows, so the score is 6 rather than higher.

Assumptions & free parameters 2 free parameters · 5 assumptions · 3 invented entities

The central claim rests on two classes of unproved inputs: strong random duality for multi-constraint random duals, and manually estimated overlap matrices for iterations beyond the second. The first two iterations are partially derived, but the general k-th iteration result is not established from stated assumptions alone. The hand-picked r_sc values also affect all quantitative conclusions.

free parameters (2)
  • r_sc (radius scaling factor) = 1.3 and 1.5
    The CLuP iteration count and all reported per-iteration values depend on this hand-chosen scaling of the sphere radius; no derivation selects it.
  • P and Q overlap matrices for k>=3 = P^(5) and Q^(5), eqs (123)-(124)
    These matrices are inputs to the k>=3 theoretical estimates and are manually tuned rather than obtained from the stated optimization; the resulting p_err predictions are therefore partly fitted.
assumptions (5)
  • domain assumption Strong Random Duality holds for the first-iteration random dual (Theorem 1).
    The proof says 'the strong random duality trivially holds' and cites [12-16,18,19]; no proof or verification is provided in this paper. This is load-bearing for all first-iteration predictions.
  • domain assumption Strong Random Duality holds for the second-iteration and k-th iteration random duals with P,Q overlap constraints.
    Section 3 Step 2 explicitly defers the underlying 'Gibbsian measures randomness' and fundamentals to a separate paper; yet equations (38) and (93) are treated as valid. If this fails, the iteration predictions are unsupported.
  • domain assumption All relevant order parameters concentrate exponentially in n.
    Used throughout to replace expectations with concentrating values, e.g., after eq (7), eq (26), and eq (63). This is standard in the author's RDT framework but not proved here.
  • ad hoc to paper The neglected terms in (48), (99), and the h0 terms are asymptotically negligible.
    The paper simply says 'neglected' or 'doesn't really play much of a role' without error analysis, yet these terms are part of the random-dual objective.
  • ad hoc to paper The manually estimated P and Q matrices are accurate enough for the reported k>=3 predictions.
    Section 4.2 uses manually estimated P,Q to produce theory-estimated values; accuracy is not systematically quantified.
invented entities (3)
  • Cross-overlap parameters p and q
    purpose: Encode the correlation between consecutive iterations in the random dual.
    Introduced in eqs (39)-(40) as presumed concentrating values; their existence and meaning are deferred to a companion paper.
  • Overlap matrices P^(k+1) and Q^(k+1)
    purpose: Encode all z and lambda cross-overlaps required for the k-th iteration random dual.
    Defined in eqs (90)-(93) and manually estimated for k>=3; no independent falsifiable prediction outside the RDT formalism.
  • Gibbsian-measure randomness
    purpose: Accounts for averaging over all optimal z and lambda configurations in the random dual.
    Mentioned in Section 3 Step 2 and Section 4 Step 2 without definition or proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complexity analysis of the Controlled Loosening-up (CLuP) algorithm." pith.science (2026). https://pith.science/paper/BNWFL2PY

@misc{pith2026190901190,
  author       = {Pith},
  title        = {Pith review of: Complexity analysis of the Controlled Loosening-up (CLuP) algorithm},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BNWFL2PY}},
  note         = {Machine review of arXiv:1909.01190}
}
abstract

In our companion paper \cite{Stojnicclupint19} 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 \emph{computational complexity}, we discuss in more details in this paper. As was explained in \cite{Stojnicclupint19}, 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 \cite{Stojnicclupint19}, 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 \cite{Stojnicclupint19}, 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 \cite{Stojnicclupint19} 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.

Figures

Figures reproduced from arXiv: 1909.01190 by the authors.

Figure 1
Figure 1. perr as a function of 1/σ2 ; α = 0.8 – theory and simulations after 10 iterations the CLuP’s performance matches the theoretical prediction on the fifth decimal level (the meaning of all relevant quantities is rather clear; we just add that ˆs (k) is the value of the CLuP’s objective after the k-th iteration; it also goes without saying that all quantities given in the table are the expected values which due to an o… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 21 canonical work pages

  1. [22]

    M. Stojnic. Controlled loosening-up (CLuP) – achieving exact MIMO ML in polynomial time. 2019. available online at arxiv

    work page 2019

  2. [1]

    Bunea, A

    F. Bunea, A. B. Tsybakov, and M. H. Wegkamp. Sparsity oracle in equalities for the lasso. Electronic Journal of Statistics , 1:169–194, 2007

    work page 2007

  3. [2]

    Chen and D

    S.S. Chen and D. Donoho. Examples of basis pursuit. Proceeding of wavelet applications in signal and image processing III , 1995

    work page 1995

  4. [3]

    The Noise-Sensitivity Phase Transition in Compressed Sensing

    D. Donoho, A. Maleki, and A. Montanari. The noise-sensitiviy thas e transition in compressed sensing. available online at http://arxiv.org/abs/1004.1218

    work page Pith review arXiv

  5. [4]

    Fincke and M

    U. Fincke and M. Pohst. Improved methods for calculating vecto rs of short length in a lattice, including a complexity analysis. Mathematics of Computation , 44:463–471, April 1985

    work page 1985

  6. [5]

    Goemans and D

    M. Goemans and D. Williamnson. Improved approximation algorithms for maximum cut and satisfia- bility problems using semidefinite programming. Journal of ACM , 42(6):1115–1145, 1995

    work page 1995

  7. [6]

    Golub and C

    G. Golub and C. Van Loan. Matrix Computations . John Hopkins University Press, 3rd edition, 1996

    work page 1996

  8. [7]

    Hassibi and H

    B. Hassibi and H. Vikalo. On the sphere decoding algorithm. Part I : The expected complexity. IEEE Trans. on Signal Processing , 53(8):2806–2818, August 2005

    work page 2005

Show all 27 references
  1. [8]

    Jalden and B

    J. Jalden and B. Ottersten. On the complexity of the sphere dec oding in digital communications. IEEE Trans. on Signal Processing , 53(4):1474–1484, August 2005

    2005

  2. [9]

    Lovasz M

    L. Lovasz M. Grotschel and A. Schriver. Geometric algorithms and combinatorial optimization . New York: Springer-Verlag, 2nd edition, 1993

    1993

  3. [10]

    Meinshausen and B

    N. Meinshausen and B. Yu. Lasso-type recovery of sparse re presentations for high-dimensional data. Ann. Statist. , 37(1):246270, 2009

    2009

  4. [11]

    M. Stojnic. Block-length dependent thresholds in block-spars e compressed sensing. available online at http://arxiv.org/abs/0907.3679

    arXiv

  5. [12]

    M. Stojnic. Discrete perceptrons. available online at http://arxiv.org/abs/1306.4375

    arXiv

  6. [13]

    M. Stojnic. A framework for perfromance characterization o f LASSO algortihms. available online at http://arxiv.org/abs/1303.7291

    arXiv

  7. [14]

    M. Stojnic. A performance analysis framework for SOCP algorithms in noisy compressed sensing. available online at http://arxiv.org/abs/1304.0002

    arXiv

  8. [15]

    M. Stojnic. A problem dependent analysis of SOCP algorithms in noisy compressed sensing. available online at http://arxiv.org/abs/1304.0480

    arXiv

  9. [16]

    M. Stojnic. Regularly random duality. available online at http://arxiv.org/abs/1303.7295

    arXiv

  10. [17]

    M. Stojnic. Upper-bounding ℓ1-optimization weak thresholds. available online at http://arxiv.org/ abs/1303.7289. 31

    arXiv

  11. [18]

    M. Stojnic. Various thresholds for ℓ1-optimization in compressed sensing. available online at http:// arxiv.org/abs/0907.3666

    arXiv

  12. [19]

    M. Stojnic. Recovery thresholds for ℓ1 optimization in binary compressed sensing. ISIT, IEEE Inter- national Symposium on Information Theory , pages 1593 – 1597, 13-18 June 2010. Austin, TX

    2010

  13. [20]

    M. Stojnic. Box constrained ℓ1 optimization in random linear systems – asymptotics. 2016. available online at http://arxiv.org/abs/1612.06835

    2016 arXiv

  14. [21]

    M. Stojnic. Box constrained ℓ1 optimization in random linear systems – finite dimensions. 2016. availab le online at http://arxiv.org/abs/1612.06839

    2016 arXiv

  15. [23]

    Stojnic, Haris Vikalo, and Babak Hassibi

    M. Stojnic, Haris Vikalo, and Babak Hassibi. A branch and bound a pproach to speed up the sphere decoder. ICASSP, IEEE International Conference on Acoustics, Signa l and Speech Processing , 3:429– 432, March 2005

    2005

  16. [24]

    Stojnic, Haris Vikalo, and Babak Hassibi

    M. Stojnic, Haris Vikalo, and Babak Hassibi. Speeding up the sphe re decoder with H ∞ and SDP inspired lower bounds. IEEE Transactions on Signal Processing , 56(2):712–726, February 2008

    2008

  17. [25]

    Tibshirani

    R. Tibshirani. Regression shrinkage and selection with the lasso. J. Royal Statistic. Society , B 58:267– 288, 1996

    1996

  18. [26]

    van de Geer

    S. van de Geer. High-dimensional generalized linear models and th e lasso. Ann. Statist. , 36(2):614–645, 2008

    2008

  19. [27]

    van Maaren and J.P

    H. van Maaren and J.P. Warners. Bound and fast approximation algorithms for binary quadratic optimization problems with application on MAX 2SAT. Discrete applied mathematics , 107:225–239, 2000. 32

    2000

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.