Nonlinear interpolation and norm minimization

We prove that the set of convolution-type functions in _d that satisfy the interpolation conditions contains a unique function whose convolution element has the minimumL _p -norm. The extremal function is determined by solving a nonlinear interpolation problem. The results are applied to an operator recovery problem.Translated fromMatematicheskie Zametki, Vol. 58, No. 4, pp. 512–524, October, 1995.     

Proximal minimization algorithm withD-functions

The original proximal minimization algorithm employs quadratic additive terms in the objectives of the subproblems. In this paper, we replace these quadratic additive terms by more generalD-functions which resemble (but are not strictly) distance functions. We characterize the properties of suchD-functions which, when used in the proximal minimization algorithm, preserve its overall convergence. The quadratic case as well as an entropy-oriented proximal minimization algorithm are obtained as special cases.The work of the first author was supported by NSF Grant CCR-8811135 and NIH Grant HL-28438, while visiting the Decision Sciences Department of the Wharton School and the Medical Image Processing Group at the Department of Radiology, both at the University of Pennsylvania, Philadelphia, Pennsylvania. The work of the second author was supported by NSF Grant CCR-91-04042 and AFOSR Grant 91-0168.The authors received valuable comments on the December 1989 and June 1990 versions of this paper, which led to considerable improvements of the results and their presentation. For this, they are indebted to D. Bertsekas, A. De Pierro, J. Eckstein, P. Eggermont, A. Iusem, M. Ferris, M. Teboulle, and three anonymous referees.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

Low-rank matrix completion using nuclear norm minimization and facial reduction

We consider a global optimization problem for Lipschitz-continuous functions with an unknown Lipschitz constant. Our approach is based on the well-known DIRECT (DIviding RECTangles) algorithm and motivated by the diagonal partitioning strategy. One of the main advantages of the diagonal partitioning scheme is that the objective function is evaluated at two points at each hyper-rectangle and, therefore, more comprehensive information about the objective function is considered than using the central sampling strategy used in most DIRECT-type algorithms. In this paper, we introduce a new DIRECT-type algorithm, which we call BIRECT (BIsecting RECTangles). In this algorithm, a bisection is used instead of a trisection which is typical for diagonal-based and DIRECT-type algorithms. The bisection is preferable to the trisection because of the shapes of hyper-rectangles, but usual evaluation of the objective function at the center or at the endpoints of the diagonal are not favorable for bisection. In the proposed algorithm the objective function is evaluated at two points on the diagonal equidistant between themselves and the endpoints of a diagonal. This sampling strategy enables reuse of the sampling points in descendant hyper-rectangles. The developed algorithm gives very competitive numerical results compared to the DIRECT algorithm and its well know modifications.     

Nuclear norm minimization for the planted clique and biclique problems

We consider the problems of finding a maximum clique in a graph and finding a maximum-edge biclique in a bipartite graph. Both problems are NP-hard. We write both problems as matrix-rank minimization and then relax them using the nuclear norm. This technique, which may be regarded as a generalization of compressive sensing, has recently been shown to be an effective way to solve rank optimization problems. In the special case that the input graph has a planted clique or biclique (i.e., a single large clique or biclique plus diversionary edges), our algorithm successfully provides an exact solution to the original instance. For each problem, we provide two analyses of when our algorithm succeeds. In the first analysis, the diversionary edges are placed by an adversary. In the second, they are placed at random. In the case of random edges for the planted clique problem, we obtain the same bound as Alon, Krivelevich and Sudakov as well as Feige and Krauthgamer, but we use different techniques.     

Stable recovery of low rank matrices from nuclear norm minimization

Low rank matrix recovery is a new topic drawing the attention of many researchers which addresses the problem of recovering an unknown low rank matrix from few linear measurements. The matrix Dantzig selector and the matrix Lasso are two important algorithms based on nuclear norm minimization. In this paper,we first prove some decay properties of restricted isometry constants, then we discuss the recovery errors of these two algorithms and give a new bound of restricted isometry constant to guarantee stable recovery, which improves the results of [11].     

Nonmonotone algorithm for minimization on closed sets with applications to minimization on Stiefel manifolds

