Pith. sign in

REVIEW 4 major objections 5 minor 28 references

Starting CLuP with polytope relaxation

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 Starting the CLuP algorithm from the polytope-relaxation solution instead of a random point reduces the iteration count for exact MIMO ML detection, reaching near-optimal error within the first three iterations in the regimes studied.

desk verdict Incremental warm-starting note that leans heavily on prior CLuP/RDT machinery; the main simulation table shows a factor-of-twelve mismatch at iteration 3 that the paper waves away. read the letter →

arxiv 1909.01201 v1 pith:XKVH6H4P 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)polytoperelaxationMIMOMLdetectionrandomdualitytheorycomplexityanalysisperiterationbinaryspheredecoding
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

This paper argues that the Controlled Loosening-up (CLuP) algorithm, an iterative method designed to solve the MIMO maximum-likelihood detection problem exactly, becomes even faster when its starting point is the solution of the standard polytope-relaxation heuristic rather than a random vector. The new variant, CLuP-plt, is analyzed iteration by iteration through random duality theory, which yields closed-form large-system predictions for the error probability, objective value, and geometry of each iterate. In the studied regime ($\alpha=0.8$, $1/\sigma^2=13$ dB, $r_{\mathrm{sc}}=1.3$) the predicted error probability after three total iterations is $0.00022$, close to the limiting value $0.00016$, while the original CLuP needs four iterations to reach a comparable error level. The practical stake is that MIMO ML detection is a hard combinatorial problem, and a fixed, small number of simple quadratic-programming iterations with a per-iteration theoretical characterization would be an unusually strong algorithmic guarantee.

What carries the argument

The load-bearing object is the CLuP iteration itself: $x^{(i+1)} = \arg\min_x -(x^{(i)})^{\mathsf{T}}x$ subject to $\|y-Ax\| \leq r$ and $x \in [-1/\sqrt{n}, 1/\sqrt{n}]^n$, followed by normalization, together with the new initialization $x^{(0,\mathrm{plt})} = \arg\min_x \|y-Ax\|^2$ over the same box. The argument is carried by the 'complexity analysis per iteration level': each iterate's objective is written as a random optimization over i.i.d. Gaussian data, and strong random duality replaces it by a deterministic saddle-point functional, e.g. $\xi^{(1)}_{\mathrm{RD}}(\alpha,\sigma; c_{1,z},\gamma) = \sqrt{\alpha}\sqrt{c_{1,z}+\sigma^2} + I_{1,1}(\gamma) + I_{2,1}(\gamma) - \gamma c_{1,z}$. Solving the resulting min-max problems yields predicted per-iteration values for error probability, objective, norm, and inner product with the true solution. The paper states that the whole analysis is structurally identical to the original CLuP's, with the first-iteration parameter $\nu$ set to zero.

What would settle it

Run CLuP-plt at $\alpha=0.8$, $1/\sigma^2=13$ dB, $r_{\mathrm{sc}}=1.3$ with increasing $n$ (800, 1600, 3200) and measure the third-iteration error probability; the theory predicts $p_{\mathrm{err}}^{(3)}=0.00022$ and a limiting value of $0.00016$. If the measured value does not move toward this prediction as $n$ grows — or if it stays near the $0.00270$ reported in the paper's own $n=800$ simulation — the asymptotic prediction is falsified. A sharper check is to compare the empirical distribution of the first-iterate variables $z_i$ with the soft-threshold form $z_i=(1/\sqrt{n})\min(\max(0,-h_i/(2\gamma)),2)$ predicted by Theorem 1; a systematic mismatch there would indicate the strong-random-duality step is not tracking the algorithm.

Watch

Extended reading notes

Core claim

The central claim is that a better initialization transfers directly into faster convergence for CLuP: replacing the random starting point with $x^{(0,\mathrm{plt})}=\arg\min_x \|y-Ax\|^2$ over the box $[-1/\sqrt{n},1/\sqrt{n}]^n$ preserves the per-iteration structure while improving every measured quantity. The paper derives the first-iteration analysis, the second-iteration analysis, and the general $k\to k+1$ step, showing that the large-$n$ limit of each iterate is governed by a max-min saddle-point formula obtained from strong random duality. For $\alpha=0.8$, $1/\sigma^2=13$ dB, $r_{\mathrm{sc}}=1.3$, CLuP-plt reaches $p_{\mathrm{err}}=0.00022$ after three iterations (two CLuP iterations after the initialization), compared with $0.00033$ after four iterations for the original CLuP, and the predicted limiting error is $0.00016$. The paper reports that simulations at $n=800$ closely track the predicted values for the squared norm, inner product with the true solution, and objective, and that the error-probability curves agree with the theoretical picture.

