Pith. sign in

REVIEW 4 major objections 5 minor 2 cited by

Controlled Loosening-up (CLuP) -- achieving exact MIMO ML in polynomial time

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 A simple iterative convex program can match the exact maximum-likelihood error rate in MIMO detection, in polynomial time, above a critical signal-to-noise line.

desk verdict A novel algorithm with real empirical appeal, but the headline claim rests on an unproven strong-random-duality equality and on observed iteration counts rather than a complexity proof. read the letter →

arxiv 1909.01175 v1 pith:HS5KQUBU submitted 2019-09-03 cs.IT math.ITmath.STstat.TH

Mihailo Stojnic This is my paper · ORCID
classification cs.ITmath.ITmath.STstat.TH
keywords MIMOdetectionmaximumlikelihoodrandomdualitytheorypolynomial-timealgorithmconvexoptimizationspheredecodingerrorprobabilitylarge-dimensionalasymptotics
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 claims that the maximum-likelihood (ML) detection problem in MIMO systems, widely regarded as computationally hard in its exact form, can be solved to ML-level accuracy in polynomial time by an iterative convex procedure called Controlled Loosening-up (CLuP). CLuP starts from a random binary vector and repeatedly minimizes a linear objective over the feasible region defined by a fixed radius around the received vector and the cube of per-symbol limits; the radius is chosen as a multiple of the polytope-relaxation radius. The theoretical engine is Random Duality Theory (RDT), which yields predictions for both the ML error probability and CLuP's error probability, and the central claim is that above a certain SNR line of corrections these two predictions coincide. If correct, a polynomial-time algorithm attains the optimal MIMO detection performance in large i.i.d. Gaussian channels, not just a good approximation. Numerical experiments with n=400 and n=800 support the predictions.

What carries the argument

The load-bearing object is the CLuP iteration itself: $x^{{(i+1)}}$ = argmin_{||y-Ax|| <= r, x in [-1/$\sqrt$(n),1/$\sqrt$(n)]^n} -($x^{{(i)}}$)^T x, followed by normalization and sign discretization; each subproblem is a convex quadratic program, so the per-iteration cost is polynomial. The analysis side rests on Random Duality Theory (RDT), a large-dimensional technique that replaces the random matrix by independent Gaussian dual variables and concentrates the resulting optimization. For CLuP it produces the bounding function xi_RD($\alpha$,$\sigma$;c2,c1,gamma,nu) = $\sqrt$($\alpha$) $\sqrt$(1-2c1+c2+$sigma^{2}$) + I22 - I1 + I21 - nu c1 - gamma c2, with I22, I1, and I21 the box-constrained integrals given in equation (22). Theorem 1 states that the true limiting objective is at least max_{gamma,nu} xi_RD, with equality claimed when strong random duality holds, which is the step that makes the CLuP error-probability prediction equal to the ML prediction. The first-iteration analysis supplies the guarantee that the initial step lands above the lower stationary point, preventing convergence to a bad local optimum.

What would settle it

For a fixed alpha and sigma with n large, solve the nonconvex limit problem (4) to global optimality on many random instances and compare its normalized optimal value with the RDT value max_{gamma,nu} xi_RD from Theorem 1: a strictly positive gap would show that strong random duality fails and CLuP's predicted error probability is a lower bound rather than the ML-matching value.

Watch

Extended reading notes

Core claim

The paper's central discovery is a duality-based characterization of the CLuP iteration, whose fixed point is the nonconvex problem of minimizing -||x||^2 subject to ||y-Ax||^2 <= r and x in [-1/$\sqrt$(n),1/$\sqrt$(n)]^n, together with the demonstration, theoretically and by simulation, that with r chosen above the polytope-relaxation radius the error probability of the discretized output matches the ML error probability computed by the same RDT machinery. The matching is claimed for the SNR regime above the line of mild or no corrections, which for $\alpha$=0.8 lies around 1/$sigma^{2}$ = 10.7105 dB. Below that line the RDT function xi_RD develops local minima that can trap the simple version of the algorithm; the paper shows these traps can be avoided by restarting or by adding a constraint derived from the polytope solution, and the first-iteration analysis proves that CLuP starts above the lower stationary point. The paper also derives RDT estimates of the ML performance itself at two levels of lifting, with a discontinuity near 9.989 dB corrected by the first level of lifted duality.