A nonmonotone Levenberg–Marquardt-based algorithm is proposed for minimization problems on closed domains. By preserving the feasible set’s geometry throughout the process, the method generates a feasible sequence converging to a stationary point independently of the initial guess. As an application, a specific algorithm is derived for minimization on Stiefel manifolds and numerical results involving a weighted orthogonal Procrustes problem are reported.     

An effective algorithm for minimization

An algorithm is proposed for minimizing certain niceC ² functionsf onE _n assuming only a computational knowledge off andf. It is shown that the algorithm provides global convergence at a rate which is eventually superlinear and possibly quadratic. The algorithm is purely algebraic and does not require the minimization of any functions of one variable.Numerical computation on specific problems with as many as six independent variables has shown that the method compares very favorably with the best of the other known methods. The method is compared with theFletcher andPowell method for a simple two dimensional test problem and for a six dimensional problem arising in control theory.Supported by Air Force grant AF-AFO SR-93 7-65 and Boeing Scientific Research Laboratories.     

A minimization algorithm for equilibrium problems with polyhedral constraints

Our aim in this paper is to study an infeasible interior proximal method for solving equilibrium problems with polyhedral constrains in a quasiconvex setting. Under mild assumptions, we show that the sequence generated by our algorithm is well defined and it converges to a solution of the problem when regularization parameters converge to zero.     

A variance algorithm for constrained minimization with linear constraints

This paper presents a quadratically convergent, rank one, variance algorithm for constrained minimization with linear constraints. The algorithm does not require a linear search for a local minimum in every iteration. Linear searches are made only when needed for stability and convergence.     

A multi-start global minimization algorithm with dynamic search trajectories

A new multi-start algorithm for global unconstrained minimization is presented in which the search trajectories are derived from the equation of motion of a particle in a conservative force field, where the function to be minimized represents the potential energy. The trajectories are modified to increase the probability of convergence to a comparatively low local minimum, thus increasing the region of convergence of the global minimum. A Bayesian argument is adopted by which, under mild assumptions, the confidence level that the global minimum has been attained may be computed. When applied to standard and other test functions, the algorithm never failed to yield the global minimum.The first author wishes to thank Prof. M. Levitt of the Department of Chemical Physics of the Weizmann Institute of Science for suggesting this line of research and also Drs. T. B. Scheffler and E. A. Evangelidis for fruitful discussions regarding Conjecture 2.1. He also acknowledges the exchange agreement award received from the National Council for Research and Development in Israel and the Council for Scientific and Industrial Research in South Africa, which made possible the visit to the Weizmann Institute where this work was initiated.     

A new subdivision for computing fixed points with a homotopy algorithm

In this paper a triangulation is introduced for homotopy methods to compute fixed points on the unit simplex or inR ⁿ . This triangulation allows for factors of incrementation of more than two. The factor may be of any size and even different at each level. Also the starting point on a new level may be any gridpoint of the last found completely labelled subsimplex on the last level. So, the decision which new factor of incrementation and which starting point is used, can be made on the ground of previous approximations. Doing so, the convergence rate can be accelerated without using restart methods.     

Alternating direction and Taylor expansion minimization algorithms for unconstrained nuclear norm optimization

Numerical Algorithms - In the past decade, robust principal component analysis (RPCA) and low-rank matrix completion (LRMC), as two very important optimization problems with the view of recovering...     

A new piecewise quadratic approximation approach for L0 norm minimization problem

In this paper, we consider the problem of finding sparse solutions for underdetermined systems of linear equations, which can be formulated as a class of L_0 norm minimization problem. By using the least absolute residual approximation, we propose a new piecewis, quadratic function to approximate the L_0 norm.Then, we develop a piecewise quadratic approximation(PQA) model where the objective function is given by the summation of a smooth non-convex component and a non-smooth convex component. To solve the(PQA) model,we present an algorithm based on the idea of the iterative thresholding algorithm and derive the convergence and the convergence rate. Finally, we carry out a series of numerical experiments to demonstrate the performance of the proposed algorithm for(PQA). We also conduct a phase diagram analysis to further show the superiority of(PQA) over L_1 and L_(1/2) regularizations.     

A combined conjugate-gradient quasi-Newton minimization algorithm