Load-bearing premise

The analysis assumes that the strong-random-duality and exponential-concentration results from the earlier CLuP complexity analysis apply unchanged to CLuP-plt once the starting point is changed; if those duality and concentration properties fail for the polytope-relaxation initialization, the predicted per-iteration error probabilities and the three-to-five iteration claims are unsupported.

Editorial extensions

If this is right

  • At $1/\sigma^2=13$ dB, $\alpha=0.8$, $r_{\mathrm{sc}}=1.3$, CLuP-plt reaches $p_{\mathrm{err}}=0.00022$ after three total iterations, close to the $0.00016$ limiting error, whereas the original CLuP needs four iterations to reach $0.00033$.
  • Counting only CLuP's own iterations after the polytope-relaxation initialization, CLuP-plt uses two iterations where the original CLuP uses four at 13 dB.
  • At 12 dB, five total iterations suffice to approach the limiting performance; at 11 dB, near the line of corrections, eight total iterations reach essentially the optimal error.
  • The per-iteration analysis supplies predicted values for error probability, objective value, squared norm, and inner product with the true solution, and the reported simulations track these predictions as the iterations progress.
  • The $k\to k+1$ step is structurally identical for all later iterations, so the same machinery computes every subsequent parameter without new assumptions.

Reading between the lines

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

  • Because the analysis is structural and not tied to binary MIMO detection, the same polytope-relaxation initialization should accelerate CLuP on other box-constrained problems in the CLuP family (for instance LASSO/SOCP-type settings); that extension is not run in the paper.
  • The improvement suggests a hierarchy: any cheap convex relaxation that yields a feasible point could serve as the CLuP starting point, and only the first-iteration parameters of the random-duality machinery would need updating; the author frames the polytope relaxation as the simplest such choice.
  • The iteration count is regime-dependent: it grows as the SNR moves toward the line of corrections, so the 'fixed small number of iterations' property holds in the operating region studied rather than uniformly; mapping the iteration count as a function of $\alpha$ and SNR would be the natural next step.
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 introduces CLuP-plt, a variant of the Controlled Loosening-up (CLuP) algorithm for MIMO maximum-likelihood detection in which the random initialization of the earlier CLuP algorithm is replaced by the solution of the box-constrained polytope relaxation. It presents a per-iteration complexity analysis: the first iteration is characterized in Theorem 1, the second and generic (k+1)-th iterations are reduced to the machinery of the author's prior work [22], and numerical tables give theoretical per-iteration error probabilities, objective values, norms, and correlations with the true transmitted vector, together with simulations at n=800. The central quantitative claim is that in the regime alpha=0.8, 1/sigma^2=13 dB, rsc=1.3, CLuP-plt reaches near-limit performance within three iterations, improving on the original CLuP.

Significance. If the analysis is valid, the paper demonstrates a fixed, dimension-independent number of iterations for near-ML MIMO detection, which would be a striking and practically relevant property. The comparison with the original CLuP in Table 8 suggests a meaningful iteration-count reduction, and the paper provides a substantial set of theoretical and simulated parameter tables. The main limitation is that the central theorem is delegated to the author's prior random-duality papers and the load-bearing independence assumptions are not established in this manuscript, so the strength of the claim is currently not backed by a self-contained proof.