Load-bearing premise

The paper's performance prediction for CLuP depends on the assumption that the random-duality lower bound for its limit problem is exactly tight, even though that limit problem minimizes a concave quadratic over the intersection of a cube and a norm ball and standard strong-duality results do not apply to it.

Editorial extensions

If this is right

  • Above the line of mild or no corrections, CLuP's error probability equals the RDT-predicted ML error probability, so a polynomial-time algorithm attains the optimal MIMO detection performance in large i.i.d. Gaussian channels.
  • The number of CLuP iterations is small and essentially independent of the problem dimension; at 10^-8 objective convergence it rarely exceeds 20 and often is below 10, putting the total complexity near that of solving a convex quadratic program.
  • At alpha=0.8 the RDT analysis identifies two critical SNR values, 9.989 dB and 10.7105 dB, below which the simple version of CLuP may need restarts or an added constraint to avoid local minima.
  • The polytope, ball, and SDP relaxation heuristics have error curves far above the ML curve, whereas CLuP with r_sc=1.5 tracks ML down to the correction line, quantifying the gain over standard convex heuristics.
  • Choosing the radius to minimize the predicted error probability, the paper's ultimate CLuP design, gives an error rate that stays at or slightly below the 1FL RDT ML estimate across the displayed SNR range.

Reading between the lines

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

  • If strong random duality is tight, the same CLuP construction should extend to other discrete alphabets such as QAM constellations, since the alphabet-specific ingredient is only the box constraint; the paper says such extensions are straightforward but does not analyze them in detail.
  • The correction line at 10.7105 dB may mark a general algorithmic boundary: the same RDT machinery could be used to predict, for any aspect ratio alpha, the SNR below which any polynomial-time detector will struggle, before running simulations.
  • A practical online variant suggested by the radius-tuning discussion would increase r until the objective stops improving, avoiding the need to know the ML curve in advance; this is an operational consequence the paper mentions only in passing.
  • If CLuP's predictions hold, the exponential hardness of MIMO ML detection in the high-SNR regime is not fundamental; the exponential barrier survives only near and below the correction line, shifting research attention to low-SNR algorithms.
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 proposes an iterative heuristic called Controlled Loosening-up (CLuP) for MIMO maximum-likelihood detection. Each iteration solves a convex problem: minimizing a linear objective -(x^(i))^T x over the intersection of the sphere constraint ||y-Ax||<=r and the cube [-1/sqrt(n),1/sqrt(n)]^n, then rescales the solution. The authors claim that, for carefully chosen r, CLuP achieves the exact ML error probability in polynomial time, and they support this with a Random Duality Theory (RDT) analysis giving Theorem 1, a set of asymptotic performance formulas (Eqs. (28)-(29)), and numerical experiments in Figures 17-18 and Tables 4-7. The ML error probability itself is also estimated through RDT (Theorem 2 and a '1FL RDT' correction). The paper is explicitly an introduction, deferring proofs of the crucial duality equalities, the corrections to the ML estimate, and the complexity analysis to companion papers.

