Search

Passive radar systems can detect and track the moving targets of interest by exploiting non-cooperative illuminators-of-opportunity to transmit orthogonal frequency division multiplexing (OFDM) signals. These targets are searched using a bank of correlators tuned to the waveform corresponding to the given Doppler frequency shift and delay. In this paper, we study the problem of joint delay-Doppler estimation of moving targets in OFDM passive radar. This task of estimation is described as an atomic-norm regularized convex optimization problem, or equivalently, a semi-definite programming problem. The alternating direction method of multipliers (ADMM) can be employed which computes each variable in a Gauss-Seidel manner, but its convergence is lack of certificate. In this paper, we use a symmetric Gauss-Seidel (sGS) to the framework of ADMM, which only needs to compute some of the subproblems twice but has the ability to ensure convergence. We do some simulated experiments which illustrate that the sGS-ADMM is superior to ADMM in terms of accuracy and computing time.

For some special data in reality, such as the genetic data, adjacent genes may have the similar function. Thus ensuring the smoothness between adjacent genes is highly necessary. But, in this case, the standard lasso penalty just doesn't seem appropriate anymore. On the other hand, in high-dimensional statistics, some datasets are easily contaminated by outliers or contain variables with heavy-tailed distributions, which makes many conventional methods inadequate. To address both issues, in this paper, we propose an adaptive Huber regression for robust estimation and inference, in which, the fused lasso penalty is used to encourage the sparsity of the coefficients as well as the sparsity of their differences, i.e., local constancy of the coefficient profile. Theoretically, we establish its nonasymptotic estimation error bounds under $\ell_2$-norm in high-dimensional setting. The proposed estimation method is formulated as a convex, nonsmooth and separable optimization problem, hence, the alternating direction method of multipliers can be employed. In the end, we perform on simulation studies and real cancer data studies, which illustrate that the proposed estimation method is more robust and predictive.

The proximal generalized alternating direction method of multipliers (p-GADMM) is substantially efficient for solving convex composite programming problems of high-dimensional to moderate accuracy. The global convergence of this method was established by Xiao, Chen & Li [Math. Program. Comput., 2018], but its convergence rate was not given. One may take it for granted that the convergence rate could be proved easily by mimicking the proximal ADMM, but we find the relaxed points will certainly cause many difficulties for theoretical analysis. In this paper, we devote to exploring its convergence behavior and show that the sequence generated by p-GADMM possesses Q-linear convergence rate under some mild conditions. We would like to note that the proximal terms at the subproblems are required to be positive definite, which is very common in most practical implementations although it seems to be a bit strong., Comment: 12pages

Over the fast few years, the numerical success of the generalized alternating direction method of multipliers (GADMM) proposed by Eckstein \& Bertsekas [Math. Prog., 1992] has inspired intensive attention in analyzing its theoretical convergence properties. In this paper, we devote to establishing the linear convergence rate of the semi-proximal GADMM (sPGADMM) for solving linearly constrained convex composite optimization problems. The semi-proximal terms contained in each subproblem possess the abilities of handling with multi-block problems efficiently. We initially present some important inequalities for the sequence generated by the sPGADMM, and then establish the local linear convergence rate under the assumption of calmness. As a by-product, the global convergence property is also discussed.

The generalized alternating direction method of multipliers (ADMM) of Xiao et al. [{\tt Math. Prog. Comput., 2018}] aims at the two-block linearly constrained composite convex programming problem, in which each block is in the form of "nonsmooth + quadratic". However, in the case of non-quadratic (but smooth), this method may fail unless the favorable structure of 'nonsmooth + smooth' is no longer used. This paper aims to remedy this defect by using a majorized technique to approximate the augmented Lagrangian function, so that the corresponding subprobllem can be decomposed into some smaller problems and then solved separately. Furthermore, the recent symmetric Gauss-Seidel (sGS) decomposition theorem guarantees the equivalence between the bigger subproblem and these smaller ones. This paper focuses on convergence analysis, that is, we prove that the sequence generated by the proposed method converges globally to a Karush-Kuhn-Tucker point of the considered problem. Finally, we do some numerical experiments on a kind of simulated convex composite optimization problems which illustrate that the proposed method is more efficient than its compared ones., Comment: 19 pages

