Search

Abstract With the appearance of approach named "robust alignment by sparse and low-rank decomposition" (RASL), a number of linearly correlated images can be accurately and robustly aligned despite significant corruptions and occlusions. It has been discovered that this aligning task can be characterized as a sequence of 3-block convex minimization problems which can be solved efficiently by the accelerated proximal gradient method (APG), or alternatively, by the directly extended alternating direction method of multipliers (ADMM). However, the directly extended ADMM may diverge although it often performs well in numerical computations. Ideally, one should find an algorithm which can have both theoretical guarantee and superior numerical efficiency over the directly extended ADMM. We achieve this goal by using the intelligent symmetric Gauss–Seidel iteration based ADMM (sGS-ADMM) which only needs to update one of the variables twice, but surprisingly, it leads to the desired convergence to be guaranteed. The convergence of sGS-ADMM can be followed directly by relating it to the classical 2-block ADMM and with a couple of specially designed semi-proximal terms. Beyond this, we also add a rank-correction term to the model with the purpose of deriving the alignment results with higher accuracy. The numerical experiments over a wide range of realistic misalignments demonstrate that sGS-ADMM is at least two times faster than RASL and APG for the vast majority of the tested problems. [ABSTRACT FROM AUTHOR]

The recent designed non-linear conjugate gradient method of Dai and Kou [SIAM J Optim. 2013;23:296–320] is very efficient currently in solving large-scale unconstrained minimization problems due to its simpler iterative form, lower storage requirement and its closeness to the scaled memoryless BFGS method. Just because of these attractive properties, this method was extended successfully to solve higher dimensional symmetric non-linear equations in recent years. Nevertheless, its numerical performance in solving convex constrained monotone equations has never been explored. In this paper, combining with the projection method of Solodov and Svaiter, we develop a family of non-linear conjugate gradient methods for convex constrained monotone equations. The proposed methods do not require the Jacobian information of equations, and even they do not store any matrix in each iteration. They are potential to solve non-smooth problems with higher dimensions. We prove the global convergence of the class of the proposed methods and establish its R-linear convergence rate under some reasonable conditions. Finally, we also do some numerical experiments to show that the proposed methods are efficient and promising. [ABSTRACT FROM AUTHOR]

• A computational binary characterization method for convex object(s). • A unified model for convex object(s) segmentation and convex hull computation. • Linearization technique employed to reduce the difficulty of the model solving. • A convergent proximal alternating direction method of multipliers for the linearization problem. • An interactive procedure to improve the segmentation accurac y in terms of shape distance and D ice coefficient. Convexity prior is one of the main cues for human vision and shape completion with important applications in image processing and computer vision. This paper provides a computable characterization method for shape convexity, and illustrates its applications in image segmentation and convex hull computation. We prove that the convexity of a region is equivalent to a series of quadratic inequality constraints on its indicator function. By incorporating this result, models are proposed for image segmentation with convexity prior and convex hull computation of clean and noisy data sets, respectively. Then, these models are summarized into a unified optimization problem on binary function(s) with the quadratic inequality constraints. Numerical method is proposed by linearizing the quadratic constraints. The linearization problem is solved by a proximal alternating direction method of multipliers, the convergence of which is guaranteed under some proper conditions. Numerical experiments demonstrate the efficiency and effectiveness of the proposed methods for image segmentation and convex hull computation. [ABSTRACT FROM AUTHOR]

The main purpose of this study is to propose, then analyze, and later test a spectral gradient algorithm for solving a convex minimization problem. The considered problem covers the matrix ℓ2,1-norm regularized least squares which is widely used in multi-task learning for capturing the joint feature among each task. To solve the problem, we firstly minimize a quadratic approximated model of the objective function to derive a search direction at current iteration. We show that this direction descends automatically and reduces to the original spectral gradient direction if the regularized term is removed. Secondly, we incorporate a nonmonotone line search along this direction to improve the algorithm’s numerical performance. Furthermore, we show that the proposed algorithm converges to a critical point under some mild conditions. The attractive feature of the proposed algorithm is that it is easily performable and only requires the gradient of the smooth function and the objective function’s values at each and every step. Finally, we operate some experiments on synthetic data, which verifies that the proposed algorithm works quite well and performs better than the compared ones. [ABSTRACT FROM AUTHOR]

