This paper studies sparse recovery using expander graphs in the context of the noisy linear model b = Ax0 +e, where x0 ∈ Rnis an (approximately) sparse signal and A ∈ {0, 1}m×nis a measurement matrix derived from the biadjacency matrix of a lossless expander. Our key contributions are threefold. First, we extend the (ℓ1, ℓ1-Restricted Isometry Property (RIP) for regular lossless expanders to quasi-regular lossless expanders, providing a sharper tool for sparse recovery analysis. Leveraging this tool, we derive better bounds on the expected estimation error for two LAD (Least Absolute Deviations) type models. As an application in the link delay estimation problem, our theoretical results improve the recovery error in the literature.We present extensive numerical experiments that validate our theoretical findings, and demonstrate that the proposed ℓ1regularized LAD method outperforms state-of-the-art methods when applied to a delayed signal with a larger number of substantial nonzero entries.

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.

Recently, non-convex and non-linear metrics have been introduced in compressed sensing to promote sparsity. This letter proposes an extension of the previously proposed$\ell _{1}/\ell _{2}$minimization method for sparse recovery using the$\ell _{1}/\ell _{p}$minimization method with$p\gt 1$. We establish sufficient conditions for the$\ell _{1}/\ell _{p}$minimization to recover sparse signals under the restricted isometry property (RIP). Additionally, we develop an effective algorithm to solve the$\ell _{1}/\ell _{p}$minimization problem. Experiments show the proposed method is comparable to state-of-the-art methods for sparse signal recovery.

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.

Generalized spatial modulation (GSM), which is a novel multiple-input multiple-output (MIMO) transmission technique, has attracted massive research attention in recent years. In this paper, we first utilize the orthogonal least squares (OLS) based detector for GSM detection. Then, we develop a sufficient condition of successful detection for the OLS based detector based on the restricted isometry property (RIP) of the channel matrix. Moreover, we prove that our sufficient condition is optimal. Finally, numerical simulations are conducted to illustrate that the proposed OLS based detector has better detection performance than the orthogonal matching pursuit (OMP) based detector with more or less the same time complexity.

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 covariance-assisted matching pursuit (CAMP) algorithm has recently been proposed for recovering sparse signals f from noisy linear measurements based on a priori knowledge of the covariance and mean of the nonzero coefficients of f. It utilizes the a priori knowledge by incorporating the Gauss-Markov theorem into the orthogonal matching pursuit (OMP) algorithm and has a significantly better reconstruction performance than OMP. This letter develops sufficient conditions of exact support recovery of any k-sparse signals f via CAMP ink iterations, under the 12-bounded and Gaussian noises. These sufficient conditions are based on the restricted isometry constant of the sensing matrix and minimum magnitude of the nonzero elements of f, and are much better than the existing ones.

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.