Convex feasibility modeling and projection methods for sparse signal recovery

A computationally-efficient method for recovering sparse signals from a series of noisy observations, known as the problem of compressed sensing (CS), is presented. The theory of CS usually leads to a constrained convex minimization problem. In this work, an alternative outlook is proposed. Instead of solving the CS problem as an optimization problem, it is suggested to transform the optimization problem into a convex feasibility problem (CFP), and solve it using feasibility-seeking sequential and simultaneous subgradient projection methods, which are iterative, fast, robust and convergent schemes for solving CFPs. As opposed to some of the commonly-used CS algorithms, such as Bayesian CS and Gradient Projections for sparse reconstruction, which become inefficient as the problem dimension and sparseness degree increase, the proposed methods exhibit robustness with respect to these parameters. Moreover, it is shown that the CFP-based projection methods are superior to some of the state-of-the-art methods in recovering the signal’s support. Numerical experiments show that the CFP-based projection methods are viable for solving large-scale CS problems with compressible signals.     

Generalized Bregman Projections in Convex Feasibility Problems

We present a method for finding common points of finitely many closed convex sets in Euclidean space. The Bregman extension of the classical method of cyclic orthogonal projections employs nonorthogonal projections induced by a convex Bregman function, whereas the Bauschke and Borwein method uses Bregman/Legendre functions. Our method works with generalized Bregman functions (B-functions) and inexact projections, which are easier to compute than the exact ones employed in other methods. We also discuss subgradient algorithms with Bregman projections.     

Analytic Center Cutting-Plane Method with Deep Cuts for Semidefinite Feasibility Problems

An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that or returns a cut A S ^m {YS ^m : AY AY - } , where 0. If , an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that contains a ball with radius > 0, the algorithm obtains eventually a point in , with a worst-case complexity of O ^*(m ³/²) on the total number of cuts generated.     

A Continuous Method for Convex Programming Problems

In this paper, we present a continuous method for convex programming (CP) problems. Our approach converts first the convex problem into a monotone variational inequality (VI) problem. Then, a continuous method, which includes both a merit function and an ordinary differential equation (ODE), is introduced for the resulting variational inequality problem. The convergence of the ODE solution is proved for any starting point. There is no Lipschitz condition required in our proof. We show also that this limit point is an optimal solution for the original convex problem. Promising numerical results are presented.This research was supported in part by Grants FRG/01-02/I-39 and FRG/01-02/II-06 of Hong Kong Baptist University and Grant HKBU2059/02P from the Research Grant Council of Hong Kong.The author thanks Professor Bingsheng He for many helpful suggestions and discussions. The author is also grateful for the comments and suggestions of two anonymous referees. In particular, the author is indebted to one referee who drew his attention to References 15, 17, 18.     

Some Remarks on the Convex Feasibility Problem and Best Approximation Problem

In this paper we investigate several solution algorithms for the convex fea- sibility problem(CFP)and the best approximation problem(BAP)respectively.The algorithms analyzed are already known before,but by adequately reformulating the CFP or the BAP we naturally deduce the general projection method for the CFP from well-known steepest decent method for unconstrained optimization and we also give a natural strategy of updating weight parameters.In the linear case we show the connec- tion of the two projection algorithms for the CFP and the BAP respectively.In addition, we establish the convergence of a method for the BAP under milder assumptions in the linear case.We also show by examples a Bauschke's conjecture is only partially correct.     

Iterative Averaging of Entropic Projections for Solving Stochastic Convex Feasibility Problems

The problem considered in this paper is that of finding a point which iscommon to almost all the members of a measurable family of closed convexsubsets of R₊₊ ⁿ , provided that such a point exists.The main results show that this problem can be solved by an iterative methodessentially based on averaging at each step the Bregman projections withrespect to f(x)=_i=1 ⁿx_i· ln x_i ofthe current iterate onto the given sets.     

A New Self-Dual Embedding Method for Convex Programming

In this paper we introduce a conic optimization formulation to solve constrained convex programming, and propose a self-dual embedding model for solving the resulting conic optimization problem. The primal and dual cones in this formulation are characterized by the original constraint functions and their corresponding conjugate functions respectively. Hence they are completely symmetric. This allows for a standard primal-dual path following approach for solving the embedded problem. Moreover, there are two immediate logarithmic barrier functions for the primal and dual cones. We show that these two logarithmic barrier functions are conjugate to each other. The explicit form of the conjugate functions are in fact not required to be known in the algorithm. An advantage of the new approach is that there is no need to assume an initial feasible solution to start with. To guarantee the polynomiality of the path-following procedure, we may apply the self-concordant barrier theory of Nesterov and Nemirovski. For this purpose, as one application, we prove that the barrier functions constructed this way are indeed self-concordant when the original constraint functions are convex and quadratic. We pose as an open question to find general conditions under which the constructed barrier functions are self-concordant.     