Convexity prior is one of the main cue for human vision and shape completion with important applications in image processing, computer vision. This paper focuses on characterization methods for convex objects and applications in image processing. We present a new method for convex objects representations using binary functions, that is, the convexity of a region is equivalent to a simple quadratic inequality constraint on its indicator function. Models are proposed firstly by incorporating this result for image segmentation with convexity prior and convex hull computation of a given set with and without noises. Then, these models are summarized to a general optimization problem on binary function(s) with the quadratic inequality. Numerical algorithm is proposed based on linearization technique, where the linearized problem is solved by a proximal alternating direction method of multipliers with guaranteed convergent. Numerical experiments demonstrate the efficiency and effectiveness of the proposed methods for image segmentation and convex hull computation in accuracy and computing time.

The linearly constrained convex composite programming problems whose objective function contains two blocks with each block being the form of nonsmooth+smooth arises frequently in multiple fields of applications. If both of the smooth terms are quadratic, this problem can be solved efficiently by using the symmetric Gaussian-Seidel (sGS) technique based proximal alternating direction method of multipliers (ADMM). However, in the non-quadratic case, the sGS technique can not be used any more, which leads to the separable structure of nonsmooth+smooth had to be ignored. In this paper, we present a generalized ADMM and particularly use a majorization technique to make the corresponding subproblems more amenable to efficient computations. Under some appropriate conditions, we prove its global convergence for the relaxation factor in $(0,2)$. We apply the algorithm to solve a kind of simulated convex composite optimization problems and a type of sparse inverse covariance matrix estimation problems which illustrates that the effectiveness of the algorithm are obvious.

