In this paper, we introduce a class of nonsmooth nonconvex least square optimization problem using convex analysis tools and we propose to use the iterative minimization-majorization (MM) algorithm on a convex set with initializer away from the origin to find an optimal point for the optimization problem. For this, first we use an approach to construct a class of convex majorizers which approximate the value of non-convex cost function on a convex set. The convergence of the iterative algorithm is guaranteed when the initial point @math is away from the origin and the iterative points @math are obtained in a ball centred at @math with small radius. The algorithm converges to a stationary point of cost function when the surregators are strongly convex. For the class of our optimization problems, the proposed penalizer of the cost function is the difference of @math -norm and the Moreau envelope of a convex function, and it is a generalization of GMC non-separable penalty function previously introduced by Ivan Selesnick in IS17 .
The current paper is proposing the use of majorization-minimization (MM) algorithm to solve the class of nonconvex nonsmooth optimization problems of type ). This approach has been used for example in @cite_8 @cite_10 @cite_0 for solving some optimization problems different than what we consider here. There are another types of methods that have been proved effective in solving nonconvex problems. For example, iteratively reweighted least squares (IRLS) method ( @cite_3 ) and iteratively reweighted @math (IRL1) ( @cite_4 ). For a list of other methods, we refer the reader to see @cite_0 and the reference therein.
@cite_4 @cite_8 @cite_3 @cite_0 @cite_10
2107861471 2119883478 2531491639 1595863776
It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained l1 minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms l1 minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted l1-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the l1 norm of the coefficient sequence as is common, but by reweighting the l1 norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing. Under certain conditions (known as the restricted isometry property, or RIP) on the mN matrix ˆ (where m<N ), vectors x 2 R N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y WDx even though ˆ � 1 .y is typically an .Nm -dimensional hyperplane; in addition, x is then equal to the element in ˆ � 1 .y of minimal 1-norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x, as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w, the element in ˆ � 1 .y with smallest 2.w -norm. If x .n is the solution at itera- tion step n, then the new weight w .n is defined by w .n WD Œjx .n j 2 C " 2� � 1=2 , i D 1; :::;N , for a decreasing sequence of adaptively defined "n; this updated weight is then used to obtain x .nC1 and the process is repeated. We prove that whensatisfies the RIP conditions, the sequence x .n converges for all y, re- gardless of whether ˆ � 1 .y contains a sparse vector. If there is a sparse vector in ˆ � 1 .y , then the limit is this sparse vector, and when x .n is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast (linear convergence in the terminology of numerical optimization). The same al- gorithm with the "heavier" weight w .n D Œjx .n The class of majorization---minimization algorithms is based on the principle of successively minimizing upper bounds of the objective function. Each upper bound, or surrogate function, is locally tight at the current estimate, and each minimization step decreases the value of the objective function. We present a majorization---minimization approach based on a novel convex---nonconvex upper bounding strategy for the solution of a certain class of nonconvex nonsmooth optimization problems. We propose an efficient algorithm for minimizing the (convex) surrogate function based on the alternating direction method of multipliers. A preliminary convergence analysis for the proposed approach is provided. Numerical experiments show the effectiveness of the proposed method for the solution of nonconvex nonsmooth minimization problems. type="main" xml:id="insr12022-abs-0001"> Modern computational statistics is turning more and more to high-dimensional optimization to handle the deluge of big data. Once a model is formulated, its parameters can be estimated by optimization. Because model parsimony is important, models routinely include non-differentiable penalty terms such as the lasso. This sober reality complicates minimization and maximization. Our broad survey stresses a few important principles in algorithm design. Rather than view these principles in isolation, it is more productive to mix and match them. A few well-chosen examples illustrate this point. Algorithm derivation is also emphasized, and theory is downplayed, particularly the abstractions of the convex calculus. Thus, our survey should be useful and accessible to a broad audience.