Search

Sparsity promoting functions (SPFs) are commonly used in optimization problems to find solutions which are assumed or desired to be sparse in some basis. For example, the l1-regularized variation model and the Rudin-Osher-Fatemi total variation (ROF-TV) model are some of the most well-known variational models for signal and image denoising, respectively. However, recent work demonstrates that convexity is not always desirable in sparsity promoting functions. In this paper, we replace convex SPFs with their induced nonconvex SPFs and develop algorithms for the resulting model by exploring the intrinsic structures of the nonconvex SPFs. We also present simulations illustrating the performance of the SPF and the developed algorithms in image denoising., Comment: 23 pages, 10 figures, 3 tables

In this paper, we consider approximations of principal component projection (PCP) without explicitly computing principal components. This problem has been studied in several recent works. The main feature of existing approaches is viewing the PCP matrix as a matrix function. This underlying function is the composition of a step function with a rational function. To find an approximate PCP, the step function is approximated by a polynomial while the rational function is evaluated by a fast ridge regression solver. In this work, we further improve this process by replacing the rational function with carefully constructed polynomials of low degree. We characterize the properties of polynomials that are suitable for approximating PCP, and establish an optimization problem to select the optimal one from those polynomials. We show theoretically and confirm numerically that the resulting approximate PCP approach with optimal polynomials is indeed effective for approximations of principal component projection.

Recently the study of modeling a non-stationary signal as a superposition of amplitude and frequency-modulated Fourier-like oscillatory modes has been a very active research area. The synchrosqueezing transform (SST) is a powerful method for instantaneous frequency estimation and component separation of non-stationary multicomponent signals. The short-time Fourier transform-based SST (FSST for short) reassigns the frequency variable to sharpen the time-frequency representation and to separate the components of a multicomponent non-stationary signal. Very recently the FSST with a time-varying parameter, called the adaptive FSST, was introduced. The simulation experiments show that the adaptive FSST is very promising in instantaneous frequency estimation of the component of a multicomponent signal, and in accurate component recovery. However the theoretical analysis of the adaptive FSST has not been carried out. In this paper, we study the theoretical analysis of the adaptive FSST and obtain the error bounds for the instantaneous frequency estimation and component recovery with the adaptive FSST and the 2nd-order adaptive FSST.

Motivated by the minimax concave penalty based variable selection in high-dimensional linear regression, we introduce a simple scheme to construct structured semiconvex sparsity promoting functions from convex sparsity promoting functions and their Moreau envelopes. Properties of these functions are developed by leveraging their structure. In particular, we provide sparsity guarantees for the general family of functions. We further study the behavior of the proximity operators of several special functions including indicator functions of closed convex sets, piecewise quadratic functions, and the linear combinations of them. To demonstrate these properties, several concrete examples are presented and existing instances are featured as special cases., Comment: 29 pages, 34 figures

We consider the extragradient method to minimize the sum of two functions, the first one being smooth and the second being convex. Under the Kurdyka-Lojasiewicz assumption, we prove that the sequence produced by the extragradient method converges to a critical point of the problem and has finite length. The analysis is extended to the case when both functions are convex. We provide, in this case, a sublinear convergence rate, as for gradient-based methods. Furthermore, we show that the recent small-prox complexity result can be applied to this method. Considering the extragradient method is an occasion to describe an exact line search scheme for proximal decomposition methods. We provide details for the implementation of this scheme for the one norm regularized least squares problem and demonstrate numerical results which suggest that combining nonaccelerated methods with exact line search can be a competitive choice.