major comments (4)
  1. [§2, Theorem 1] Theorem 1 is the foundation of the entire per-iteration analysis, yet its proof is entirely delegated: 'Follows automatically from [22]' and 'the strong random duality is trivially in place here as well.' The starting point x(0,plt) in Eq. (4) is a deterministic function of the same A and v that appear in all later iterations, whereas [22] analyzes a random x(0) independent of the data. The paper does not show that the concentration and strong-duality results from [22] transfer to this dependent initialization; without such a transfer, Eq. (13) and the first-row parameters in Table 1 are unsupported. This is load-bearing because the iteration error probabilities in Tables 2-6 are computed from these first-iteration quantities.
  2. [§5, Table 7] At the headline operating point (alpha=0.8, 1/sigma^2=13 dB, rsc=1.3), Table 7 reports simulated p_err^(3)=0.00270 against the theoretical p_err^(3)=0.00022 from Tables 4 and 6, a factor of about 12, and the simulated error increases from 0.00078 at iteration 2 to 0.00270 at iteration 3. No trial count or standard error is reported, so this cannot be dismissed as known finite-n fluctuation. The discrepancy directly contradicts the abstract's claim that CLuP-plt 'often achieves within the first three iterations an excellent performance' and the claim of 'excellent agreement' in Section 5; it must be resolved or the claim revised.
  3. [§3, Eqs. (28), (33), (46)] The parameter c1,z is listed as 0.0835 in Table 1 but appears as 0.835 in the phi(1) sets in Eqs. (33) and (46). Since c1,z enters the denominator in the q(1) formula (28) and is propagated into the second- and third-iteration computations, a factor-of-ten inconsistency changes all downstream quantities. The paper needs a single corrected value and a re-check of Tables 2-6.
  4. [§3-§4] The analysis of iterations two and higher is presented by reference: Eq. (23) is declared 'structurally literally identical' to [22]'s (31), and the generic iteration repeats 'all the steps between (85) and (108) in [22]'. However, the constraints in (23) and (34) involve x(1,s) and the correlation vectors s2,j and matrices Q(k+1), which are estimated from previous iterations and are statistically dependent on A and v. Establishing the exponential concentration of these random objectives and of the optimizing z_i is a substantive step that cannot be obtained merely by declaring the problems structurally identical; the manuscript should state and prove the needed transfer or clearly identify which theorem in [22] supplies it.
minor comments (5)
  1. [Eq. (35)] Eq. (35) writes x(k+1,s)_i = 1/sqrt(n) - z(2)_i; the subscript should be z(k+1)_i.
  2. [§5, Tables 7-10] The simulations report n=800 but no number of trials, so it is impossible to estimate Monte Carlo error; please report trial counts and error bars.
  3. [References] References [22] and [23] are cited as 'available online at arxiv' without arXiv identifiers; since they carry the proofs relied on here, they need complete bibliographic data.
  4. [Throughout] There are several typos and inconsistencies: 'Algorthms' in the index terms, 'havng' in Section 5.1, 'aer' in Table 4, and inconsistent capitalization 'CluP-plt'.
  5. [§5, Table 7 caption] Table 7's caption says 'Simulated (n=800)/Theory-computed (n->infinity)', but the simulation column entries are point estimates; a description of how p_err was estimated (e.g., fraction of symbol errors across trials) would help.

Circularity Check

1 steps flagged · score 4.0 of 10

The paper's per-iteration error predictions rest on a one-sentence proof delegating Theorem 1 to the author's own prior RDT work, but the numerical claims are not fitted to data and retain independent content.

  1. self citation load bearing [Theorem 1 proof (Section 2, Eqs. (9)-(14)); same delegation in Section 3 (Eqs. (23)-(28)) and Section 4 (Eqs. (34)-(41)).]
    "Proof. Follows automatically from [22] and ultimately the RDT mechanisms from [12–16, 18, 19] (as in [22], the strong random duality is trivially in place here as well)."

    Theorem 1 is the load-bearing derivation of the first-iteration error probability, and all later iterations are declared 'structurally literally identical' to [22] with 'all the steps' repeated by reference. Here [22] is the same author's prior CLuP complexity paper, and the cited RDT series [12–21] is also the author's own work. In [22], x(0) was random and independent of A and v; here x(0) is the data-dependent solution of (4), a function of the same A and v used in every subsequent iteration.

full rationale