CG_DESCENT is a state-of-the-art algorithm to solve large-scale unconstrained minimization problems. However, research activities on CG_DESCENT in some other scenarios are relatively fewer. In this paper, by combining with the projection method of Solodov and Svaiter, we extend CG_DESCENT to solve large-scale nonlinear convex constrained monotone equations. The proposed method does not require the Jacobian information, even though it does not store any matrix at each iteration. It thus has the potential to solve large-scale non-smooth problems. Under some mild conditions, we show that the proposed method converges globally. Primary numerical results illustrate that the proposed method works quite well. Moreover, we also extend this method to solve the -norm regularized problems to decode a sparse signal in compressive sensing. Performance comparisons show that the proposed method is practical, efficient and competitive with the compared ones. [ABSTRACT FROM AUTHOR]

Abstract: Finding sparse solutions to under-determined linear systems of equations have intensively involved in fields of machine learning, signal processing, compressive sensing, linear inverse problems and statistical inference. Generally, the task can be realized by solving -norm regularized minimization problems. However, the resulting problem is challenging due to the non-smoothness of the regularization term. Inspired by Nesterov’s smoothing technique, this paper proposes, analyzes and tests a modified Polak–Ribière–Polyak conjugate gradient method to solve large-scale -norm least squares problem for sparse signal recovery. The per-iteration cost of the proposed algorithm is dominated by three matrix–vector multiplications and the global convergence is guaranteed by results in optimization literature. Moreover, the algorithm is also accelerated by continuation loops as usual. The limited experiments show that this continuation technique benefits to its performance. Numerical experiments which decode a sparse signal from its limited measurements illustrate that the proposed algorithm performs better than NESTA—a recently developed code with Nesterov’s smoothing technique and gradient algorithm. [Copyright &y& Elsevier]

Given a set of corrupted data drawn from a union of multiple subspace, the subspace recovery problem is to segment the data into their respective subspace and to correct the possible noise simultaneously. Recently, it is discovered that the task can be characterized, both theoretically and numerically, by solving a matrix nuclear-norm and a ℓ-mixed norm involved convex minimization problems. The minimization model actually has separable structure in both the objective function and constraint; it thus falls into the framework of the augmented Lagrangian alternating direction approach. In this paper, we propose and investigate an augmented Lagrangian algorithm. We split the augmented Lagrangian function and minimize the subproblems alternatively with one variable by fixing the other one. Moreover, we linearize the subproblem and add a proximal point term to easily derive the closed-form solutions. Global convergence of the proposed algorithm is established under some technical conditions. Extensive experiments on the simulated and the real data verify that the proposed method is very effective and faster than the sate-of-the-art algorithm LRR. [ABSTRACT FROM AUTHOR]

For solving large-scale unconstrained minimization problems, the nonlinear conjugate gradient method is welcome due to its simplicity, low storage, efficiency and nice convergence properties. Among all the methods in the framework, the conjugate gradient descent algorithm — CG_DESCENT is very popular, in which the generated directions descend automatically, and this nice property is independent of any line search used. In this paper, we generalize CG_DESCENT with two Barzilai–Borwein steplength reused cyclically. We show that the resulting algorithm owns attractive sufficient descent property and converges globally under some mild conditions. We test the proposed algorithm by using a large set of unconstrained problems with high dimensions in CUTEr library. The numerical comparisons with the state-of-the-art algorithm CG_DESCENT illustrate that the proposed method is effective, competitive, and promising. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose, analyze, and test a new method for solving -norm regularization problems arising from the spare solution recovery in compressed sensing, basis-pursuit problems, and linear inverse problems. The method aims to minimize a non-smooth minimization problem consisting of a least-squares data fitting term and a -norm regularization term. The problem is firstly formulated for a convex quadratic program problem, and then for an equivalent non-smooth equation. At each iteration, a spectral gradient method is applied to the resulting problem without requiring Jacobian matrix information. Convergence of the proposed method follows directly from the results which already exist. The algorithm is easily performed, where only the matrix–vector inner product is required at each and every step. Numerical experiments to decode a sparse signal arising in compressed sensing and image deconvolution are performed. The numerical results illustrate that the proposed method is practical and promising. [Copyright &y& Elsevier]