Significance. If the central claim were established, the result would be of substantial interest: a polynomial-time algorithm matching the optimal MIMO ML error probability in large i.i.d. Gaussian channels would be a notable advance over the exponential worst-case complexity of exact ML and over standard convex heuristics. The paper also contains useful numerical evidence that the simple iterative scheme behaves well in the simulated SNR regime, and the derivation of the RDT formulas is detailed and reproducible. However, the load-bearing parts of the claim are asserted rather than proved: the equality in Theorem 1 is not verified for the nonconvex CLuP limit problem, the 'ultimate CLuP' curve involves optimizing over the free parameter rsc, and the polynomial complexity statement rests on observed iteration counts rather than a theorem. As a result, the central claim is not supported as stated. Credit is due for the transparency of the presentation: the paper itself flags the missing strong-random-duality condition immediately after Theorem 1, notes that the 1FL RDT correction is deferred to a companion paper, and reports the empirical rather than proven nature of the iteration count.

major comments (4)
  1. [Section 2.1.1, Theorem 1 and Eq. (24)] Theorem 1 establishes only the inequality xi_p >= max_{gamma,nu} xi_RD. The text immediately asserts that equality holds when strong random duality holds, and refers to [12-16] for the claim that this follows from strong deterministic duality. The CLuP limit problem (4) minimizes the concave function -||x||^2 over the intersection of a ball and a cube; this is a nonconvex problem, and a deterministic Lagrangian dual of such a problem generically has a gap (for example, minimizing -x^2 over x in [-1,1] has a dual value of -infinity, not the primal value -1). No argument is given that strong random duality nevertheless holds for problem (4). All subsequent performance predictions -- Eqs. (28)-(29), the 'ultimate CLuP' curve, Table 1, and the comparisons in Section 4.2 -- use the RDT expression as if it were exact. If the inequality in (24) is strict, then p_err^(CLuP) is a lower bound on the true CLuP error probability, and the claim that CLuP matches ML collapses. The paper flags the missing condition but does not verify it; this is load-bearing.
  2. [Section 3.2.4 and Figures 2, 13] The 'ultimate CLuP' performance curve is obtained by choosing the radius scaling rsc so as to minimize the predicted error probability p_err^(CLuP) given by Eq. (29). This is an optimization over a free parameter that is selected based on the same RDT formulas used to compute the ML estimate. Consequently, the comparison in Figures 2 and 13 between 'ultimate CLuP' and the RDT-based ML curve is not a test of a parameter-free prediction: a shared modeling error in the RDT expressions would affect both curves and would not be detected. The manuscript should either report a fixed, a priori rule for choosing rsc and evaluate the resulting error probability, or provide an out-of-sample validation in which rsc is selected on one dataset and tested on another. As it stands, the agreement in Figures 2 and 13 is weaker evidence for the ML-matching claim than the text suggests.
  3. [Section 5, 'Overall complexity' paragraph] The central claim of polynomial-time exact ML performance is not supported by a complexity theorem. The manuscript states that in the favorable regime the number of iterations needed for a 10^{-8} convergence level was 'rarely over 20' and that this is 'basically matching the complexity of solving a quadratic program.' This is an empirical observation, not a worst-case or even high-probability guarantee, and there is no analysis of how the iteration count scales with n, alpha, sigma, or rsc. Since the whole point of the paper is to break the exponential/polynomial barrier for exact MIMO ML, the complexity claim needs a formal statement (for example, a bound on the number of iterations or a proof of convergence to the exact ML solution) rather than a remark about observed behavior. The paper acknowledges that the complexity analysis is deferred to companion papers, which further supports that this load-bearing assertion is currently unsupported.
  4. [Section 4.1 and Table 4] The ML validation is circular in an important respect. The simulated ML error probabilities in Figure 17 and Table 4 are obtained from a fast bit-flipping heuristic for which, as the paper states, there is no guarantee of optimality. The comparison is made against the author's own RDT-based ML estimate, with the 1FL RDT prediction used as the reference curve. If the RDT ML estimate is biased, the heuristic could be matching a biased prediction rather than the true ML error probability. A comparison against a branch-and-bound exact solver for moderate n (for example, the methods of [23,24]) or against a known lower bound independent of RDT would be needed to establish that the simulated curve is actually the ML error probability. The paper should state clearly which parts of the validation are against exact ML and which are against an RDT prediction.