The claimed derivation chain is not a case of fitted-input circularity: the key parameters (gamma, nu, c1,z, etc.) are obtained by solving the min-max problems (15), (28), and (41), not by matching Tables 7-10, and the simulations are presented afterward as validation. I therefore do not find a step where a prediction is equivalent to its input by construction. The main concern is instead load-bearing self-citation: Theorem 1 is proved by invoking the same author's [22] and RDT series without executing the transfer, and Sections 3-4 say the second and higher iterations are 'structurally literally identical' to [22] and 'repeat all the steps' from it. Because the new initialization x(0) is a function of the same A and v used during CLuP iterations, the independence properties used in [22] are not automatic; the assertion that strong random duality is 'trivially in place' is an unproved premise. The manuscript's own Table 7 provides partial independent grounding for the first two iterations (0.00776 vs 0.00720; 0.00078 vs 0.00092) but contradicts the three-iteration headline at the third iteration (simulated 0.00270 vs theoretical 0.00022), and the error rises from iteration 2 to 3. That is a correctness/validation discrepancy, not circularity, but it reinforces that the imported theory is not independently checked here. A separate decimal inconsistency, c1,z = 0.835 in (33)/(46) versus 0.0835 in Table 1, would change the q(1) computation in (28). On balance: moderate load-bearing self-citation (score 4), central claim not fitted by construction.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper contributes an algorithm variant but inherits the entire proof machinery from self-cited prior work. The only hand-set free parameter is the radius scaling rsc = 1.3. No new physical or mathematical entities are introduced.

free parameters (1)
  • radius scaling rsc = r / r_plt = 1.3
    The algorithm radius r is set as 1.3 times the polytope-relaxation threshold r_plt. All theoretical tables and the central three-to-five iteration claim use this hand-chosen value; Figure 1 of the prior paper shows that different rsc values give different performance.
assumptions (3)
  • domain assumption Random Gaussian model for A and v with m = alpha n and binary x in { -1/sqrt(n), 1/sqrt(n) }^n.
    The entire RDT analysis and the simulation setup rely on i.i.d. standard normal entries for A and v and a fixed aspect ratio alpha = 0.8. This is stated in Section 1, not derived.
  • ad hoc to paper Strong random duality and exponential concentration hold for the specific CLuP-plt optimization problems in (9), (23), and (34).
    Theorem 1 says only "Follows automatically from [22]" and the RDT papers. The same assertion is reused without proof in Sections 3 and 4. This is the load-bearing mathematical premise and it is not established in this paper.
  • ad hoc to paper The polytope-relaxation starting point x(0,plt) inherits the same concentration and limiting behavior as the random starting point analyzed in [22].
    The paper assumes that after replacing the random initialization with the box-constrained least-squares solution, all per-iteration formulas from [22] still hold with only nu set to zero. No separate proof is given for this inheritance.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Starting CLuP with polytope relaxation." pith.science (2026). https://pith.science/paper/XKVH6H4P

@misc{pith2026190901201,
  author       = {Pith},
  title        = {Pith review of: Starting CLuP with polytope relaxation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XKVH6H4P}},
  note         = {Machine review of arXiv:1909.01201}
}
read the original abstract

The Controlled Loosening-up (CLuP) mechanism that we recently introduced in \cite{Stojnicclupint19} 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 \cite{Stojnicclupcmpl19}, we presented a detailed complexity analysis that indeed confirms the relatively small number of iterations. Since both papers, \cite{Stojnicclupint19} and \cite{Stojnicclupcmpl19} 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. \cite{StojnicBBSD05,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 \cite{Stojnicclupcmpl19}, a particular \textbf{\emph{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 \textbf{\emph{first three iterations}} an excellent performance. We also complement the theoretical findings with a solid set of numerical experiments.

Figures

Figures reproduced from arXiv: 1909.01201 by the authors.

Figure 1
Figure 1. perr as a function of 1/σ2 ; α = 0.8 – theory and simulations the attention in [22] is the fact that not only is the number of CLuP’s iterations fixed and small, it is actually achieved without much effort in making the algorithm even the tiniest of the bits more complex than its most basic version. That in the first place meant that in [22], we analyzed CLuP’s complexity by assuming that the starting x (0) is basic… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 4 canonical work pages

  1. [22]

    M. Stojnic. Complexity analysis of the controlled loosening-up (C LuP) algorithm. 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. 14

    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

    1995

  4. [3]

    Donoho, A

    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

    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

    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

    1995

  7. [6]

    Golub and C

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

    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

    2005

Show all 28 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

    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]

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

    2019

  16. [24]

    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

  17. [25]

    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

  18. [26]

    Tibshirani

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

    1996

  19. [27]

    van de Geer

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

    2008

  20. [28]

    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. 16

    2000

Pith tools

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