Abstract: In this paper, we give some notes on the two modified spectral gradient methods which were developed in . These notes present the relationship between their stepsize formulae and some new secant equations in the quasi-Newton method. In particular, we also introduce another two new choices of stepsize. By using an efficient nonmonotone line search technique, we propose some new spectral gradient methods. Under some mild conditions, we show that these proposed methods are globally convergent. Numerical experiments on a large number of test problems from the CUTEr library are also reported, which show that the efficiency of these proposed methods. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a modified BFGS (Broyden–Fletcher–Goldfarb–Shanno) method with nonmonotone line search for unconstrained optimization. Under some mild conditions, we show that the method is globally convergent without a convexity assumption on the objective function. We also report some preliminary numerical results to show the efficiency of the proposed method. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a family of derivative-free conjugate gradient methods for large-scale nonlinear systems of equations. They come from two modified conjugate gradient methods [W.Y. Cheng, A two term PRP based descent Method, Numer. Funct. Anal. Optim. 28 (2007) 1217–1230; L. Zhang, W.J. Zhou, D.H. Li, A descent modified Polak–Ribiére–Polyak conjugate gradient method and its global convergence, IMA J. Numer. Anal. 26 (2006) 629–640] recently proposed for unconstrained optimization problems. Under appropriate conditions, the global convergence of the proposed method is established. Preliminary numerical results show that the proposed method is promising. [Copyright &y& Elsevier]

Abstract: In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm. [Copyright &y& Elsevier]

Abstract: In this paper, a new numerical method for solving large-scale unconstrained optimization problems is presented. It is derived from a modified BFGS-type update formula by Wei, Li, and Qi. It is observed that the update formula can be extended to the framework of limited memory scheme with hardly more storage or arithmetic operations. Under some suitable conditions, the global convergence property is established. The implementations of the method on a set of CUTE problems indicate that this extension is beneficial to the performance of the algorithm. [Copyright &y& Elsevier]

Abstract: An active set limited memory BFGS algorithm for large-scale bound constrained optimization is introduced. The active sets are based on guessing technique to be identified at each iteration, the search direction in free subspace is determined by limited memory BFGS (L-BFGS) algorithm, which provides an efficient means for attacking large-scale optimization problems. The implementations of the method on CUTE test problems are described. [Copyright &y& Elsevier]

eLoom is an open source graph simulation software tool, developed at the University of New Mexico (UNM), that enables users to specify and simulate neural network models. Its specification language and libraries enables users to construct and simulate arbitrary, potentially hierarchical network structures on serial and parallel processing systems. In addition, eLoom is integrated with UNM''s Flatland, an open source virtual environments development tool to provide real-time visualizations of the network structure and activity. Visualization is a useful method for understanding both learning and computation in artificial neural networks. Through 3D animated pictorially representations of the state and flow of information in the network, a better understanding of network functionality is achieved. ART-1, LAPART-II, MLP, and SOM neural networks are presented to illustrate eLoom and Flatland''s capabilities. [Copyright &y& Elsevier]

We know that compressive sensing can establish stable sparse recovery results from highly undersampled data under a restricted isometry property condition. In reality, however, numerous problems are coherent, and vast majority conventional methods might work not so well. Recently, it was shown that using the difference between ℓ 1 - and ℓ 2 -norm as a regularization always has superior performance. In this paper, we consider an adaptive ℓ p - ℓ 1 − 2 model where the ℓ p -norm with p ≥ 1 measures the data fidelity and the ℓ 1 − 2 -term measures the sparsity. This proposed model has the ability to deal with different types of noises and extract the sparse property even under high coherent condition. We use a proximal majorization-minimization technique to handle the non-convex regularization term and then employ a semismooth Newton method to solve the corresponding convex relaxation subproblem. We prove that the sequence generated by the semismooth Newton method admits fast local convergence rate to the subproblem under some technical assumptions. Finally, we do some numerical experiments to demonstrate the superiority of the proposed model and the progressiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The rank minimization problem with affine constraints is widely applied in the fields of control, system identification, and machine learning, and attracted much attention and well studied in the past few years. Unlike most of the existing methods where a nuclear norm is used to approximate the rank term, in this paper, we apply the penalty decomposition method to solve the rank minimization problem directly. One subproblem can be solved effectively by using linear conjugate gradient method, and the other one has closed-form solutions by taking full use of the problem’s favorable structure. Under some suitable assumptions, the convergence results for the proposed method are given. Finally, we do numerical experiments on randomly generated and real data, the results show that the proposed method is effective and promising. [ABSTRACT FROM AUTHOR]

Abstract: A spectral gradient projection algorithm for monotone nonlinear equations with convex constraints is proposed. This new procedure is obtained by combining a modified spectral gradient method and a projection method. A relevant property of the presented method is that the computation of the iteration sequence does not require the solution of any subproblem. The algorithm is shown to be globally convergent under mild assumptions and it can be also applied to nonsmooth equations. Preliminary numerical tests show that the proposed method works quite well even for large scale problems. [Copyright &y& Elsevier]