Iterative Method for Solving the Linear Feasibility Problem

Many optimization problems reduce to the solution of a system of linear inequalities (SLI). Some solution methods use relaxed, averaged projections. Others invoke surrogate constraints (typically stemming from aggregation). This paper proposes a blend of these two approaches. A novelty comes from introducing as surrogate constraint a halfspace defined by differences of algorithmic iterates. The first iteration is identical to surrogate constraints methods. In next iterations, for a given approximation , besides the violated constraints in , we also take into consideration the surrogate inequality, which we have obtained in the previous iteration. The motivation for this research comes from the recent work of Scolnik et al. (Appl. Numer. Math. 41, 499–513, 2002), who studied some projection methods for a system of linear equations. The author thanks Professor Andrzej Cegielski for suggesting the problem and many helpful discussions during the preparation of the paper.     

修正的IPA算法的建立及在不等式约束凸优化问题中的应用

本文首先对IPA算法进行了修正，并证明了修正IPA算法的收敛性，然后将修正后的IPA应用到不等式约束凸优化问题中得到新的内点算法，并与传统的障碍函数法作了比较，从理论上体现了新算法的优势，并给出了其工程解求解法以及收敛性的证明．     

A Dynamical System Associated with Newton's Method for Parametric Approximations of Convex Minimization Problems

We study the existence and asymptotic convergence when t→+∞ for the trajectories generated by where is a parametric family of convex functions which approximates a given convex function f we want to minimize, and ε(t) is a parametrization such that ε(t)→ 0 when t→+∞ . This method is obtained from the following variational characterization of Newton's method: where H is a real Hilbert space. We find conditions on the approximating family and the parametrization to ensure the norm convergence of the solution trajectories u(t) toward a particular minimizer of f . The asymptotic estimates obtained allow us to study the rate of convergence as well. The results are illustrated through some applications to barrier and penalty methods for linear programming, and to viscosity methods for an abstract noncoercive variational problem. Comparisons with the steepest descent method are also provided. Accepted 5 December 1996     

A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints

We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising.     

Research Article: On Extending Primal-Dual Interior-Point Method for Linear Optimization to Convex Quadratic Symmetric Cone Optimization

Disjoint frames are interesting frames in Hilbert spaces, which were introduced by Han and Larson in [4 D. Han and D. R. Larson ( 2000 ). Frames, Basis and Group Representations . Memoirs of the American Mathematical Society, No. 679. AMS, Providence, RI.  [Google Scholar]]. In this article, we use disjoint frames to construct frames. In particular, we obtain some conditions for the linear combinations of frames to be frames where the coefficients in the combination may be operators. Our results generalize the corresponding results obtained by Han and Larson. Finally, we provide some examples to illustrate our constructions.     

Proximal-Like Algorithm Using the Quasi D-Function for Convex Second-Order Cone Programming

In this paper, we present a measure of distance in a second-order cone based on a class of continuously differentiable strictly convex functions on ℝ₊₊. Since the distance function has some favorable properties similar to those of the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]), we refer to it as a quasi D-function. Then, a proximal-like algorithm using the quasi D-function is proposed and applied to the second-cone programming problem, which is to minimize a closed proper convex function with general second-order cone constraints. Like the proximal point algorithm using the D-function (Censor and Zenios in J. Optim. Theory Appl. 73:451–464 [1992]; Chen and Teboulle in SIAM J. Optim. 3:538–543 [1993]), under some mild assumptions we establish the global convergence of the algorithm expressed in terms of function values; we show that the sequence generated by the proposed algorithm is bounded and that every accumulation point is a solution to the considered problem. Research of Shaohua Pan was partially supported by the Doctoral Starting-up Foundation (B13B6050640) of GuangDong Province. Jein-Shan Chen is a member of the Mathematics Division, National Center for Theoretical Sciences, Taipei Office. The author’s work was partially supported by National Science Council of Taiwan.     

凸可行问题的一种强收敛算法

