Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Problems with Applications to Background/Foreground Extraction

1. Introduction.

• The model allows convex Ψ and possibly nonconvex, nonsmooth, non-Lipschitz Φ, with linear maps and regularizers that can induce low rank or sparsity.Background/foreground extraction is modeled by decomposing video data into low-rank background and sparse foreground components.Source: §1 · pp. 1–2
• Prior convergence results do not cover direct ADMM adaptation to the general model, including its nonconvex nonsmooth terms and nontrivial dual step-size.The paper studies dual step-sizes τ ≠ 1, which the authors say had not been studied in nonconvex scenarios.Source: §1 · p. 3
• For any positive dual step-size below the golden ratio, bounded iterates and a penalty above a computable τ-dependent threshold yield a stationary cluster point.A tailored potential function supports the analysis; if it is a Kurdyka–Łojasiewicz function, the whole sequence converges globally.Source: §1 · pp. 3–4
• The paper also gives an initialization strategy to guarantee boundedness of the generated sequence.The convergence result additionally establishes global convergence of the whole sequence when the special potential function is a Kurdyka–Łojasiewicz function.Source: §1 · p. 4
• Real-data experiments compare the proposed ADMM using different nonconvex regularizers with PALM and report efficiency for a nontrivial dual step-size.The experiments focus on background/foreground extraction.Source: §1 · p. 4

2. Notation and preliminaries.

• The notation section defines matrix norms, the trace inner product, linear-map adjoints and eigenvalue bounds, and the indicator and normal-cone notation used later.It also defines distance to a set and the closest-point projection.Source: §2 · pp. 4–5
• The paper uses the limiting subdifferential, which agrees with the classical derivative for continuously differentiable functions and with the convex subdifferential for convex functions.A local minimizer satisfies the generalized Fermat condition, which underlies the stated first-order necessary conditions for the model.Source: §2 · pp. 4–6
• The Kurdyka–Łojasiewicz property is introduced as a local condition on a proper lower semicontinuous function, and a function satisfying it throughout the relevant domain is called a KL function.The paper recalls a uniformized version on compact sets for use in the global convergence analysis.Source: §2 · p. 5
• A point is stationary for the model when it satisfies the first-order conditions specified in the preliminaries.The paper defines stationarity by requiring the model’s conditions (2.2), which are also necessary at a local minimizer.Source: §2 · p. 6

3. Alternating direction method of multipliers.

• The ADMM uses three variable blocks under the constraint B(L) + C(S) = Z, with multiplier Λ and penalty parameter β in the augmented Lagrangian.Each iteration updates the primal variables and then the multiplier; the algorithm accepts a dual step-size τ as input.Source: §3 · p. 6
• The multiplier update adds a dual step-size τ, extending the compared ADMM formulation beyond its τ = 1 setting.The text notes that τ around 2 had been demonstrated to speed convergence in cited convex-problem variants; it also says τ = 2 gives the worst performance for the paper’s nonconvex problems.Source: §3 · pp. 6–7
• For common choices such as nuclear- and ℓ1-norm regularizers, the L- and S-subproblems can be solved efficiently by proximal gradient methods.Some indicator-function L-updates have explicit projections, while certain separable sparsity penalties yield an S-update solvable by root finding.Source: §3 · p. 7
• The convergence analysis is stated for a restricted range of positive dual step-sizes and proceeds under suitable assumptions.The cited prior result for τ = 1 does not directly cover τ ≠ 1 or nonsmooth nonconvex Φ.Source: §4 · p. 7, §3 · p. 7

• A specially constructed potential function underpins the analysis, and it decreases along ADMM iterates when β exceeds a computable threshold.For 0 < τ < 1+√2, the potential is at least the augmented Lagrangian, with equality at τ = 1.Source: §4 · p. 8
• If (a1) and (a3) of Assumption 4.1 hold, then 0 < τ < 1+√2 and β > β̄ guarantee that the ADMM sequence is bounded.Source: §4 · p. 11
• Under Assumption 4.1, 0 < τ < 1+√2, and β > β̄, successive iterates approach one another and every cluster point is stationary.Source: §4 · p. 13
• For any β > 1, the paper reports an interval of dual step-sizes containing τ = 1 for which the corresponding ADMM converges.If β starts below β̄, it can be increased until it exceeds the threshold; if it is never increased, successive changes vanish and the sequence is bounded, with cluster points stationary when Φ is continuous.Source: §4 · p. 15
• With Assumption 4.1, 0 < τ < 1+√2, β > β̄, and a KL potential function, the entire ADMM sequence converges to a stationary point.The KL condition is additional to Assumption 4.1.Source: §4 · p. 16

Convergence analysis

• The proof shows that the potential function is constant on the set of cluster points of the generated sequence.This constancy enables application of the uniformized KL property in the sequence-convergence argument.Source: §4 · pp. 16–17
• If the potential is a Kurdyka–Łojasiewicz function, the generated sequence is convergent.The proof establishes that the potential is constant on the cluster-point set, then uses the KL property and a subgradient bound to show the sequence is Cauchy.Source: §4 · pp. 17, 20
• A suitable initialization can ensure Assumption 4.1(a3), and a specific strategy satisfies the required conditions for objectives Ψ(L)=δΩ(L) and Φ(S) of form (1.2), with Ω compact and convex.The paper states that the initialization conditions can be met and presents a strategy for this class of problems.Source: §4 · pp. 20, 22

5.1. Implementation details.

• The tests use four real videos and compare three sparse regularizers under noisy and noisy-blurred observation models.The models use A(L + S) = L + S for noisy data and A(L + S) = H(L + S) for blurred, noisy data.Source: §5.1 · p. 23

5.2. Comparisons between ADMM with different τ and PALM.

• The benchmark comprises 720 problems with A(L + S) = L + S and 240 with A(L + S) = H(L + S).The unblurred tests span four videos, three sparse regularizers, ten μ choices, and six p and α choices; the blurred tests use two p and α choices.Source: §5.2 · p. 25
• ADMM with τ = 0.8 or 1 usually takes fewer iterations than PALM with comparable function values; τ = 1.6 is fastest under blurring but ends with the worst function value.For the bridge regularizer, τ = 0.8 slightly outperforms τ = 1 in iteration count; other regularizers show comparable performance.Source: §5.2 · p. 26

5.3. Simulation Results.

• Foreground recovery is scored by F-measure after thresholding the recovered support at 1e-3; the reported μ maximizes F-measure for each p and α.The experiments include noisy and noisy-blurred surveillance videos.Source: §5.3 · p. 27
• ADMM with τ = 0.8 takes less CPU time on most extraction problems while returning comparable F-measures.The paper also describes the extraction results in Figs. 5.5 and 5.6 as promising.Source: §5.3 · p. 27

6. Concluding remarks. √

• For τ in (0, 1+√2), the ADMM has stationary cluster points under assumptions, and the whole sequence converges when the potential function is KL.The paper also reports computational results demonstrating the algorithm’s efficiency.Source: §6 · p. 27
• The method may not be beneficial when B or C lacks special structure because the corresponding ADMM subproblems may lack closed-form solutions.Source: §6 · p. 28