Although quasi-Newton algorithms generally converge in fewer iterations than conjugate gradient algorithms, they have the disadvantage of requiring substantially more storage. An algorithm will be described which uses an intermediate (and variable) amount of storage and which demonstrates convergence which is also intermediate, that is, generally better than that observed for conjugate gradient algorithms but not so good as in a quasi-Newton approach. The new algorithm uses a strategy of generating a form of conjugate gradient search direction for most iterations, but it periodically uses a quasi-Newton step to improve the convergence. Some theoretical background for a new algorithm has been presented in an earlier paper; here we examine properties of the new algorithm and its implementation. We also present the results of some computational experience.This research was supported by the National Research Council of Canada grant number A-8962.     

Decomposition algorithm for convex differentiable minimization

In this paper, we propose a decomposition algorithm for convex differentiable minimization. This algorithm at each iteration solves a variational inequality problem obtained by adding to the gradient of the cost function a strongly proximal related function. A line search is then performed in the direction of the solution to this variational inequality (with respect to the original cost). If the constraint set is a Cartesian product ofm sets, the variational inequality decomposes intom coupled variational inequalities, which can be solved in either a Jacobi manner or a Gauss-Seidel manner. This algorithm also applies to the minimization of a strongly convex (possibly nondifferentiable) cost subject to linear constraints. As special cases, we obtain the GP-SOR algorithm of Mangasarian and De Leone, a diagonalization algorithm of Feijoo and Meyer, the coordinate descent method, and the dual gradient method. This algorithm is also closely related to a splitting algorithm of Gabay and a gradient projection algorithm of Goldstein and of Levitin-Poljak, and has interesting applications to separable convex programming and to solving traffic assignment problems.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058. The author thanks the referees for their many helpful comments, particularly for suggesting the use of a general functionH instead of that given by (4).     

Computational complexity of a piecewise linear homotopy algorithm

We give a bound on the number of steps required by the piecewise linear algorithm based on component wise homotopy (proposed by the author for structured problems) when solving a linear problem. When the coefficient matrix is symmetric and positive definite, this bound is polynomial inn and linear in the condition number of the matrix. We also investigate the expected value of the bound for a particular distribution of such matrices. This research has been partially supported by the grant MCS 80-05154 from the National Science Foundation.     

A homotopy algorithm for a symmetric generalized eigenproblem

In this paper, a homotopy algorithm for finding all eigenpairs of a real symmetric matrix pencil (A, B) is presented, whereA andB are realn×n symmetric matrices andB is a positive semidefinite matrix. In the algorithm, pencil (A, B) is first reduced to a pencil , where is a symmetric tridiagonal matrix and is a positive definite and diagonal matrix. Then, the Divide and Conquer strategy with homotopy continuation approach is used to find all eigenpairs of pencil . One can easily form the eigenpair (x,) of pencil (A, B) from the eigenpair (y, ) of pencil with a few computations. Numerical comparisons of our algorithm with the QZ algorithm in the widely used EISPACK library are presented. Numerical results show that our algorithm is strongly competitive in terms of speed, accuracy and orthogonality. The performance of the parallel version of our algorithm is also presented.Research supported in part by NSF under Grant CCR-9024840.     

An alternating direction method for linear‐constrained matrix nuclear norm minimization

The aim of the nuclear norm minimization problem is to find a matrix that minimizes the sum of its singular values and satisfies some constraints simultaneously. Such a problem has received more attention largely because it is closely related to the affine rank minimization problem, which appears in many control applications including controller design, realization theory, and model reduction. In this paper, we first propose an exact version alternating direction method for solving the nuclear norm minimization problem with linear equality constraints. At each iteration, the method involves a singular value thresholding and linear matrix equations which are solved exactly. Convergence of the proposed algorithm is followed directly. To broaden the capacity of solving larger problems, we solve approximately the subproblem by an iterative method with the Barzilai–Borwein steplength. Some extensions to the noisy problems and nuclear norm regularized least‐square problems are also discussed. Numerical experiments and comparisons with the state‐of‐the‐art method FPCA show that the proposed method is effective and promising. Copyright © 2011 John Wiley & Sons, Ltd.