minor comments (5)
  1. [Table 4, row 1/sigma^2 = 13 db] The simulated value of xi is listed as 1.9994e-02, which appears to be a typo: the theoretical values immediately above are 2.0022e-01, and the simulated values for xi elsewhere in the table are of the same order as the theory. This should read approximately 1.9994e-01.
  2. [Throughout] The paper contains several typographical errors and inconsistences that should be corrected in revision, including 'Algorthms' in the index terms, 'informaton' and 'proce ssing' in the abstract, 'Polytpe' in Section 2, and 'erfinv' in Eq. (40) which should be the inverse error function.
  3. [Section 2.1, Eq. (6)] The rewrite of the constraint in (6) is stated for xsol with all components equal to 1/sqrt(n), but the 'without a loss of generality' justification is not spelled out. Since the components of xsol are assumed to be deterministic and the distribution of A is rotationally invariant, the justification should be given explicitly rather than asserted.
  4. [Figures 2, 13, and 18] The vertical 'line of corrections' is central to the discussion but its location is only described verbally. The figures would be easier to interpret if the coordinates of the vertical lines (10.7105 dB and 9.989 dB) were indicated directly on the plots, as is done for the ML curves in Figure 3.
  5. [Section 3.2.4 and Figure 12] The statement that the choice c2 = 0.9979 'will become clear later on' is awkward; the criterion for selecting this particular value of c2 should be stated when it is first used, since it governs the 'ultimate CLuP' curve in Figures 2 and 13.

Circularity Check

2 steps flagged · score 5.0 of 10

CLuP's ML-matching prediction depends on an unproved self-cited RDT equality and is benchmarked against an RDT-derived ML curve; the 'ultimate CLuP' curve optimizes over the free radius.

  1. uniqueness imported from authors [Section 2.1.1, after Theorem 1 (Eqs. (24)-(25))]
    "Moreover, the inequalities in the above theorem are replaced with equalities when the strong random duality holds. As shown in [12–16] this certainly happens when the strong deterministic duality holds."

    Theorem 1 itself proves only ξp ≥ max_{γ,ν} ξRD. The paper's subsequent CLuP performance formulas, (28)-(29), and every CLuP/ML plot treat the RDT expression as exact. The only justification offered for the equality is the self-cited [12-16] condition of strong deterministic duality, but the CLuP limit problem (4), min −||x||² over {||y−Ax|| ≤ r} ∩ [−1/√n,1/√n]^n, is not convex and has no general deterministic strong duality; no proof is given that strong random duality nevertheless holds for this nonconvex problem. Thus the headline 'CLuP matches ML' is not derived from the stated theorem but imported from the author's prior convex RDT results as an unverified equality.

  2. fitted input called prediction [Section 3.2.4 (Figs. 2, 11-13; Table 1)]
    "if we just stick with the probability of error p(CLuP) err then seemingly the most natural way would be to choose rsc as to minimize p(CLuP) err. Recalling on (29), this essentially means that one should choose rsc so that ν(CLuP) is minimized. The results that we obtained following this strategy are shown in Figures 11 and 12 ... Moreover, the resulting p(CLuP) err is exactly the dashed curve in Figure 2 to which we refer as the ultimate CLuP calculated performance."

    The 'ultimate CLuP' curve is not a prediction for a fixed algorithm; it is the minimum over the free scaling parameter rsc of the RDT expression that is already only a lower-bound estimate. Optimizing the free parameter against the very quantity later reported as the algorithm's predicted error makes the resulting curve an optimized envelope rather than a derived first-principles prediction. In Table 1 and Figures 2/13 this optimized envelope is placed next to the RDT ML estimate, so part of the apparent agreement with ML is a consequence of the parameter freedom rather than a closed-form performance guarantee.

full rationale