无限维Hilbert空间中,解凸可行问题的平行投影算法通常是弱收敛的.本文对一般的平行投影算法进行改进,设计了一种解凸可行问题的具有强收敛性的新算法.该算法主要是在原有算法基础上引入了一个参数序列,在参数序列满足一定的控制条件下保证了算法的强收敛性.为了简单证明算法的强收敛性,我们构建了一个新的积空间,然后把原空间的这种改进平行投影算法转换为积空间中的交替投影算法.这样,改进的平行投影算法的强收敛性就可以通过交替投影算法的收敛性证明得到.     

How good are projection methods for convex feasibility problems?

We consider simple projection methods for solving convex feasibility problems. Both successive and sequential methods are considered, and heuristics to improve these are suggested. Unfortunately, particularly given the large literature which might make one think otherwise, numerical tests indicate that in general none of the variants considered are especially effective or competitive with more sophisticated alternatives. Electronic Supplementary Material The online version of this article () contains supplementary material, which is available to authorized users. This work was supported by the EPSRC grant GR/S42170.     

An Accelerated Iterative Method with Diagonally Scaled Oblique Projections for Solving Linear Feasibility Problems

The Projected Aggregation Methods (PAM) for solving linear systems of equalities and/or inequalities, generate a new iterate x ^k+1 by projecting the current point x ^k onto a separating hyperplane generated by a given linear combination of the original hyperplanes or halfspaces. In Scolnik et al. (2001, 2002a) and Echebest et al. (2004) acceleration schemes for solving systems of linear equations and inequalities respectively were introduced, within a PAM like framework. In this paper we apply those schemes in an algorithm based on oblique projections reflecting the sparsity of the matrix of the linear system to be solved. We present the corresponding theoretical convergence results which are a generalization of those given in Echebest et al. (2004). We also present the numerical results obtained applying the new scheme to two algorithms introduced by Garcí a-Palomares and González-Castaño (1998) and also the comparison of its efficiency with that of Censor and Elfving (2002).     

Optimization for Inconsistent Split Feasibility Problems

The split feasibility problem deals with finding a point in a closed convex subset of the domain space of a linear operator such that the image of the point under the linear operator is in a prescribed closed convex subset of the image space. The split feasibility problem and its variants and generalizations have been widely investigated as a means for resolving practical inverse problems in various disciplines. Many iterative algorithms have been proposed for solving the problem. This article discusses a split feasibility problem which does not have a solution, referred to as an inconsistent split feasibility problem. When the closed convex set of the domain space is the absolute set and the closed convex set of the image space is the subsidiary set, it would be reasonable to formulate a compromise solution of the inconsistent split feasibility problem by using a point in the absolute set such that its image of the linear operator is closest to the subsidiary set in terms of the norm. We show that the problem of finding the compromise solution can be expressed as a convex minimization problem over the fixed point set of a nonexpansive mapping and propose an iterative algorithm, with three-term conjugate gradient directions, for solving the minimization problem.     

Iterative Methods of Solving Stochastic Convex Feasibility Problems and Applications

The stochastic convex feasibility problem (SCFP) is the problem of finding almost common points of measurable families of closed convex subsets in reflexive and separable Banach spaces. In this paper we prove convergence criteria for two iterative algorithms devised to solve SCFPs. To do that, we first analyze the concepts of Bregman projection and Bregman function with emphasis on the properties of their local moduli of convexity. The areas of applicability of the algorithms we present include optimization problems, linear operator equations, inverse problems, etc., which can be represented as SCFPs and solved as such. Examples showing how these algorithms can be implemented are also given.     

Hybrid Conjugate Gradient Method for a Convex Optimization Problem over the Fixed-Point Set of a Nonexpansive Mapping

The main aim of the paper is to accelerate the existing method for a convex optimization problem over the fixed-point set of a nonexpansive mapping. To achieve this goal, we present an algorithm (Algorithm 3.1) by using the conjugate gradient direction. We present also a convergence analysis (Theorem 3.1) under some assumptions. Finally, to demonstrate the effectiveness and performance of the proposed method, we present numerical comparisons of the existing method with the proposed method.     

Extrapolated cyclic subgradient projection methods for the convex feasibility problems and their numerical behaviour

ABSTRACT

We present two versions of the extrapolated cyclic subgradient projections method for solving the convex feasibility problem. Moreover, we present the results of numerical tests, where we compare the methods with the classical cyclic subgradient projections method.