Abstract. The nonconvex optimization method has attracted increasing attention due to its excellent ability of promoting sparsity in signal processing, image restoration, and machine learning. In this paper, we consider a new minimization method [Formula: see text] [Formula: see text] and its applications in signal recovery and image reconstruction because [Formula: see text] minimization provides an effective way to solve the [Formula: see text]-ratio sparsity minimization model. Our main contributions are to establish a convex hull decomposition for [Formula: see text] and investigate RIP-based conditions for stable signal recovery and image reconstruction by [Formula: see text] minimization. For one-dimensional signal recovery, our derived RIP condition extends existing results. For two-dimensional image recovery under [Formula: see text] minimization of image gradients, we provide the error estimate of the resulting optimal solutions in terms of sparsity and noise level, which is missing in the literature. Numerical results of the limited angle problem in computed tomography imaging and image deblurring are presented to validate the efficiency and superiority of the proposed minimization method among the state-of-art image recovery methods.

Transformed $L_1$ (TL1) regularization has been shown to have comparable signal recovery capability with $L_1-L_2$ regularization and $L_1/L_2$ regularization, regardless of whether the measurement matrix satisfies the restricted isometry property (RIP). In the spirit of the TL1 method, we introduce a transformed total variation (TTV) minimization model to investigate robust image recovery from a certain number of noisy measurements by the proposed TTV minimization model in this paper. An optimal error bound, up to a logarithmic factor, of robust image recovery from compressed measurements via the TTV minimization model is established, and the RIP based condition is improved compared with total variation (TV) minimization. Numerical results of image reconstruction demonstrate our theoretical results and illustrate the efficiency of the TTV minimization model among state-of-the-art methods. Empirically, the error bound between the reconstructed image and the original image is shown to be better than that produced by TV minimization.

The $\ell_1-\ell_2$ regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the $\ell_1-\ell_2$ minimization method shows that it has superior sparse recovery performance over the classical $\ell_1$ minimization method. The motivation and major contribution of this paper is to provide a positive answer to the open problem posed in [T.-H. Ma, Y. Lou, and T.-Z. Huang, SIAM J. Imaging Sci., 10 (2017), pp. 1346--1380] about the sufficient conditions that can be sharpened for the $\ell_1-\ell_2$ minimization method. The novel technique used in our analysis of the $\ell_1-\ell_2$ minimization method is a crucial sparse representation adapted to the $\ell_1-\ell_2$ metric which is different from the other state-of-the-art works in the context of the $\ell_1-\ell_2$ minimization method. The new restricted isometry property (RIP) analysis is better than the existing RIP based conditions to guarantee the exact and stable recovery of signals.

A complete characterization for the restricted isometry constant (RIC) bounds on$\delta _{{{ tk}}}$for all$ {t}>0$is an important problem on recovery of sparse signals with prior support information via weighted$\ell _{{p}}$-minimization ($0 < {p} \leqslant 1$). In this paper, new bounds on the restricted isometry constants$\delta _{{{ tk}}}$($0 < {t} < \frac {4}{3}{d}$), where$d$is a key constant determined by prior support information, are established to guarantee the sparse signal recovery via the weighted$\ell _{{p}}$minimization in both noiseless and noisy settings. This result fills a vacancy on$\delta _{{{ tk}}}$with$0 < {t} < \frac {4}{3}{d}$, compared with previous works on$\delta _{{{ tk}}}$(${t} \geqslant \frac {4}3{d}$). We show that, when the accuracy of prior support estimate is at least 50%, the new recovery condition in terms of$\delta _{{{ tk}}}$($0 < {t} < \frac {4}{3}{d}$) via weighted$\ell _{1}$minimization is weaker than the condition required by classical$\ell _{1}$minimization without weighting. Our weighted$\ell _{1}$minimization gives better recovery error bounds in noisy setting. Similarly, the new recovery condition in terms of$\delta _{{{ tk}}}$($0 < {t} < \frac {4}{3}{d}$) is extended to weighted$\ell _{{p}}$($0 < {p} < 1$) minimization, and it is also weaker than the condition obtained by standard non-convex$\ell _{{p}}$($0 < {p} < 1$) minimization without weighting. Numerical illustrations are provided to demonstrate our new theoretical results.

A* orthogonal matching pursuit (A* OMP) aims at combination of best‐first tree search with the OMP algorithm for the compressed sensing problem. In this study, the authors present a new analysis for the A* OMP algorithm using the restricted isometry property (RIP). The results show that if the sampling matrix satisfies the RIP with ( ), then under some constraints on SNR, A* OMP accurately recovers the support of any K ‐sparse signal from the samples , where B is the number of child paths for each candidate in the algorithm. In addition, the proposed condition is an optimal condition that guarantees the success of A* OMP in the noise‐free case.

In this paper, we consider the recovery of k-sparse signals using the weighted ℓp(0tkwith dp(0tkwith t(a+1)k(a > 1). Second, we provide a sufficient condition on δtkwith 1p(02kin the literature. Last, various numerical examples are presented to demonstrate the better performance of the weighted ℓp(0p(0 <; p ≤1) minimization.

The null space property (NSP), which depends only on the null space of the column space of measurement matrix, has received much attention in compressed sensing. This letter considers NSP of the truncated l1-2minimization. It provides two versions of NSP of the truncated l1-2minimization, under which we present sufficient conditions for the truncated l1-2minimization to recover sparse and compressible signals. In addition, we discuss that the truncated l1-2stable NSP holds by Gaussian matrices of appropriate sizes with overwhelming probability.

Interleaving is commonly used to guard against burst errors since it provides a form of time diversity in the coded sequence. A novel algorithm for identifying the helical interleaving of the first type is presented based on the linear property of channel coding and the structure characteristic of the helical interleaver. We make use of the basis of parity-check vectors to locate codewords within the interleaved block to estimate the parameters at the output of a binary symmetric channel. Experimental results are run to validate the algorithm.