The paper contains genuine independent content: Algorithm 1 is a concrete polynomial-time procedure, and the fixed-rsc simulations in Section 4.2 agree with the theory for rsc = 1.1, 1.3, 1.5, so the central claim is not wholly equivalent to its inputs. However, the theoretical bridge from the algorithm to ML is regressive: Theorem 1 provides only an inequality; the equality needed for p_err is carried by a self-cited strong-random-duality condition that is not verified for the nonconvex problem (4); and the ML benchmark itself is an RDT estimate, with the 1FL corrections deferred to companion papers, rather than an external ground truth. The 'ultimate CLuP' comparison additionally optimizes the free radius. This is partial circularity/unsupported self-citation, but not a full definitional equivalence.

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

The central claim depends on a chain of domain assumptions: the large random Gaussian model, the symmetry reduction of xsol, the concentration of Lagrange multipliers, the unproven strong random duality equality for a nonconvex problem, and the adequacy of the RDT ML estimate as a benchmark. The only explicit free parameter is the radius scaling rsc, which is hand-chosen or fitted. No new physical entities are introduced.

free parameters (1)
  • rsc (radius scaling factor) = 1.1, 1.3, 1.5; 'ultimate CLuP' varies with SNR (exact values not tabulated)
    Hand-chosen multiplier on the polytope radius rplt; the 'ultimate CLuP' curve is obtained by minimizing perr over rsc, making the reported best performance a fitted envelope.
assumptions (5)
  • domain assumption Strong random duality holds for the CLuP optimization problem (4), so the RDT lower bound in Theorem 1 is tight.
    Invoked after Theorem 1; the CLuP problem is concave minimization over a convex set, not a convex program, so the stated sufficient condition (strong deterministic duality) is not automatically satisfied.
  • domain assumption A and v are i.i.d. standard normals with m = α n and n large (coherent large-dimensional regime).
    This is the statistical model in Eq. (1) and Section 1; all asymptotic RDT results and comparisons are valid only in this regime.
  • domain assumption Without loss of generality, the transmitted vector xsol has all components equal to 1/sqrt(n).
    Section 2.1 uses symmetry of the Gaussian model to fix the sign pattern; this assumes the error probability is symmetric over the discrete constellation.
  • domain assumption Lagrange multipliers ν and γ concentrate to deterministic values, allowing exchange of min/max and expectation in the RDT steps.
    Used in equations (7)-(18); concentration of these scalars is a pillar of the author's RDT and is not proved in this paper.
  • domain assumption The RDT estimate (40) (with 1FL corrections) approximates the true ML error probability closely enough to serve as the ML benchmark.
    The ML reference curves in Figures 2, 13, and 19 come from the same random duality framework; Section 3.1 admits that corrections may be needed and higher lifting levels may change the estimate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Controlled Loosening-up (CLuP) -- achieving exact MIMO ML in polynomial time." pith.science (2026). https://pith.science/paper/HS5KQUBU

@misc{pith2026190901175,
  author       = {Pith},
  title        = {Pith review of: Controlled Loosening-up (CLuP) -- achieving exact MIMO ML in polynomial time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HS5KQUBU}},
  note         = {Machine review of arXiv:1909.01175}
}
read the original abstract

In this paper we attack one of the most fundamental signal processing/informaton theory problems, widely known as the MIMO ML-detection. We introduce a powerful Random Duality Theory (RDT) mechanism that we refer to as the Controlled Loosening-up (CLuP) as a way of achieving the exact ML-performance in MIMO systems in polynomial time. We first outline the general strategy and then discuss the rationale behind the entire concept. A solid collection of results obtained through numerical experiments is presented as well and found to be in an excellent agreement with what the theory predicts. As this is the introductory paper of a massively general concept that we have developed, we mainly focus on keeping things as simple as possible and put the emphasis on the most fundamental ideas. In our several companion papers we present various other complementary results that relate to both, theoretical and practical aspects and their connections to a large collection of other problems and results that we have achieved over the years in Random Duality.

