This paper proposes the Proximal Iteratively REweighted (PIRE) algorithm for solving a general problem, which involves a large body of nonconvex sparse and structured sparse related problems. Comparing with previous iterative solvers for nonconvex sparse problem, PIRE is much more general and efficient. The computational cost of PIRE in each iteration is usually as low as the state-of-the-art convex solvers. We further propose the PIRE algorithm with Parallel Splitting (PIRE-PS) and PIRE algorithm with Alternative Updating (PIRE-AU) to handle the multi-variable problems. In theory, we prove that our proposed methods converge and any limit solution is a stationary point. Extensive experiments on both synthesis and real data sets demonstrate that our methods achieve comparative learning performance, but are much more efficient, by comparing with previous nonconvex solvers.
Another related work is @cite_16 which aims to solve In each iteration, @math is efficiently updated by solving a series of problem But their solver is only for problem ) which is a special case of ). The convergence proofs also depend on the special property of the @math -norm, thus is not general.
@cite_16
2063761188
Many conjugate gradient-like methods for solving linear systems @math use recursion formulas for updating residual vectors instead of computing the residuals directly. For such methods it is shown that the difference between the actual residuals and the updated approximate residual vectors generated in finite precision arithmetic depends on the machine precision @math and on the maximum norm of an iterate divided by the norm of the true solution. It is often observed numerically, and can sometimes be proved, that the norms of the updated approximate residual vectors converge to zero or, at least, become orders of magnitude smaller than the machine precision. In such cases, the actual residual norm reaches the level @math times the maximum ratio of the norm of an iterate to that of the true solution. Using exact arithmetic theory to bound the size of the iterates, we give a priori estimates of the size of the final residual for a number of algorithms. We propose an approximate Newton method for solving the coupled nonlinear system @math and @math where @math , @math , @math and @math . The method involves applying the basic iteration S of a general solver for the equation @math , withtfixed. It is therefore well suited for problems for which such a solver already exists or can be implemented more efficiently than a solver for the coupled system. We derive conditions for S under which the method is locally convergent. Basically, if S is sufficiently contractive for G, then convergence for the coupled system is guaranteed. Otherwise, we show how to construct an @math from S for which convergence is assured. These results are applied to continuation methods where N represents a pseudo-arclength condition. We show that under certain conditions the algorithm converges if S is convergent for G. Numerical results are given for a two-level nonlinear multi-grid solver applied ... We propose simple and extremely efficient methods for solving the basis pursuit problem @math which is used in compressed sensing. Our methods are based on Bregman iterative regularization, and they give a very accurate solution after solving only a very small number of instances of the unconstrained problem @math for given matrix @math and vector @math . We show analytically that this iterative approach yields exact solutions in a finite number of steps and present numerical results that demonstrate that as few as two to six iterations are sufficient in most cases. Our approach is especially useful for many compressed sensing applications where matrix-vector operations involving @math and @math can be computed by fast transforms. Utilizing a fast fixed-point continuation solver that is based solely on such operations for solving the above unconstrained subproblem, we were able to quickly solve huge instances of compressed sensing problems on a standard PC. For numerical computation of the minimal Euclidean norm (least-squares) solution of overdetermined linear systems, usually direct solvers are used (like QR decomposition, see [4]). The iterative methods for such kind of problems need special assumptions about the system (consistency, full rank of the system matrix, some parameters they use or they give not the minimal length solution, [2,3,5,8,10,13]). In the present paper we purpose two iterative algorithms which generate sequences convergent to the minimal Euclidean length solution in the general case (inconsistent system and rank deficient matrix). The algorithms use only some combinations and properties of the well-known Kaczmarz iterative method ([13]) and need no special assumptions about the system.