Magnetic Resonance Imaging (MRI) is a kind of medical imaging technology used for diagnostic imaging of diseases, but its image quality may be suffered by the long acquisition time. The compressive sensing (CS) based strategy may decrease the reconstruction time greatly, but it needs efficient reconstruction algorithms to produce high-quality and reliable images. This paper focuses on the algorithmic improvement for the sparse reconstruction of CS-MRI, especially considering a non-smooth convex minimization problem which is composed of the sum of a total variation regularization term and a $\ell_1$-norm term of the wavelet transformation. The partly motivation of targeting the dual problem is that the dual variables are involved in relatively low-dimensional subspace. Instead of solving the primal model as usual, we turn our attention to its associated dual model composed of three variable blocks and two separable non-smooth function blocks. However, the directly extended alternating direction method of multipliers (ADMM) must be avoided because it may be divergent, although it usually performs well numerically. In order to solve the problem, we employ a symmetric Gauss-Seidel (sGS) technique based ADMM. Compared with the directly extended ADMM, this method only needs one additional iteration, but its convergence can be guaranteed theoretically. Besides, we also propose a generalized variant of ADMM because this method has been illustrated to be efficient for solving semidefinite programming in the past few years. Finally, we do extensive experiments on MRI reconstruction using some simulated and real MRI images under different sampling patterns and ratios. The numerical results demonstrate that the proposed algorithms significantly achieve high reconstruction accuracies with fast computational speed.

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 $\ell_1$- and $\ell_2$-norm as a regularization always has superior performance. In this paper, we propose an adaptive $\ell_p$-$\ell_{1-2}$ model where the $\ell_p$-norm with $p\geq 1$ measures the data fidelity and the $\ell_{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 nonconvex 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.

This paper is concerned with a partially linear semiparametric regression model containing an unknown regression coefficient, an unknown nonparametric function, and an unobservable Gaussian distributed random error. We focus on the case of simultaneous variable selection and estimation with a divergent number of covariates under the assumption that the regression coefficient is sparse. We consider the applications of the least squares to semiparametric regression and particularly present an adaptive lasso penalized least squares (PLS) method to select the regression coefficient. We note that there are many algorithms for PLS in various applications, but they seem to be rarely used in semiparametric regression. This paper focuses on using a semismooth Newton augmented Lagrangian (SSNAL) algorithm to solve the dual of PLS which is the sum of a smooth strongly convex function and an indicator function. At each iteration, there must be a strongly semismooth nonlinear system, which can be solved by semismooth Newton by making full use of the penalized term. We show that the algorithm offers a significant computational advantage, and the semismooth Newton method admits fast local convergence rate. Numerical experiments on some simulation data and real data to demonstrate that the PLS is effective and the SSNAL is progressive.

Transform Invariant Low-Rank Textures, referred to as TILT, can accurately and robustly extract textural or geometric information in a 3D from user-specified windows in 2D in spite of significant corruptions and warping. It was discovered that the task can be characterized, both theoretically and numerically, by solving a sequence of matrix nuclear-norm and $\ell_1$-norm involved convex minimization problems. For solving this problem, the direct extension of Alternating Direction Method of Multipliers (ADMM) in an usual Gauss-Seidel manner often performs numerically well in practice but there is no theoretical guarantee on its convergence. In this paper, we resolve this dilemma by using the novel symmetric Gauss-Seidel (sGS) based ADMM developed by Li, Sun \& Toh (Math. Prog. 2016). The sGS-ADMM is guaranteed to converge and we shall demonstrate in this paper that it is also practically efficient than the directly extended ADMM. When the sGS technique is applied to this particular problem, we show that only one variable needs to be re-updated, and this updating hardly imposes any excessive computational cost. The sGS decomposition theorem of Li, Sun \& Toh (arXiv: 1703.06629) establishes the equivalent between sGS-ADMM and the classical ADMM with an additional semi-proximal term, so the convergence result is followed directly. Extensive experiments illustrate that the sGS-ADMM and its generalized variant have superior numerical efficiency over the directly extended ADMM., Comment: 9pages, 2 figures, 1 table

In this paper, we propose a generalized alternating direction method of multipliers (ADMM) with semi-proximal terms for solving a class of convex composite conic optimization problems, of which some are high-dimensional, to moderate accuracy. Our primary motivation is that this method, together with properly chosen semi-proximal terms, such as those generated by the recent advance of symmetric Gauss-Seidel technique, is applicable to tackling these problems. Moreover, the proposed method, which relaxes both the primal and the dual variables in a natural way with one relaxation factor in the interval $(0,2)$, has the potential of enhancing the performance of the classic ADMM. Extensive numerical experiments on various doubly non-negative semidefinite programming problems, with or without inequality constraints, are conducted. The corresponding results showed that all these multi-block problems can be successively solved, and the advantage of using the relaxation step is apparent., Comment: 30 pages

This paper is devoted to minimizing the sum of a smooth function and a nonsmooth $\ell_1$-regularized term. This problem as a special cases includes the $\ell_1$-regularized convex minimization problem in signal processing, compressive sensing, machine learning, data mining, etc. However, the non-differentiability of the $\ell_1$-norm causes more challenging especially in large problems encountered in many practical applications. This paper proposes, analyzes, and tests a Barzilai-Borwein gradient algorithm. At each iteration, the generated search direction enjoys descent property and can be easily derived by minimizing a local approximal quadratic model and simultaneously taking the favorable structure of the $\ell_1$-norm. Moreover, a nonmonotone line search technique is incorporated to find a suitable stepsize along this direction. The algorithm is easily performed, where the values of the objective function and the gradient of the smooth term are required at per-iteration. Under some conditions, the proposed algorithm is shown to be globally convergent. The limited experiments by using some nonconvex unconstrained problems from CUTEr library with additive $\ell_1$-regularization illustrate that the proposed algorithm performs quite well. Extensive experiments for $\ell_1$-regularized least squares problems in compressive sensing verify that our algorithm compares favorably with several state-of-the-art algorithms which are specifically designed in recent years., Comment: 20 pages

Total variation (TV) regularization is popular in image restoration and reconstruction due to its ability to preserve image edges. To date, most research activities on TV models concentrate on image restoration from blurry and noisy observations, while discussions on image reconstruction from random projections are relatively fewer. In this paper, we propose, analyze, and test a fast alternating minimization algorithm for image reconstruction from random projections via solving a TV regularized least-squares problem. The per-iteration cost of the proposed algorithm involves a linear time shrinkage operation, two matrix-vector multiplications and two fast Fourier transforms. Convergence, certain finite convergence and $q$-linear convergence results are established, which indicate that the asymptotic convergence speed of the proposed algorithm depends on the spectral radii of certain submatrix. Moreover, to speed up convergence and enhance robustness, we suggest an accelerated scheme based on an inexact alternating direction method. We present experimental results to compare with an existing algorithm, which indicate that the proposed algorithm is stable, efficient and competitive with TwIST \cite{TWIST} -- a state-of-the art algorithm for solving TV regularization problems.