Figures

Figures reproduced from arXiv: 1909.01175 by the authors.

Figure 1
Figure 1. Comparison of perr as a function of 1/σ2 ; α = 0.8 (RDT) calculating the performance characterizations of all these convexity based techniques is relatively simple and the resulting plots are given in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. perr as a function of 1/σ2 ; α = 0.8 In [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. p (ml) err as a function of 1/σ2 ; α = 0.8 (RDT - 0FL and 1FL (0RSB and 1RSB)) full blue curve is obtained based on the above machinery. One immediately observes that the curve has a very strong and clearly visible discontinuity happening around 9.989[db]. This of course signals that certain corrections might be needed to the estimates that one obtains using the above theorem. We introduce these corrections through … view at source ↗
Figures from the paper (16 more)
Figure 4
Figure 4. Figure 4: ξ (ml) RD as a function of c1; α = 0.8; 1/σ2 = 10.7105[db] (RDT - 0FL (0RSB)) of the 1FL RDT for the companion papers we do mention here that it substantially smoothens the glitch. Still, we do believe that higher levels of lifting actually achieve the exact performanc…
Figure 5
Figure 5. Figure 5: ξ (ml) RD as a function of c1; α = 0.8; 1/σ2 = 9.989[db] (RDT - 0FL (0RSB)) unlikely). This is of course only a particular choice of c2 which will correspond to a particular choice of rsc and consequently r. However, we found no c2 where a local optimum over c1 emerges…
Figure 6
Figure 6. Figure 6: ξRD as a function of c1; α = 0.8; 1/σ2 = 11[db]; c2 = 0.9979 (RDT - 0FL (0RSB)) Combining this with Theorem 1 (and the analysis that preceded Theorem 1) and in particular with (23) one has ξRD,γ1 (α, σ; c2, c1, γ, ν) = − √ c2 + γ1( √ α p 1 − 2c1 + c2 + σ 2 + I22 − I1 +…
Figure 7
Figure 7. Figure 7: ξRD as a function of c1; α = 0.8; 1/σ2 = 10[db]; c2 = 0.985 (RDT - 0FL (0RSB)) ξRD = 0.252694, c2 = 0.92731, c1 = 0.93236, ν = −2.060218, γ = 0.45413, γ1 = 0.901472. (49) We have found no other stationary points and the above two actually exactly correspond to the two …
Figure 8
Figure 8. Figure 8: ξRD as a function of c1; α = 0.8; 1/σ2 = 9[db]; c2 = 0.951 (RDT - 0FL (0RSB)) the criteria to determine what the best possible performance is. There are of course many criteria that one can consider but if we just stick with the probability of error p (CLuP ) err then …
Figure 9
Figure 9. Figure 9: ξRD as a function of c1; α = 0.8; 1/σ2 = 9[db]; c2 = 0.96 (RDT - 0FL (0RSB)) 3.2.6 CLuP – avoiding lower stationary point As earlier calculations and Figures 14 and 15 indicate there are clearly two stationary points that might be of interest when looking at the CLuP’s…
Figure 10
Figure 10. Figure 10: ξRD as a function of c1; α = 0.8; 1/σ2 = 9[db]; c2 = 0.975 (RDT - 0FL (0RSB)) − p π/2(ν 2 + 1)erf(ν/√ 2) − exp(−0.5ν 2 )ν)/(4√ 2πγ) I2,1(γ, ν) = (4γ + 2ν).5erfc((4γ + ν)/ √ 2) − 2exp(−1/2(4γ + ν) 2 )/ √ 2π. (53) Moreover, set ξ (1) RD(α, σ; c1,z, s1, γ, ν) = √ α q c1,…
Figure 11
Figure 11. Figure 11: rsc = ξ (1F LML) p /rplt or is chosen so that p (CLuP ) err is minimal and given as a function of 1/σ2 ; α = 0.8 sx,2(γ, ν) = 2(.5erfc((4γ + ν)/ √ 2)) sxsq,2(γ, ν) = 2sx,2, (58) to finally obtain E((xsol) T x) = 1 − (ρsx,1(ˆγ (1) , νˆ (1)) + (1 − ρ)sx,1(ˆγ (1) , −νˆ (…
Figure 12
Figure 12. Figure 12: perr as a function of c2; 1/σ2 = 11[db]; α = 0.8 [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]
Figure 13
Figure 13. Figure 13: rsc chosen such that p (CLuP ) err is minimal and given as a function of 1/σ2 ; α = 0.8 values and parameters of the simulated systems are given as well. Although it should be clear by itself, we add that 0FLML and 1FLML in superscripts denote estimates obtained based…
Figure 14
Figure 14. Figure 14: ξRD as a function of c2; 1/σ2 = 10 db a) left - full range of c2, b) right - appearance of local optima c2 0.4 0.5 0.6 0.7 0.8 0.9 1 ξRD 0.15 0.2 0.25 0.3 0.35 ξRD as a function of c2 Global minimum r Local minimum sc = 1.41, ξRD = 0.27415 rsc = 1.38, ξRD = 0.26765 rs…
Figure 15
Figure 15. Figure 15: ξRD as a function of c2; 1/σ2 = 9 db a) left - full range of c2, b) right - appearance of local optima 5 Summary As the mechanisms that we presented in previous sections are a somewhat complex interplay of many factors we in this section provide a brief summary of the…
Figure 16
Figure 16. Figure 16: ξRD as a function of c1; α = 0.8; 1/σ2 = 9; – 0FL ML and 1FL ML RDT [PITH_FULL_IMAGE:figures/full_fig_p023_16.png]
Figure 17
Figure 17. Figure 17: p (ml) err as a function of 1/σ2 ; α = 0.8 – theory and simulations [PITH_FULL_IMAGE:figures/full_fig_p024_17.png]
Figure 18
Figure 18. Figure 18: perr as a function of 1/σ2 ; α = 0.8 – theory and simulations [PITH_FULL_IMAGE:figures/full_fig_p025_18.png]
Figure 19
Figure 19. Figure 19: Comparison of perr as a function of 1/σ2 ; α = 0.8 be combined with all the other ones that we have already mentioned. Another very interesting option is to successively change the radius through the iterations within a single running of CLuP. In other words, instead …

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy

    cond-mat.dis-nn 2025-07 conditional novelty 6.0 of 10

    CLuP±Hop approximates Hopfield ground state free energies to within about 0.3% using simple gradient descent, backed by the author's fully lifted random duality theory.

  2. A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy

    cond-mat.dis-nn 2025-07 conditional novelty 5.0 of 10

    The authors propose a CLuP-SK barrier-descent algorithm and report it achieves approximately 0.76 of the SK ground state free energy for n around 2000 to 8000, approaching the theoretical Parisi limit of about 0.763.

Reference graph

Works this paper leans on

27 extracted references · 1 canonical work pages · cited by 2 Pith papers

  1. [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

    2007

  2. [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

  3. [3]

    Donoho, A

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

    arXiv

  4. [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

  5. [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

  6. [6]

    Golub and C

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

    1996

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

  8. [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

Show all 27 references
  1. [9]

    Lovasz M

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

    1993

  2. [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

  3. [11]

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

    arXiv

  4. [12]

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

    arXiv

  5. [13]

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

    arXiv

  6. [14]

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

    arXiv

  7. [15]

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

    arXiv

  8. [16]

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

    arXiv

  9. [17]

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

    arXiv

  10. [18]

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

    arXiv

  11. [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

  12. [20]

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

    2016 arXiv

  13. [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

  14. [22]

    M. Stojnic. Complexity analysis of the controlled loosening-up (C LuP) algorithm. 2019. available online at arxiv

    2019

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

    2000

Pith tools

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