This paper shows that error bounds can be used as effective tools for deriving complexity results for first-order descent methods in convex minimization. In a first stage, this objective led us to revisit the interplay between error bounds and the Kurdyka-\L ojasiewicz (KL) inequality. One can show the equivalence between the two concepts for convex functions having a moderately flat profile near the set of minimizers (as those of functions with H\"olderian growth). A counterexample shows that the equivalence is no longer true for extremely flat functions. This fact reveals the relevance of an approach based on KL inequality. In a second stage, we show how KL inequalities can in turn be employed to compute new complexity bounds for a wealth of descent methods for convex problems. Our approach is completely original and makes use of a one-dimensional worst-case proximal sequence in the spirit of the famous majorant method of Kantorovich. Our result applies to a very simple abstract scheme that covers a wide class of descent methods. As a byproduct of our study, we also provide new results for the globalization of KL inequalities in the convex framework. Our main results inaugurate a simple methodology: derive an error bound, compute the desingularizing function whenever possible, identify essential constants in the descent method and finally compute the complexity using the one-dimensional worst case proximal sequence. Our method is illustrated through projection methods for feasibility problems, and through the famous iterative shrinkage thresholding algorithm (ISTA), for which we show that the complexity bound is of the form $O(q^{k})$ where the constituents of the bound only depend on error bound constants obtained for an arbitrary least squares objective with $\ell^1$ regularization.

In this paper, we study a simple iterative method for finding the Dantzig selector, which was designed for linear regression problems. The method consists of two main stages. The first stage is to approximate the Dantzig selector through a fixed-point formulation of solutions to the Dantzig selector problem. The second stage is to construct a new estimator by regressing data onto the support of the approximated Dantzig selector. We compare our method to an alternating direction method, and present the results of numerical simulations using both the proposed method and the alternating direction method on synthetic and real data sets. The numerical simulations demonstrate that the two methods produce results of similar quality, however the proposed method tends to be significantly faster., Comment: 15 pages, 5 figures. Submitted to Computational Statistics and Data Analysis

The problem of 1-bit compressive sampling is addressed in this paper. We introduce an optimization model for reconstruction of sparse signals from 1-bit measurements. The model targets a solution that has the least l0-norm among all signals satisfying consistency constraints stemming from the 1-bit measurements. An algorithm for solving the model is developed. Convergence analysis of the algorithm is presented. Our approach is to obtain a sequence of optimization problems by successively approximating the l0-norm and to solve resulting problems by exploiting the proximity operator. We examine the performance of our proposed algorithm and compare it with the binary iterative hard thresholding (BIHT) [10] a state-of-the-art algorithm for 1-bit compressive sampling reconstruction. Unlike the BIHT, our model and algorithm does not require a prior knowledge on the sparsity of the signal. This makes our proposed work a promising practical approach for signal acquisition., Comment: 27 pages and 10 figures

In this paper, we first propose a general interpolation algorithm in a free module of a linearized polynomial ring, and then apply this algorithm to decode several important families of codes, Gabidulin codes, KK codes and MV codes. Our decoding algorithm for Gabidulin codes is different from the polynomial reconstruction algorithm by Loidreau. When applied to decode KK codes, our interpolation algorithm is equivalent to the Sudan-style list-1 decoding algorithm proposed by K/"otter and Kschischang for KK codes. The general interpolation approach is also capable of solving the interpolation problem for the list decoding of MV codes proposed by Mahdavifar and Vardy, and has a lower complexity than solving linear equations.

While random linear network coding is a powerful tool for disseminating information in communication networks, it is highly susceptible to errors caused by various sources. Due to error propagation, errors greatly deteriorate the throughput of network coding and seriously undermine both reliability and security of data. Hence error control for network coding is vital. Recently, constant-dimension codes (CDCs), especially K\"otter-Kschischang (KK) codes, have been proposed for error control in random linear network coding. KK codes can also be constructed from Gabidulin codes, an important class of rank metric codes. Rank metric decoders have been recently proposed for both Gabidulin and KK codes, but they have high computational complexities. Furthermore, it is not clear whether such decoders are feasible and suitable for hardware implementations. In this paper, we reduce the complexities of rank metric decoders and propose novel decoder architectures for both codes. The synthesis results of our decoder architectures for Gabidulin and KK codes with limited error-correcting capabilities over small fields show that our architectures not only are affordable, but also achieve high throughput., Comment: 14 pages, 12 figures, accepted by IEEE Trans. VLSI Syst